POLYNOMIAL LANGUAGES WITH FINITE ANTIDICTIONARIES / Shur Arseny M. // RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS. - 2009. - V. 43, l. 2. - P. 269-279.

ISSN/EISSN:

0988-3754 / нет данных

Type:

Article

Abstract:

We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.

Author keywords:

Regular language; finite antidictionary; combinatorial complexity; wed-like automaton WORDS

DOI:

10.1051/ita:2008028

Web of Science ID:

ISI:000264879300007

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

—

Другие поля

Поле	Значение
Month	APR-JUN
Publisher	EDP SCIENCES S A
Address	17, AVE DU HOGGAR, PA COURTABOEUF, BP 112, F-91944 LES ULIS CEDEX A, FRANCE
Language	English
Keywords-Plus	WORDS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Information Systems
Author-Email	Arseny.Shur@usu.ru
Number-of-Cited-References	6
Journal-ISO	Rairo-Theor. Inform. Appl.
Doc-Delivery-Number	428VK