We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the Size of Two-Way Reasonable Automata for the Liveness Problem.
- Authors
Bianchi, Maria Paola; Hromkovič, Juraj; Kováč, Ivan
- Abstract
The existence of a substantial gap between deterministic and nondeterministic two-way automata is one of the most famous open problems in automata theory. This problem is also related to the fundamental DLOG vs. NLOG question. An exponential gap between the number of states of two-way nondeterministic automata (2 NFAS) and their deterministic counterparts (2 DFAS) has been proved only for some restrictions of 2 DFAS up to now. It seems that the hardness of this problem lies in the fact that, when trying to prove lower bounds, we must consider every possible automaton, without imposing any particular structure or meaning to the states, while when designing a specific automaton, we always assign an unambiguous interpretation to the states. In an attempt to capture the concept of meaning of states, a new model of two-way automata, namely reasonable automaton ( RA), was introduced in [6]. In a RA, each state is associated with a logical formula expressing some properties of the input word, and transitions are designed to maintain consistency within this setting. In this paper we extend the study, started in [6], of the descriptional complexity of RAS solving the liveness problem, showing several lower and upper bounds with respect to the logic used for describing the meaning of the individual states.
- Subjects
MACHINE theory; MATHEMATICAL bounds; DETERMINISTIC finite automata; PROBLEM solving; MATHEMATICAL formulas
- Publication
International Journal of Foundations of Computer Science, 2018, Vol 29, Issue 2, p187
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054118400038