Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111144
Title: On the Growth Rates of Complexity of Threshold Languages
Authors: Shur, A. M.
Gorbunova, I. A.
Issue Date: 2010
Publisher: EDP Sciences
Citation: Shur A. M. On the Growth Rates of Complexity of Threshold Languages / A. M. Shur, I. A. Gorbunova // RAIRO - Theoretical Informatics and Applications. — 2010. — Vol. 44. — Iss. 1. — P. 175-192.
Abstract: Threshold languages, which are the (k/(k-1))+-free languages over k-letter alphabets with k ≥, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over k letters tends to a constant α̌ ≈ 1.242 as k tends to infinity. © 2010 EDP Sciences.
Keywords: COMBINATORIAL COMPLEXITY
DEJEAN'S CONJECTURE
GROWTH RATE
POWER-FREE LANGUAGES
THRESHOLD LANGUAGES
COMBINATORIAL COMPLEXITY
COMPUTER ASSISTED
FREE LANGUAGES
GROWTH PROPERTIES
QUERY LANGUAGES
LINGUISTICS
URI: http://hdl.handle.net/10995/111144
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 77249179671
ISSN: 0988-3754
metadata.dc.description.sponsorship: The authors heartly thank the referees for their valuable comments and remarks.
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-77249179671.pdf306,97 kBAdobe PDFView/Open


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