On the State Complexity of Operations on Two-Way Finite Automata

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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