Complementing two-way finite automata
From MaRDI portal
Publication:2643079
DOI10.1016/j.ic.2007.01.008zbMath1121.68063OpenAlexW1989657066WikidataQ57380787 ScholiaQ57380787MaRDI QIDQ2643079
Viliam Geffert, Giovanni Pighizzini, Carlo Mereghetti
Publication date: 23 August 2007
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2007.01.008
Related Items
Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata ⋮ Improved complement for two-way alternating automata ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ Size complexity of rotating and sweeping automata ⋮ Unambiguous finite automata over a unary alphabet ⋮ State complexity of transforming graph-walking automata to halting, returning and reversible ⋮ On the translation of automata to linear temporal logic ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ Once-Marking and Always-Marking 1-Limited Automata ⋮ On multi-head automata with restricted nondeterminism ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ On the State Complexity of Operations on Two-Way Finite Automata ⋮ On the Size Complexity of Rotating and Sweeping Automata ⋮ Reversibility of computations in graph-walking automata ⋮ Two-way automata making choices only at the endmarkers ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ On the state complexity of operations on two-way finite automata ⋮ Removing nondeterminism in constant height pushdown automata ⋮ Linear-time limited automata ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Complement for two-way alternating automata ⋮ State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet ⋮ Size Complexity of Two-Way Finite Automata ⋮ DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ ⋮ State complexity of union and intersection on graph-walking automata ⋮ Two-way automata characterizations of L/poly versus NL
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The method of forced enumeration for nondeterministic automata
- A note on the reduction of two-way automata to one-way automata
- Halting space-bounded computations
- Lower bounds on the size of sweeping automata
- Exact lower time bounds for computing Boolean functions on CREW PRAMs
- Converting two-way nondeterministic unary automata into simpler automata.
- Quantum automata and quantum grammars
- Complementing unary nondeterministic automata
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Nondeterministic Space is Closed under Complementation
- Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
- Nondeterminism and the size of two way finite automata
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- Probabilistic automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- On the power of Las Vegas II: Two-way finite automata
