Power, positive closure, and quotients on convex languages

DOI10.1016/j.tcs.2021.02.002zbMath1504.68103OpenAlexW3127462027MaRDI QIDQ2029485

Michal Hospodár

Publication date: 3 June 2021

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

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

zbMATH Keywords

powerdeterministic finite automatanondeterministic finite automataoperational state complexityleft quotientright quotientclosed languagesconvex languagesideal languagespositive closure

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (4)

Nondeterministic operational complexity in subregular languages ⋮ Operations on Boolean and Alternating Finite Automata ⋮ Closure properties of subregular languages under operations ⋮ Operations on subregular languages and nondeterministic state complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversal of binary regular languages
• Prefix-free languages: left and right quotient and reversal
• State complexity of basic operations on suffix-free regular languages
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• Complexity of proper suffix-convex regular languages
• Quotient complexity of closed languages
• Quotient complexity of ideal languages
• Descriptional complexity of power and positive closure on convex languages
• NFA-to-DFA trade-off for regular operations
• Nondeterministic complexity in subclasses of convex languages
• Nondeterministic complexity of operations on free and convex languages
• Nondeterministic Complexity of Operations on Closed and Ideal Languages
• COMPLEXITY IN UNION-FREE REGULAR LANGUAGES
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Kleene Closure on Regular and Prefix-Free Languages
• Complexity in Convex Languages
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Quotient Complexity of Bifix-, Factor-, and Subword-free Regular Language
• INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES
• Complement on Prefix-Free, Suffix-Free, and Non-Returning NFA Languages
• Square on Ideal, Closed and Free Languages
• Complement on Free and Ideal Languages
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Complexity of proper prefix-convex regular languages
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity

This page was built for publication: Power, positive closure, and quotients on convex languages