Complementing two-way finite automata

DOI10.1016/j.ic.2007.01.008zbMath1121.68063DBLPjournals/iandc/GeffertMP07OpenAlexW1989657066WikidataQ57380787 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

zbMATH Keywords

formal languagesdescriptional complexityfinite state automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (30)

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

This page was built for publication: Complementing two-way finite automata