Nondeterministic operational complexity in subregular languages

DOI10.1016/J.TCS.2023.114075MaRDI QIDQ6093571zbMATH OpenOpenAlexFDO

Authors 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

unionstarconcatenationintersectioncomplementationnondeterministic finite automatareversaloperational state complexitystar-free languagesfinite languagesideal languagespower-separating languagesordered languagescomet languagessymmetric definite languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3473324 (Why is no real title available?)
• scientific article; zbMATH DE number 1156489 (Why is no real title available?)
• scientific article; zbMATH DE number 2068872 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1916664 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
• Complement on free and ideal languages
• Complement on prefix-free, suffix-free, and non-returning NFA languages
• Complexity in union-free regular languages
• Determination of finite automata accepting subregular languages
• Intersection and union of regular languages and state complexity
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Nondeterministic complexity in subclasses of convex languages
• Nondeterministic state complexity for suffix-free regular languages
• Nondeterministic state complexity of star-free languages
• On finite monoids having only trivial subgroups
• Operations on Permutation Automata
• Operations on automata with all states final
• Operations on subregular languages and nondeterministic state complexity
• Power, positive closure, and quotients on convex languages
• Power-separating regular languages
• Prefix-free languages: left and right quotient and reversal
• Roots of Star Events
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• State complexity bounds for the commutative closure of group languages
• State complexity of cyclic shift
• State complexity of power
• State complexity of projection on languages recognized by permutation automata and commuting letters
• State complexity of some operations on binary regular languages
• Ultimate-Definite and Symmetric-Definite Events and Automata

Cited in

(2)

• Nondeterministic complexity in subclasses of convex languages
• A Polynomial-Time Algorithm for Computing Finite-Makespan Controllable Sublanguages

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

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