Growth rates of complexity of power-free languages / Shur Arseny M. // THEORETICAL COMPUTER SCIENCE. - 2010. - V. 411, l. 34-36. - P. 3209-3223.

ISSN/EISSN:

0304-3975 / нет данных

Type:

Article

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. (C) 2010 Elsevier B.V. All rights reserved.

Author keywords:

Growth rate; Regular language; Power-free language; Finite antidictionary BINARY WORDS

DOI:

10.1016/j.tcs.2010.05.017

Web of Science ID:

ISI:000280276200017

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	JUL 17
Publisher	ELSEVIER SCIENCE BV
Address	PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Language	English
Keywords-Plus	BINARY WORDS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	aimsure@mail.ru
Number-of-Cited-References	24
Journal-ISO	Theor. Comput. Sci.
Doc-Delivery-Number	630MA