Lower bounds on the size of sweeping automata
From MaRDI portal
Publication:1145513
DOI10.1016/0022-0000(80)90034-3zbMath0445.68064WikidataQ60019650 ScholiaQ60019650MaRDI QIDQ1145513
Publication date: 1980
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(80)90034-3
68Q45: Formal languages and automata
Related Items
DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ, NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES, On the power of Las Vegas II: Two-way finite automata, Size complexity of rotating and sweeping automata, Two-way automata making choices only at the endmarkers, Two-way unary automata versus logarithmic space, Descriptional and computational complexity of finite automata -- a survey, Complexity of multi-head finite automata: origins and directions, Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal, Finite automata and unary languages, Complexity results for two-way and multi-pebble automata and their logics, Converting two-way nondeterministic unary automata into simpler automata., Tight lower bounds on the size of sweeping automata, On the descriptional power of heads, counters, and pebbles, Communication complexity method for measuring nondeterminism in finite automata, On multi-partition communication complexity, Oblivious two-way finite automata: decidability and complexity, Infinite vs. finite size-bounded randomized computations, 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, NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, Deterministic blow-ups of minimal NFA's, On the Size Complexity of Rotating and Sweeping Automata, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, Descriptional and Computational Complexity of Finite Automata, Size Complexity of Two-Way Finite Automata
Cites Work
