scientific article; zbMATH DE number 3568031
From MaRDI portal
Publication:4139689
zbMath0364.68057MaRDI QIDQ4139689
Publication date: 1977
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Finite automata and unary languages ⋮ Complementing two-way finite automata ⋮ Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Converting two-way nondeterministic unary automata into simpler automata. ⋮ Lower bounds on the size of sweeping automata ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ On the State Complexity of Complements, Stars, and Reversals of Regular Languages ⋮ Two-way automata making choices only at the endmarkers ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis ⋮ Two-Way Automata versus Logarithmic Space ⋮ Nondeterminism Is Essential in Small 2FAs with Few Reversals ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Two-way automata versus logarithmic space ⋮ State complexity of some operations on binary regular languages ⋮ Two-way unary automata versus logarithmic space ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ Size Complexity of Two-Way Finite Automata ⋮ Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs ⋮ Deterministic blow-ups of minimal NFA's ⋮ Two-way automata characterizations of L/poly versus NL
