Open problems about regular languages, 35 years later

DOI10.1142/9789813148208_0007MaRDI QIDQ4683188zbMATH OpenOpenAlexFDO

Authors Jean-Éric Pin

Publication date 20 September 2018

Published in The Role of Theory in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/9789813148208_0007

zbMATH Keywords

dot-depth hierarchyfinite semigroupsgroup complexitylimitedness problemoptimality of prefix codesregular languagesregularity of non-counting classesrestricted star heightstar heightstar removal

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Recommendations

• Distance desert automata and the star height problem
• Some results on the generalized star-height problem
• scientific article; zbMATH DE number 3874645
• scientific article; zbMATH DE number 5218131
• Regular languages of star height one

Cited in

(20)

• Rational languages and the Burnside problem
• Algorithms for determining relative star height and star height
• Some results on the generalized star-height problem
• Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups
• Generic results for concatenation hierarchies
• Stamina: stabilisation monoids in automata theory
• Concatenation hierarchies: new bottle, old wine
• Automata theory: Its past and future
• On the complexity of the relative inclusion star height problem
• scientific article; zbMATH DE number 177805 (Why is no real title available?)
• scientific article; zbMATH DE number 1134630 (Why is no real title available?)
• Star height via games
• The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words
• scientific article; zbMATH DE number 2201362 (Why is no real title available?)
• scientific article; zbMATH DE number 5218131 (Why is no real title available?)
• Regular expressions: new results and open problems
• Open problems related to palindrome recognition: are there open problems related to palindrome recognition?
• Monadic monadic second order logic
• Short synchronizing words for random automata
• Seventy years of algebraic, logical, and topological methods for regular languages

This page was built for publication: Open problems about regular languages, 35 years later

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