LANGUAGES WITH A FINITE ANTIDICTIONARY: SOME GROWTH QUESTIONS / Shur Arseny M. // INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - 2014. - V. 25, l. 8, SI. - P. 937-953.

ISSN/EISSN:

0129-0541 / 1793-6373

Type:

Article

Abstract:

We study FAD-languages, which are regular languages defined by finite sets of forbidden factors, together with their ``canonical{''} recognizing automata. we are mainly interested in the possible asymptotic orders of growth for such languages. We analyze certain simplifications of sets of forbidden factors and show that they ``almost{''} preserve the canonical automata. Using this result and structural properties of canonical automata, we describe an algorithm that effectively lists all canonical automata having a sink strong component isomorphic to a given digraph, or report:, that no such automata exist. This algorithm can be used, in particular, to prove the existence of a FAD-language over a given alphabet with a given exponential growth rate. On the other hand, we give an example showing that the algorithm cannot prove non-existence of a FAD-language having a given growth rate. Finally, we provide some examples of canonical automata with a nontrivial condensation graph and of FAD-languages with a ``complex{''} order of growth.

Author keywords:

Finite antidictionary; regular language; combinatorial complexity; growth rate

DOI:

10.1142/S0129054114400164

Web of Science ID:

ISI:000350333300002

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

—

Другие поля

Поле	Значение
Month	DEC
Publisher	WORLD SCIENTIFIC PUBL CO PTE LTD
Address	5 TOH TUCK LINK, SINGAPORE 596224, SINGAPORE
Language	English
EISSN	1793-6373
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	arseny.shur@usu.ru
Number-of-Cited-References	13
Journal-ISO	Int. J. Found. Comput. Sci.
Doc-Delivery-Number	CC4OS