Undecidability of the state complexity of composed regular operations

DOI10.1007/978-3-642-21254-3_39MaRDI QIDQ3004607zbMATH OpenOpenAlexFDO

Authors Kai Salomaa, Arto Salomaa, Sheng Yu

Publication date 3 June 2011

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21254-3_39

zbMATH Keywords

composition of operationsfinite deterministic automatonregularity-preserving operationsstate complexityundecidability

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Undecidability of state complexity
• State complexity of four combined operations composed of union, intersection, star and reversal
• Undecidability of state complexities using mirror images
• The state complexities of some basic operations on regular languages
• State complexity of combined operations with union, intersection, star and reversal

Cited in

(11)

• State complexity of unique rational operations
• Undecidability of state complexity
• State complexity of Kleene-star operations on trees
• Undecidability of state complexities using mirror images
• State complexity of star of union and square of union on \textit{k} regular languages
• State complexity of union and intersection of star on \(k\) regular languages
• State complexity of the concatenation of regular tree languages
• State complexity of combined operations with two basic operations
• scientific article; zbMATH DE number 6855103 (Why is no real title available?)
• State complexity of union and intersection of square and reversal on \(k\) regular languages
• Lower bounds for the size of deterministic unranked tree automata

This page was built for publication: Undecidability of the state complexity of composed regular operations

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