Descriptional Complexity of the Forever Operator

DOI10.1142/S0129054119400069zbMath1415.68130OpenAlexW2920638727MaRDI QIDQ5384434

Galina Jirásková, Peter Mlynárčik, Michal Hospodár

Publication date: 24 June 2019

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

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

zbMATH Keywords

regular languagestrade-offminimal automatadeterministic automatanondeterministic automataBoolean automataforever operator

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal simulation of self-verifying automata by deterministic automata
• On equations for regular languages, finite automata, and sequential networks
• A lower bound technique for the size of nondeterministic finite automata
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• On the expressive power of temporal logic
• The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic
• On the State Complexity of the Shuffle of Regular Languages
• Descriptional Complexity of Operations on Alternating and Boolean Automata
• COMPLEXITY IN UNION-FREE REGULAR LANGUAGES
• Constructions for alternating finite automata^∗
• On Dedekind's Problem: The Number of Isotone Boolean Functions. II
• Mathematical Foundations of Computer Science 2005
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata