|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Computing the Growth of the Number of Overlap-Free Words with Spectra of Matricesстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Дата последнего поиска статьи во внешних источниках: 19 июля 2013 г.
- Авторы: Jungers R.M., Protasov V.Yu, Blondel V.D.
- Сборник: LATIN 2008: Theoretical Informatics, 8th Latin American Symposium, Buzios, Brazil, April 7-11, 2008, Proceedings
- Серия: Lecture Notes in Computer Science
- Том: 4957
- Год издания: 2008
- Издательство: SPRINGER
- Местоположение издательства: VAN GODEWIJCKSTRAAT 30, DORDRECHT, NETHERLANDS, 3311GZ
- Первая страница: 84
- Последняя страница: 93
- DOI: 10.1007/978-3-540-78773-0_8
- Аннотация: Overlap-free words are words over the alphabet A = {a, b} that do not contain factors of the form xvxvx, where x ∈ A and v ∈ A *. We analyze the asymptotic growth of the number u n of overlap-free words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of u n in terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of one set of matrices of dimension 20. Using these descriptions we provide estimates of the rates of growth that are within 0.4% and 0.03 % of their exact value. The best previously known bounds were within 11% and 3% respectively. We prove that u n actually has the same growth for “almost all” n. This “average” growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it.
- Добавил в систему: Протасов Владимир Юрьевич