Factorial languages of low combinatorial complexity / Shur Arseny M. // . - 2006. - V. 4036, l. . - P. 397-407.

ISSN/EISSN:

0302-9743 / нет данных

Type:

Article; Proceedings Paper

Abstract:

The complexity (or growth) functions of some languages are studied over arbitrary nontrivial alphabets. The attention is focused on the languages determined by a finite set of forbidden factors, called an antidictionary. Let m be a nonnegative integer. Examples of languages of complexity Theta(n(m)) with finite (and even symmetric finite) anti-dictionaries are given. For any integer s such that 1 <= s <= m, a sequence of languages with finite antidictionaries and Theta(n(m)) complexities, converging to the language of Theta(n(s)) complexity, is exhibited. Some languages of intermediate complexity are shown to be the limits of sequences of languages with finite antidictionaries and polynomial complexities.

Author keywords:

WORDS

DOI:

нет данных

Web of Science ID:

ISI:000239454100036

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

—

Другие поля

Поле	Значение
Editor	Ibarra, OH and Dang, Z
Booktitle	DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS
Series	LECTURE NOTES IN COMPUTER SCIENCE
Note	10th International Conference on Developments in Language Theory, Univ Calif Santa Barbara, Santa Barbara, CA, JUN 26-29, 2006
Organization	Univ Calif Santa Barbara, Comp Sci Dept; Univ Calif Santa Barbara, Coll Engn; Univ Calif Santa Barbara, Grad Div; Ask com; Citrix; Google
Publisher	SPRINGER-VERLAG BERLIN
Address	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
Language	English
ISBN	3-540-35428-X
Keywords-Plus	WORDS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	Arseny.Shur@usu.ru
Number-of-Cited-References	7
Usage-Count-Since-2013	1
Doc-Delivery-Number	BET64