Complementing two-way finite automata
From MaRDI portal
Publication:2643079
DOI10.1016/J.IC.2007.01.008zbMATH Open1121.68063DBLPjournals/iandc/GeffertMP07OpenAlexW1989657066WikidataQ57380787 ScholiaQ57380787MaRDI QIDQ2643079FDOQ2643079
Authors: Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini 
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
Recommendations
Cites Work
- Title not available (Why is that?)
- Probabilistic automata
- Nondeterministic Space is Closed under Complementation
- Exact lower time bounds for computing Boolean functions on CREW PRAMs
- The method of forced enumeration for nondeterministic automata
- Halting space-bounded computations
- Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
- Descriptional complexity of machines with limited resources
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- A note on the reduction of two-way automata to one-way automata
- Quantum automata and quantum grammars
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- Lower bounds on the size of sweeping automata
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Nondeterminism and the size of two way finite automata
- On the power of Las Vegas II: Two-way finite automata
- Converting two-way nondeterministic unary automata into simpler automata.
- Complementing unary nondeterministic automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Deterministic moles cannot solve liveness
Cited In (41)
- Reversibility of computations in graph-walking automata
- Translation from classical two-way automata to pebble two-way automata
- On the State Complexity of Operations on Two-Way Finite Automata
- On the length of shortest strings accepted by two-way finite automata
- Linear-time limited automata
- On the length of shortest strings accepted by two-way finite automata
- State complexity of transforming graph-walking automata to halting, returning and reversible
- Complement for two-way alternating automata
- Two-way automata characterizations of L/poly versus NL
- Size complexity of rotating and sweeping automata
- Unambiguous finite automata over a unary alphabet
- New size hierarchies for two way automata
- On multi-head automata with restricted nondeterminism
- State complexity of operations on two-way finite automata over a unary alphabet
- Descriptional complexity of unambiguous input-driven pushdown automata
- Homomorphisms and inverse homomorphisms on graph-walking automata
- On the transformation of two-way finite automata to unambiguous finite automata
- State complexity of operations on two-way deterministic finite automata over a unary alphabet
- Developments in Language Theory
- Investigations on automata and languages over a unary alphabet
- Notes on looping deterministic two-way pushdown automata
- A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
- TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
- On the transformation of two-way deterministic finite automata to unambiguous finite automata
- Removing nondeterminism in constant height pushdown automata
- Two-way automata making choices only at the endmarkers
- Once-Marking and Always-Marking 1-Limited Automata
- Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
- Improved complement for two-way alternating automata
- Complement for two-way alternating automata
- Two-way non-uniform finite automata
- Two-Way Non-Uniform Finite Automata
- Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formulæ
- On the Size Complexity of Rotating and Sweeping Automata
- Small Sweeping 2NFAs Are Not Closed Under Complement
- Size Complexity of Two-Way Finite Automata
- On the translation of automata to linear temporal logic
- Two-way finite automata: old and recent results
- On the state complexity of operations on two-way finite automata
- Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
- State complexity of union and intersection on graph-walking automata
This page was built for publication: Complementing two-way finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643079)
