Lower bounds on the size of sweeping automata
From MaRDI portal
Publication:1145513
DOI10.1016/0022-0000(80)90034-3zbMath0445.68064OpenAlexW1990283467WikidataQ60019650 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
Related Items (39)
On multi-partition communication complexity ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Complexity results for two-way and multi-pebble automata and their logics ⋮ Finite automata and unary languages ⋮ Infinite vs. finite size-bounded randomized computations ⋮ Complementing two-way finite automata ⋮ Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Converting two-way nondeterministic unary automata into simpler automata. ⋮ Size complexity of rotating and sweeping automata ⋮ Jump complexity of finite automata with translucent letters ⋮ Once-Marking and Always-Marking 1-Limited Automata ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ On the Size Complexity of Rotating and Sweeping Automata ⋮ Reversibility of computations in graph-walking automata ⋮ Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal ⋮ Two-way automata making choices only at the endmarkers ⋮ NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES ⋮ Complexity results for multi-pebble automata and their logics ⋮ 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 ⋮ On the state complexity of operations on two-way finite automata ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Two-way unary automata versus logarithmic space ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ On the power of Las Vegas II: Two-way finite automata ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Size Complexity of Two-Way Finite Automata ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Descriptional complexity of regular languages ⋮ DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ ⋮ Deterministic blow-ups of minimal NFA's ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines ⋮ Tight lower bounds on the size of sweeping automata
Cites Work
This page was built for publication: Lower bounds on the size of sweeping automata
