Comparing complexity functions of a language and its extendable part / Shur Arseny M. // RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS. - 2008. - V. 42, l. 3. - P. 647-655.

ISSN/EISSN:

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

Type:

Article; Proceedings Paper

Abstract:

Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.

Author keywords:

нет данных

DOI:

10.1051/ita:2008021

Web of Science ID:

ISI:000256464100015

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

—

Другие поля

Поле	Значение
Month	JUL-SEP
Note	11th Mons Days of Theoretical Computer Science, Rennes, FRANCE, AUG 31-SEP 01, 2006
Organization	Assoc Francaise Informat Fondament; European Sci Fdn, Auto Matha Program; City Rennes; Fdn Michel Metivier; GDR Algorithmis; CNRE, Langage \& Programmat; Lab IRISA; Minist Enseignements; Super \& Recherche; Reg Bretagne; Univ Rennes 1
Publisher	CAMBRIDGE UNIV PRESS
Address	32 AVENUE OF THE AMERICAS, NEW YORK, NY 10013-2473 USA
Language	English
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Information Systems
Author-Email	Arseny.Shur@usu.ru
Number-of-Cited-References	11
Journal-ISO	Rairo-Theor. Inform. Appl.
Doc-Delivery-Number	309MI