Undecidability of state complexities using mirror images

DOI10.1007/978-3-642-31644-9_15MaRDI QIDQ3166954zbMATH OpenOpenAlexFDO

Authors 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

nondeterminismundecidabilityfinite automatonstate 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)

Recommendations

• Undecidability of state complexity
• Undecidability of the state complexity of composed regular operations
• Mirror images and schemes for the maximal complexity of nondeterminism
• The state complexities of some basic operations on regular languages
• On the state complexity of reversals of regular languages

Cites work

• scientific article; zbMATH DE number 572102 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Composition sequences for functions over a finite domain.
• Estimation of state complexity of combined operations
• Mirror images and schemes for the maximal complexity of nondeterminism
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• On the State Complexity of Combined Operations
• On the state complexity of reversals of regular languages
• State complexity of combined operations
• The state complexities of some basic operations on regular languages
• Undecidability of the state complexity of composed regular operations

Cited in

(3)

• Mirror images and schemes for the maximal complexity of nondeterminism
• Undecidability of the state complexity of composed regular operations
• Undecidability of state complexity

This page was built for publication: Undecidability of state complexities using mirror images

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