Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/51322
Title: Growth properties of power-free languages
Authors: Shur, Arseny M.
Issue Date: 2012
Citation: Shur A. M. Growth properties of power-free languages / Arseny M. Shur // Computer Science Review. — 2012. — Vol. 6. — № 5-6. — P. 187-208.
Abstract: The aim of this paper is to survey the area formed by the intersection of two popular lines of research in formal language theory. The first line, originated by Thue in 1906, concerns repetition-free words and languages. The second line is the study of growth functions for words and languages; it can be traced back to the classical papers by Morse and Hedlund on symbolic dynamics (1938, 1940). Growth functions of repetition-free languages have been investigated since the 1980's. Most of the results are obtained for power-free languages, but some ideas can be applied for languages avoiding patterns and Abelian-power-free languages as well. In this paper, we present key contributions to the area, its state of the art, and conjectures that suggest answers to some natural unsolved problems. Also, we pay much attention to the tools and techniques that made the progress in the area possible. © 2012 Elsevier Inc.
Keywords: ASYMPTOTIC PROPERTIES
COMBINATORIAL COMPLEXITY
GROWTH RATE
POWER-FREE LANGUAGE
REPETITION-FREE LANGUAGE
URI: http://hdl.handle.net/10995/51322
https://elar.urfu.ru/handle/10995/51322
Access: info:eu-repo/semantics/restrictedAccess
SCOPUS ID: 84870390868
WOS ID: 000219779800001
PURE ID: 1071557
ISSN: 1574-0137
DOI: 10.1016/j.cosrev.2012.09.001
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
10.1016j.cosrev.2012.09.001_2012.pdf540,42 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.