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