On the State Complexity of Operations on Two-Way Finite Automata
From MaRDI portal
Publication:3533031
DOI10.1007/978-3-540-85780-8_35zbMath1161.68540OpenAlexW1510604108WikidataQ57380791 ScholiaQ57380791MaRDI QIDQ3533031
Alexander Okhotin, Galina Jirásková
Publication date: 30 October 2008
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_35
Related Items (9)
State Complexity of Kleene-Star Operations on Trees ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Cellular Automata: Descriptional Complexity and Decidability ⋮ Concatenation of regular languages and descriptional complexity ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ On the state complexity of operations on two-way finite automata ⋮ State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ Descriptional complexity of regular languages
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- Halting space-bounded computations
- Succinct representation of regular languages by Boolean automata
- Complementing two-way finite automata
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- Nondeterminism and the size of two way finite automata
- 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
This page was built for publication: On the State Complexity of Operations on Two-Way Finite Automata
