On intermediate factorial languages / Shur Arseny M. // DISCRETE APPLIED MATHEMATICS. - 2009. - V. 157, l. 7. - P. 1669-1675.

ISSN/EISSN:

0166-218X / нет данных

Type:

Article

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. (C) 2008 Elsevier B.V. All rights reserved.

Author keywords:

Factorial languages; Combinatorial complexity; Intermediate complexity; Web-like automata

DOI:

10.1016/j.dam.2008.09.007

Web of Science ID:

ISI:000264989500039

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	APR 6
Publisher	ELSEVIER SCIENCE BV
Address	PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Language	English
Research-Areas	Mathematics
Web-of-Science-Categories	Mathematics, Applied
Author-Email	Arseny.Shur@usu.ru
Funding-Acknowledgement	Federal Science and Innovation Agency of Russia {[}RI-111.0/002/075, 2227.2003.01]; Russian Foundation for Basic Research {[}05-01-00540]; Federal Education Agency of Russia {[}49123]
Funding-Text	The author is grateful to J. Karhumaki 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.
Number-of-Cited-References	5
Usage-Count-Since-2013	1
Journal-ISO	Discret Appl. Math.
Doc-Delivery-Number	430LB