On the State Complexity of Operations on Two-Way Finite Automata
From MaRDI portal
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 some operations on binary regular languages
- State complexity of operations on two-way deterministic finite automata over a unary alphabet
- The state complexities of some basic operations on regular languages
Cites work
- Complementing two-way finite automata
- Halting space-bounded computations
- scientific article; zbMATH DE number 7354705 (Why is no real title available?)
- scientific article; zbMATH DE number 3353192 (Why is no real title available?)
- Mathematical Foundations of Computer Science 2005
- Nondeterminism and the size of two way finite automata
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- State complexity of power
- Succinct representation of regular languages by Boolean automata
- The state complexity of \(L^{2}\) and \(L^k\)
Cited in
(21)- Concatenation of inputs in a two-way automaton
- Alternation in two-way finite automata
- Descriptional complexity of regular languages
- Oblivious two-way finite automata: decidability and complexity
- On the length of shortest strings accepted by two-way finite automata
- Complementing two-way finite automata
- State complexity of Kleene-star operations on trees
- Oblivious two-way finite automata: decidability and complexity
- State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
- Descriptional complexity of input-driven pushdown automata
- Concatenation of Regular Languages and Descriptional Complexity
- State complexity of operations on two-way finite automata over a unary alphabet
- Two-way automata and length-preserving homomorphisms
- scientific article; zbMATH DE number 1452984 (Why is no real title available?)
- Sampling a two-way finite automaton
- Cellular automata: descriptional complexity and decidability
- On the state complexity of operations on two-way finite automata
- On the length of shortest strings accepted by two-way finite automata
- Minicomplexity
- State complexity of operations on two-way deterministic finite automata over a unary alphabet
- Concatenation of regular languages and descriptional complexity
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 Q3533031)
