Publication:4139689

zbMath0364.68057MaRDI QIDQ4139689

Piotr Berman, Andrzej Lingas

Publication date: 1977

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

On the Size of Two-Way Reasonable Automata for the Liveness Problem, State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis, Two-way automata making choices only at the endmarkers, Two-way unary automata versus logarithmic space, Complexity of multi-head finite automata: origins and directions, Finite automata and unary languages, Lower bounds on the size of sweeping automata, Converting two-way nondeterministic unary automata into simpler automata., Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs, State complexity of some operations on binary regular languages, Oblivious two-way finite automata: decidability and complexity, Two-way automata versus logarithmic space, Two-way automata characterizations of L/poly versus NL, Boolean language operations on nondeterministic automata with a pushdown of constant height, Complementing two-way finite automata, Translation from classical two-way automata to pebble two-way automata, Two-Way Automata versus Logarithmic Space, Nondeterminism Is Essential in Small 2FAs with Few Reversals, Deterministic blow-ups of minimal NFA's, On the Size of Two-Way Reasonable Automata for the Liveness Problem, On the State Complexity of Complements, Stars, and Reversals of Regular Languages, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, Size Complexity of Two-Way Finite Automata