Tight lower bounds on the size of sweeping automata

DOI10.1006/JCSS.2001.1783zbMath1006.68071OpenAlexW2091988401MaRDI QIDQ1604196

Hing-Man Leung

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/7e1273a2f28f2db7c252132ea7defdb1b1505a89

zbMATH Keywords

sweeping automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Complexity of multi-head finite automata: origins and directions ⋮ Sweeping input-driven pushdown automata ⋮ Nondeterminism Is Essential in Small 2FAs with Few Reversals ⋮ New size hierarchies for two way automata ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ On the descriptional power of heads, counters, and pebbles

Cites Work

• Unnamed Item
• Unnamed Item
• Finite automata and unary languages
• Lower bounds on the size of sweeping automata
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Nondeterminism and the size of two way finite automata
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata

This page was built for publication: Tight lower bounds on the size of sweeping automata