The state complexity of star-complement-star

DOI10.1007/978-3-642-31653-1_34MaRDI QIDQ3167511zbMATH OpenOpenAlexFDO

Authors Galina Jirásková, Jeffrey Shallit

Publication date 2 November 2012

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.5353

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We resolve an open question by determining matching (asymptotic) upper and lower bounds on the state complexity of the operation that sends a language L to (c(L*))*, where c() denotes complement.

Recommendations

• Star-complement-star on prefix-free languages
• The exact complexity of star-complement-star
• On the state complexity of star of union and star of intersection
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• Square, power, positive closure, and complementation on star-free languages

Cited in

(9)

• The exact complexity of star-complement-star
• On the boundary of regular languages
• On the state complexity of star of union and star of intersection
• The Average State Complexity of the Star of a Finite Set of Words Is Linear
• Algebraic and combinatorial tools for state complexity: application to the star-xor problem
• Kuratowski Algebras Generated by Prefix-, Suffix-, Factor-, and Subword-Free Languages Under Star and Complementation
• Star-complement-star on prefix-free languages
• State complexity of deletion and bipolar deletion
• Operational state complexity revisited: the contribution of monsters and modifiers

This page was built for publication: The state complexity of star-complement-star

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