Growth Rates of Complexity of Power-Free Languages

Abstract

We present a new fast algorithm for calculating the growth rate of complexity for regular languages. Using this algorithm we develop a space and time efficient method to approximate growth rates of complexity of arbitrary power-free languages over finite alphabets. Through extensive computer-assisted studies we sufficiently improve all known upper bounds for growth rates of such languages, obtain a lot of new bounds and discover some general regularities. © 2010 Elsevier B.V.