Nondeterministic state complexity of star-free languages

DOI10.1016/j.tcs.2012.04.028zbMath1278.68135OpenAlexW2071992537MaRDI QIDQ442152

Markus Holzer, Katja Meckel, Martin Kutrib

Publication date: 9 August 2012

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

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

zbMATH Keywords

descriptional complexitynondeterministic finite automataoperational state complexitystar-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items (7)

Expressive Capacity of Concatenation Freeness ⋮ Nondeterministic operational complexity in subregular languages ⋮ Expressive capacity of subregular expressions ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Closure properties of subregular languages under operations ⋮ Operations on subregular languages and nondeterministic state complexity ⋮ Concatenation-free languages

Cites Work

• Descriptional and computational complexity of finite automata -- a survey
• A lower bound technique for the size of nondeterministic finite automata
• Finite automata and unary languages
• Intersection and union of regular languages and state complexity
• Quotient complexity of closed languages
• State complexity of some operations on binary regular languages
• Determination of finite automata accepting subregular languages
• Optimal Simulations between Unary Automata
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• Complexity in Union-Free Regular Languages
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Power-separating regular languages
• On finite monoids having only trivial subgroups
• Roots of Star Events
• On Decompositions of Regular Events
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Nondeterministic state complexity of star-free languages