Nondeterministic operational complexity in subregular languages

DOI10.1016/J.TCS.2023.114075OpenAlexW4384817627MaRDI QIDQ6093571FDOQ6093571

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

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

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)