Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111961
Title: On Pansiot Words Avoiding 3-Repetitions
Authors: Gorbunova, I. A.
Shur, A. M.
Issue Date: 2011
Publisher: Open Publishing Association
Open Publishing Association
Citation: Gorbunova I. A. On Pansiot Words Avoiding 3-Repetitions / I. A. Gorbunova, A. M. Shur. — DOI 10.1038/s41598-022-07450-7 // Electronic Proceedings in Theoretical Computer Science, EPTCS. — 2011. — Vol. 63. — P. 138-146.
Abstract: The recently confirmed Dejean?fs conjecture about the threshold between avoidable and unavoidable powers of words gave rise to interesting and challenging problems on the structure and growth of threshold words. Over any finite alphabet with k ≥ 5 letters, Pansiot words avoiding 3-repetitions forma regular language, which is a rather small superset of the set of all thresholdwords. Using cylindric and 2-dimensionalwords, we prove that, as k approaches infinity, the growth rates of complexity for these regular languages tend to the growth rate of complexity of some ternary 2-dimensional language. The numerical estimate of this growth rate is ≈ 1.2421. © 2011 I. A. Gorbunova, A. M. Shur.
Keywords: COMPUTATIONAL METHODS
COMPUTER SCIENCE
FINITE ALPHABET
CONTEXT FREE LANGUAGES
URI: http://hdl.handle.net/10995/111961
Access: info:eu-repo/semantics/openAccess
Conference name: 8th International Conference Words, WORDS 2011
Conference date: 12 September 2011 through 16 September 2011
SCOPUS ID: 84870392115
ISSN: 2075-2180
DOI: 10.1038/s41598-022-07450-7
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84870392115.pdf177,58 kBAdobe PDFView/Open


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