On the state complexity of operations on two-way finite automata
From MaRDI portal
Publication:515574
DOI10.1016/j.ic.2016.12.007zbMath1371.68153OpenAlexW2560045680MaRDI QIDQ515574
Alexander Okhotin, Galina Jirásková
Publication date: 16 March 2017
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2016.12.007
Related Items (5)
Performing regular operations with 1-limited automata ⋮ Homomorphisms on graph-walking automata ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ Operational complexity: NFA-to-DFA trade-off ⋮ State complexity of unambiguous operations on finite automata
Cites Work
- Unambiguous finite automata over a unary alphabet
- An alternating hierarchy for finite automata
- On a structural property in the state complexity of projected regular languages
- State complexity of operations on two-way finite automata over a unary alphabet
- Partial orders on words, minimal elements of regular languages, and state complexity
- The state complexity of \(L^{2}\) and \(L^k\)
- State complexity of power
- A note on the reduction of two-way automata to one-way automata
- Lower bounds on the size of sweeping automata
- The state complexities of some basic operations on regular languages
- Converting two-way nondeterministic unary automata into simpler automata.
- Complementing two-way finite automata
- Optimal Simulations between Unary Automata
- Operations on Unambiguous Finite Automata
- Reversibility of Computations in Graph-Walking Automata
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- Two-Way Automata versus Logarithmic Space
- State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
- On the State Complexity of Operations on Two-Way Finite Automata
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- State-complexity of finite-state devices, state compressibility and incompressibility
- Mathematical Foundations of Computer Science 2005
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the state complexity of operations on two-way finite automata
