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


68Q45 Formal languages and automata
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Expansion of 1/(exp(-x) - x) as exponential generating function.