Two-way unary automata versus logarithmic space
From MaRDI portal
Publication:549665
DOI10.1016/J.IC.2011.03.003zbMATH Open1216.68143OpenAlexW2005397173WikidataQ61677514 ScholiaQ61677514MaRDI QIDQ549665FDOQ549665
Viliam Geffert, Giovanni Pighizzini
Publication date: 18 July 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2011.03.003
Recommendations
- Two-Way Unary Automata versus Logarithmic Space
- Two-way automata versus logarithmic space
- Two-Way Automata versus Logarithmic Space
- scientific article; zbMATH DE number 1502111
- Two-Way Non-Uniform Finite Automata
- Two-way non-uniform finite automata
- scientific article; zbMATH DE number 1848284
- State complexity of operations on two-way finite automata over a unary alphabet
- Unary Languages Recognized by Two-Way One-Counter Automata
- On the transformation of two-way deterministic finite automata to unambiguous finite automata
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relationships between nondeterministic and deterministic tape complexities
- Turing machines with sublogarithmic space
- Making Nondeterminism Unambiguous
- Title not available (Why is that?)
- State-complexity of finite-state devices, state compressibility and incompressibility
- Turing machines that take advice
- Lower bounds on the size of sweeping automata
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Size Complexity of Two-Way Finite Automata
- Nondeterminism and the size of two way finite automata
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Converting two-way nondeterministic unary automata into simpler automata.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Space-bounded reducibility among combinatorial problems
- Deterministic moles cannot solve liveness
- Unary finite automata vs. arithmetic progressions
Cited In (14)
- Title not available (Why is that?)
- Two-way automata characterizations of L/poly versus NL
- Two-Way Automata versus Logarithmic Space
- Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
- Investigations on Automata and Languages Over a Unary Alphabet
- Oblivious two-way finite automata: decidability and complexity
- DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ
- State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis
- Converting two-way nondeterministic unary automata into simpler automata.
- Two-way automata versus logarithmic space
- Two-way automata making choices only at the endmarkers
- Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
- Boolean language operations on nondeterministic automata with a pushdown of constant height
- Two-Way Unary Automata versus Logarithmic Space
This page was built for publication: Two-way unary automata versus logarithmic space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q549665)
