Complementing two-way finite automata
From MaRDI portal
Publication:2643079
Recommendations
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3568031 (Why is no real title available?)
- scientific article; zbMATH DE number 1502111 (Why is no real title available?)
- A note on the reduction of two-way automata to one-way automata
- Complementing unary nondeterministic automata
- Converting two-way nondeterministic unary automata into simpler automata.
- Descriptional complexity of machines with limited resources
- Deterministic moles cannot solve liveness
- Exact lower time bounds for computing Boolean functions on CREW PRAMs
- Halting space-bounded computations
- Lower bounds on the size of sweeping automata
- Nondeterminism and the size of two way finite automata
- Nondeterministic Space is Closed under Complementation
- 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
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Probabilistic automata
- Quantum automata and quantum grammars
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
- The method of forced enumeration for nondeterministic automata
Cited in
(40)- State complexity of union and intersection on graph-walking automata
- Reversibility of computations in graph-walking 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 finite automata to unambiguous finite automata
- On the length of shortest strings accepted by two-way finite automata
- On the length of shortest strings accepted by two-way finite automata
- On multi-head automata with restricted nondeterminism
- Developments in Language Theory
- New size hierarchies for two way automata
- Size complexity of rotating and sweeping automata
- Unambiguous finite automata over a unary alphabet
- Once-Marking and Always-Marking 1-Limited Automata
- State complexity of operations on two-way deterministic finite automata over a unary alphabet
- Two-way non-uniform finite automata
- Investigations on automata and languages over a unary alphabet
- Notes on looping deterministic two-way pushdown automata
- Small Sweeping 2NFAs Are Not Closed Under Complement
- State complexity of operations on two-way finite automata over a unary alphabet
- Homomorphisms and inverse homomorphisms on graph-walking automata
- Size Complexity of Two-Way Finite Automata
- Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
- Linear-time limited automata
- Two-Way Non-Uniform Finite Automata
- TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
- Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
- State complexity of transforming graph-walking automata to halting, returning and reversible
- Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formulæ
- On the state complexity of operations on two-way finite automata
- Descriptional complexity of unambiguous input-driven pushdown automata
- On the transformation of two-way deterministic finite automata to unambiguous finite automata
- Improved complement for two-way alternating automata
- On the translation of automata to linear temporal logic
- Two-way finite automata: old and recent results
- Complement for two-way alternating automata
- On the State Complexity of Operations on Two-Way Finite Automata
- Complement for two-way alternating automata
- Removing nondeterminism in constant height pushdown automata
- On the Size Complexity of Rotating and Sweeping Automata
- Two-way automata characterizations of L/poly versus NL
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)
