The Ranges of Accepting State Complexities of Languages Resulting from Some Operations

DOI10.1142/S0129054120420083zbMath1482.68126OpenAlexW3114524785MaRDI QIDQ5859667

Michal Hospodár, Markus Holzer

Publication date: 19 April 2021

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

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

zbMATH Keywords

permutationregular languagesquotientintersectiondescriptional complexityminimal automatadeterministic automatareversalsymmetric differencenondeterministic automataaccepting states

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Closure properties of subregular languages under operations ⋮ Operational union-complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversal of binary regular languages
• Finite automata and unary languages
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• State complexity of permutation on finite languages over a binary alphabet
• Descriptional complexity and operations -- two non-classical cases
• Magic numbers in the state hierarchy of finite automata
• Reversal on Regular Languages and Descriptional Complexity
• MAGIC NUMBERS AND TERNARY ALPHABET
• On the Number of Accepting States of Finite Automata
• Kleene Closure on Regular and Prefix-Free Languages
• Constructions for alternating finite automata^∗

This page was built for publication: The Ranges of Accepting State Complexities of Languages Resulting from Some Operations