×

zbMATH — the first resource for mathematics

The state complexity of star-complement-star. (English) Zbl 1370.68178
Yen, Hsu-Chun (ed.) et al., Developments in language theory. 16th international conference, DLT 2012, Taipei, Taiwan, August 14–17, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31652-4/pbk). Lecture Notes in Computer Science 7410, 380-391 (2012).
Summary: 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 \(\left( \, \overline{L^*} \, \right)^*\).
For the entire collection see [Zbl 1248.68052].

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI Link