Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111773
Title: On intermediate Factorial Languages
Authors: Shur, A. M.
Issue Date: 2009
Publisher: Elsevier BV
Citation: Shur A. M. On intermediate Factorial Languages / A. M. Shur // Discrete Applied Mathematics. — 2009. — Vol. 157. — Iss. 7. — P. 1669-1675.
Abstract: We prove that factorial languages defined over non-trivial finite alphabets under some natural conditions have intermediate complexity functions, i.e., the number of words in such a language grows faster than any polynomial but slower than any exponential function. © 2008 Elsevier B.V. All rights reserved.
Keywords: COMBINATORIAL COMPLEXITY
FACTORIAL LANGUAGES
INTERMEDIATE COMPLEXITY
WEB-LIKE AUTOMATA
QUERY LANGUAGES
TRANSLATION (LANGUAGES)
COMBINATORIAL COMPLEXITY
EXPONENTIAL FUNCTIONS
FACTORIAL LANGUAGES
FINITE ALPHABETS
INTERMEDIATE COMPLEXITY
NATURAL CONDITIONS
NON-TRIVIAL
WEB-LIKE AUTOMATA
LINGUISTICS
URI: http://hdl.handle.net/10995/111773
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 61849155317
ISSN: 0166-218X
metadata.dc.description.sponsorship: The author is grateful to J. Karhumäki for valuable remarks on the paper. The author was supported by the Federal Science and Innovation Agency of Russia under the grants RI-111. 0/002/075 and 2227.2003.01, by the Russian Foundation for Basic Research under the grant 05-01-00540, and by the Federal Education Agency of Russia under the grant 49123.
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-61849155317.pdf545,54 kBAdobe PDFView/Open


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