Nondeterminism and the size of two way finite automata

DOI10.1145/800133.804357zbMath1282.68160OpenAlexW2034243894WikidataQ57380763 ScholiaQ57380763MaRDI QIDQ5402568

Publication date: 14 March 2014

Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/800133.804357

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (77)

State-complexity of finite-state devices, state compressibility and incompressibility ⋮ On multi-partition communication complexity ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ The equivalence of pebbles and sensing heads for finite automata ⋮ Finite automata and unary languages ⋮ Infinite vs. finite size-bounded randomized computations ⋮ Complementing two-way finite automata ⋮ A note on the reduction of two-way automata to one-way automata ⋮ Tradeoffs for language recognition on alternating machines ⋮ Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Halting space-bounded computations ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Improved complement for two-way alternating automata ⋮ Weight-reducing Turing machines ⋮ Unnamed Item ⋮ Converting two-way nondeterministic unary automata into simpler automata. ⋮ From bidirectionality to alternation. ⋮ The size of power automata. ⋮ Size complexity of rotating and sweeping automata ⋮ Lower bounds on the size of sweeping automata ⋮ Optimal 2DFA Algorithms for One-Way Liveness on Two and Three Symbols ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ Operational state complexity revisited: the contribution of monsters and modifiers ⋮ Complexity of exclusive nondeterministic finite automata ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ Two-way machines and de Bruijn words ⋮ Once-Marking and Always-Marking 1-Limited Automata ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Two-way deterministic finite automata are exponentially more succinct than sweeping automata ⋮ An alternating hierarchy for finite automata ⋮ Fooling a two way automaton or one pushdown store is better than one counter for two way machines ⋮ Two-way automata and length-preserving homomorphisms ⋮ On the State Complexity of Complements, Stars, and Reversals of Regular Languages ⋮ On the State Complexity of Operations on Two-Way Finite Automata ⋮ On the Size Complexity of Rotating and Sweeping Automata ⋮ Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal ⋮ Two-way automata making choices only at the endmarkers ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis ⋮ Magic numbers in the state hierarchy of finite automata ⋮ Two-Way Automata versus Logarithmic Space ⋮ Nondeterminism Is Essential in Small 2FAs with Few Reversals ⋮ Two double-exponential gaps for automata with a limited pushdown ⋮ New size hierarchies for two way automata ⋮ Intersection and union of regular languages and state complexity ⋮ Partial orders on words, minimal elements of regular languages, and state complexity ⋮ Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Two-way automata versus logarithmic space ⋮ State complexity of some operations on binary regular languages ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Two-way unary automata versus logarithmic space ⋮ From Philosophical to Industrial Logics ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Complement for two-way alternating automata ⋮ Alternation in two-way finite automata ⋮ On the power of Las Vegas II: Two-way finite automata ⋮ From Monadic Logic to PSL ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ From Hadamard expressions to weighted rotating automata and back ⋮ From Hadamard expressions to weighted rotating automata and back ⋮ Both Ways Rational Functions ⋮ The complexity of weakly recognizing morphisms ⋮ Size Complexity of Two-Way Finite Automata ⋮ Unnamed Item ⋮ Two-Way Automata in Coq ⋮ Self-Verifying Finite Automata and Descriptional Complexity ⋮ Operations on Weakly Recognizing Morphisms ⋮ On NFAs where all states are final, initial, or both ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Complement on Free and Ideal Languages ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines ⋮ Tight lower bounds on the size of sweeping automata ⋮ Two-way automata characterizations of L/poly versus NL

This page was built for publication: Nondeterminism and the size of two way finite automata