Undecidability of State Complexities Using Mirror Images

DOI10.1007/978-3-642-31644-9_15zbMath1367.68177OpenAlexW302452608MaRDI QIDQ3166954

Arto Salomaa

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

zbMATH Keywords

undecidabilityfinite automatonnondeterminismstate complexitymirror imageeexponential polynomials

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items (1)

Undecidability of state complexity

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

This page was built for publication: Undecidability of State Complexities Using Mirror Images