Nondeterministic state complexity of star-free languages

DOI10.1016/j.tcs.2012.04.028zbMath1278.68135MaRDI 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 complexity; nondeterministic finite automata; operational state complexity; star-free languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q19: Descriptive complexity and finite models

Related Items

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

Cites Work

• 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
• 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