scientific article

zbMath0479.68081MaRDI QIDQ3938525

Piotr Berman

Publication date: 1980

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

zbMATH Keywords

regular languagesacception of languagesdeterministic two-way finite automatonminimal sizeautomata size

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (10)

On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Converting two-way nondeterministic unary automata into simpler automata. ⋮ Size complexity of rotating and sweeping 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 ⋮ On the Size Complexity of Rotating and Sweeping Automata ⋮ Two-way automata making choices only at the endmarkers ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ On the power of Las Vegas II: Two-way finite automata ⋮ Tight lower bounds on the size of sweeping automata

This page was built for publication: