Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111146
Title: Comparing Complexity Functions of a Language and Its Extendable Part
Authors: Shur, A. M.
Issue Date: 2008
Publisher: EDP Sciences
Citation: Shur A. M. Comparing Complexity Functions of a Language and Its Extendable Part / A. M. Shur // RAIRO - Theoretical Informatics and Applications. — 2008. — Vol. 42. — Iss. 3. — P. 647-655.
Abstract: Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly. © 2008 EDP Sciences.
Keywords: (ALGORITHMIC) COMPLEXITY
COMPLEXITY FUNCTIONS
LINGUISTICS
URI: http://hdl.handle.net/10995/111146
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 44849090412
ISSN: 0988-3754
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

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


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