Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111231
Title: Growth Rates of Complexity of Power-Free Languages
Authors: Shur, A. M.
Issue Date: 2010
Publisher: Elsevier BV
Citation: Shur A. M. Growth Rates of Complexity of Power-Free Languages / A. M. Shur // Theoretical Computer Science. — 2010. — Vol. 411. — Iss. 34-36. — P. 3209-3223.
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. © 2010 Elsevier B.V.
Keywords: FINITE ANTIDICTIONARY
GROWTH RATE
POWER-FREE LANGUAGE
REGULAR LANGUAGE
COMPUTER ASSISTED
FAST ALGORITHMS
FINITE ALPHABET
FREE LANGUAGES
POWER-FREE LANGUAGE
REGULAR LANGUAGES
SPACE AND TIME
UPPER BOUND
CONTEXT FREE LANGUAGES
GROWTH RATE
LINGUISTICS
QUERY LANGUAGES
URI: http://hdl.handle.net/10995/111231
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 77955413698
ISSN: 0304-3975
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-77955413698.pdf496,02 kBAdobe PDFView/Open


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