Nondeterministic operational complexity in subregular languages

DOI10.1016/j.tcs.2023.114075OpenAlexW4384817627MaRDI QIDQ6093571

Michal Hospodár, Viktor Olejár

Publication date: 7 September 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114075

zbMATH Keywords

complementationstarintersectionfinite languagesunionconcatenationreversalnondeterministic finite automataoperational state complexitystar-free languagesideal languagespower-separating languagesordered languagescomet languagessymmetric definite languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nondeterministic state complexity of star-free languages
• State complexity of projection on languages recognized by permutation automata and commuting letters
• Prefix-free languages: left and right quotient and reversal
• State complexity of power
• Intersection and union of regular languages and state complexity
• State complexity of some operations on binary regular languages
• Power, positive closure, and quotients on convex languages
• State complexity bounds for the commutative closure of group languages
• Operations on subregular languages and nondeterministic state complexity
• Determination of finite automata accepting subregular languages
• Nondeterministic complexity in subclasses of convex languages
• COMPLEXITY IN UNION-FREE REGULAR LANGUAGES
• State complexity of cyclic shift
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Power-separating regular languages
• Operations on Permutation Automata
• Ultimate-Definite and Symmetric-Definite Events and Automata
• On finite monoids having only trivial subgroups
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• Complement on Prefix-Free, Suffix-Free, and Non-Returning NFA Languages
• Complement on Free and Ideal Languages
• Roots of Star Events
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity

This page was built for publication: Nondeterministic operational complexity in subregular languages