ISSN: 2310-757X
Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/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://elar.urfu.ru/handle/10995/111773 |
| Access: | info:eu-repo/semantics/openAccess |
| SCOPUS ID: | 61849155317 |
| WOS ID: | 000264989500039 |
| PURE ID: | 30126721 |
| ISSN: | 0166-218X |
| 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 | Size | Format | |
|---|---|---|---|---|
| 2-s2.0-61849155317.pdf | 545,54 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.