scientific article; zbMATH DE number 2038729

zbMath1039.68068MaRDI QIDQ4449194

Juraj Hromkovič, Georg Schnitger

Publication date: 8 February 2004

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2719/27190439.htm

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

nondeterminismFinite automatadescriptional complexity of regular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (14)

On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Complexity of multi-head finite automata: origins and directions ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ 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 ⋮ 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 ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Two-way unary automata versus logarithmic space ⋮ Size Complexity of Two-Way Finite Automata ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines

This page was built for publication: