Pages that link to "Item:Q1145513"
From MaRDI portal
The following pages link to Lower bounds on the size of sweeping automata (Q1145513):
Displayed 39 items.
- Size complexity of rotating and sweeping automata (Q414916) (← links)
- Two-way automata making choices only at the endmarkers (Q476168) (← links)
- On the state complexity of operations on two-way finite automata (Q515574) (← links)
- Two-way unary automata versus logarithmic space (Q549665) (← links)
- Descriptional and computational complexity of finite automata -- a survey (Q553312) (← links)
- Complexity of multi-head finite automata: origins and directions (Q616495) (← links)
- Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal (Q656586) (← links)
- Finite automata and unary languages (Q1099644) (← links)
- Complexity results for two-way and multi-pebble automata and their logics (Q1349896) (← links)
- Converting two-way nondeterministic unary automata into simpler automata. (Q1401239) (← links)
- Tight lower bounds on the size of sweeping automata (Q1604196) (← links)
- On the descriptional power of heads, counters, and pebbles (Q1763719) (← links)
- Communication complexity method for measuring nondeterminism in finite automata (Q1854501) (← links)
- On multi-partition communication complexity (Q1886038) (← links)
- Descriptional complexity of regular languages (Q2074214) (← links)
- Converting nondeterministic two-way automata into small deterministic linear-time machines (Q2105419) (← links)
- Reversibility of computations in graph-walking automata (Q2216129) (← links)
- Oblivious two-way finite automata: decidability and complexity (Q2252534) (← links)
- Boolean language operations on nondeterministic automata with a pushdown of constant height (Q2403237) (← links)
- Infinite vs. finite size-bounded randomized computations (Q2637645) (← links)
- Complementing two-way finite automata (Q2643079) (← links)
- Complexity of Promise Problems on Classical and Quantum Automata (Q2944886) (← links)
- Translation from classical two-way automata to pebble two-way automata (Q2998731) (← links)
- Two-Way Automata versus Logarithmic Space (Q3007639) (← links)
- Nondeterminism Is Essential in Small 2FAs with Few Reversals (Q3012920) (← links)
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY (Q3395129) (← links)
- Deterministic blow-ups of minimal NFA's (Q3421910) (← links)
- On the Size of Two-Way Reasonable Automata for the Liveness Problem (Q3451094) (← links)
- On the Size Complexity of Rotating and Sweeping Automata (Q3533032) (← links)
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity (Q3602795) (← links)
- Descriptional and Computational Complexity of Finite Automata (Q3618565) (← links)
- Size Complexity of Two-Way Finite Automata (Q3637213) (← links)
- Complexity results for multi-pebble automata and their logics (Q4632417) (← links)
- On the Size of Two-Way Reasonable Automata for the Liveness Problem (Q4640037) (← links)
- DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ (Q5495414) (← links)
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES (Q5696955) (← links)
- On the power of Las Vegas II: Two-way finite automata (Q5958109) (← links)
- Jump complexity of finite automata with translucent letters (Q6190004) (← links)
- Once-Marking and Always-Marking 1-Limited Automata (Q6204137) (← links)