On the state complexity of operations on two-way finite automata

DOI10.1016/J.IC.2016.12.007zbMATH Open1371.68153OpenAlexW2560045680MaRDI QIDQ515574FDOQ515574

Authors Galina Jirásková, Alexander Okhotin

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

zbMATH Keywords

descriptional complexityfinite-state automatadeterministic automatastate complexitytwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the State Complexity of Operations on Two-Way Finite Automata
• State complexity of operations on two-way finite automata over a unary alphabet
• State complexity of operations on two-way deterministic finite automata over a unary alphabet
• State complexity of some operations on binary regular languages
• The state complexity of two combined operations: star of catenation and star of reversal

Cites work

• scientific article; zbMATH DE number 3241282 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• A note on the reduction of two-way automata to one-way automata
• An alternating hierarchy for finite automata
• Complementing two-way finite automata
• Converting two-way nondeterministic unary automata into simpler automata.
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• Lower bounds on the size of sweeping automata
• Mathematical Foundations of Computer Science 2005
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On a structural property in the state complexity of projected regular languages
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• On the State Complexity of Operations on Two-Way Finite Automata
• Operations on Unambiguous Finite Automata
• Optimal simulations between unary automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Reversibility of computations in graph-walking automata
• State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
• State complexity of operations on two-way finite automata over a unary alphabet
• State complexity of power
• State-complexity of finite-state devices, state compressibility and incompressibility
• The state complexities of some basic operations on regular languages
• The state complexity of \(L^{2}\) and \(L^k\)
• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
• Two-Way Automata versus Logarithmic Space
• Unambiguous finite automata over a unary alphabet

Cited in

(12)

• Performing regular operations with 1-limited 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
• State complexity of operations on two-way deterministic finite automata over a unary alphabet
• State complexity of operations on two-way finite automata over a unary alphabet
• Operational complexity: NFA-to-DFA trade-off
• Performing regular operations with 1-limited automata
• Homomorphisms and inverse homomorphisms on graph-walking automata
• State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
• State complexity of unambiguous operations on finite automata
• On the State Complexity of Operations on Two-Way Finite Automata
• Homomorphisms on graph-walking automata

This page was built for publication: On the state complexity of operations on two-way finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515574)