Undecidability of State Complexities Using Mirror Images
From MaRDI portal
Publication:3166954
DOI10.1007/978-3-642-31644-9_15zbMath1367.68177MaRDI QIDQ3166954
Publication date: 1 November 2012
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-31644-9_15
undecidability; finite automaton; nondeterminism; state complexity; mirror image; eexponential polynomials
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
03B25: Decidability of theories and sets of sentences
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the state complexity of reversals of regular languages
- The state complexities of some basic operations on regular languages
- Composition sequences for functions over a finite domain.
- Estimation of state complexity of combined operations
- State complexity of combined operations
- Undecidability of the State Complexity of Composed Regular Operations
- ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
- On the State Complexity of Combined Operations