Nondeterministic state complexity of star-free languages

DOI10.1016/J.TCS.2012.04.028zbMATH Open1278.68135OpenAlexW2071992537MaRDI QIDQ442152FDOQ442152

Authors: Markus Holzer, Martin Kutrib, Katja Meckel 

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

Recommendations

• Nondeterministic state complexity of star-free languages
• QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
• Quotient complexity of star-free languages
• Star-complement-star on prefix-free languages
• Syntactic complexities of six classes of star-free languages
• Square, power, positive closure, and complementation on star-free languages
• Nondeterministic state complexity for suffix-free regular languages
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Syntactic complexities of some classes of star-free languages
• State complexity of basic operations on suffix-free regular languages

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)

Cites Work

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

Cited In (10)

• Operations on subregular languages and nondeterministic state complexity
• Expressive capacity of subregular expressions
• QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
• Concatenation-free languages
• Closure properties of subregular languages under operations
• Nondeterministic complexity in subclasses of convex languages
• Nondeterministic operational complexity in subregular languages
• The nondeterministic state complexity of the site-directed deletion language operation
• Expressive Capacity of Concatenation Freeness
• Nondeterminism growth and state complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442152)