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
On the Size of Two-Way Reasonable Automata for the Liveness Problem, Complexity results for multi-pebble automata and their logics, 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, On the state complexity of operations on two-way finite automata, 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, Reversibility of computations in graph-walking automata, Oblivious two-way finite automata: decidability and complexity, Boolean language operations on nondeterministic automata with a pushdown of constant height, Infinite vs. finite size-bounded randomized computations, Complementing two-way finite automata, Complexity of Promise Problems on Classical and Quantum 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 of Two-Way Reasonable Automata for the Liveness Problem, 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
