RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2009 Number 9, Pages 82–88 (Mi ivm3069)

This article is cited in 4 papers

Brief communications

Growth rates of power-free languages

A. M. Shur

Chair of Algebra and Discrete Mathematics, Ural State University, Ekaterinburg, Russia

Abstract: We propose a new fast algorithm for calculating the growth rate of complexity for regular languages. Based on this algorithm, we develop an efficient universal method of estimating the upper bound of the growth rates for power-free languages. 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.

Keywords: power-free languages, regular languages, combinatorial complexity, growth rate.

UDC: 519.16

Received: 26.12.2008


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2009, 53:9, 73–78

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024