zbMATH — the first resource for mathematics

Combinatorial complexity of regular languages. (English) Zbl 1142.68428
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 289-301 (2008).
Summary: We study combinatorial complexity (or counting function) of regular languages, describing these functions in three ways. First, we classify all possible asymptotically tight upper bounds of these functions up to a multiplicative constant, relating each particular bound to certain parameters of recognizing automata. Second, we show that combinatorial complexity equals, up to an exponentially small term, to a function constructed from a finite number of polynomials and exponentials. Third, we describe oscillations of combinatorial complexity for factorial, prefix-closed, and arbitrary regular languages. Finally, we construct a fast algorithm for calculating the growth rate of complexity for regular languages, and apply this algorithm to approximate growth rates of complexity of power-free languages, improving all known upper bounds for growth rates of such languages.
For the entire collection see [Zbl 1136.68005].

68Q45 Formal languages and automata
68R15 Combinatorics on words
PDF BibTeX Cite
Full Text: DOI