The Range of State Complexities of Languages Resulting from the Cascade Product — The Unary Case

DOI10.1142/s0129054123430049OpenAlexW4327972292MaRDI QIDQ6070753

Markus Holzer, Christian Rauch

Publication date: 24 November 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

cascade productdescriptional complexitymagic numbers

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Unnamed Item
• The range of state complexities of languages resulting from the cascade product -- the general case (extended abstract)
• Direct or cascade product of pushdown automata
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• The range of state complexities of languages resulting from the cut operation
• Magic numbers in the state hierarchy of finite automata
• Kleene Star on Unary Regular Languages
• MAGIC NUMBERS AND TERNARY ALPHABET
• On the Square of Regular Languages
• On the Krohn-Rhodes Cascaded Decomposition Theorem
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines