Finitely generated ideal languages and synchronizing automata

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/102498

Title:	Finitely generated ideal languages and synchronizing automata
Authors:	Gusev, V. V. Maslennikova, M. I. Pribavkina, E. V.
Issue Date:	2013
Publisher:	Springer Verlag
Citation:	Gusev V. V. Finitely generated ideal languages and synchronizing automata / V. V. Gusev, M. I. Maslennikova, E. V. Pribavkina. — DOI 10.1007/978-3-642-40579-2_16 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2013. — Vol. 8079 LNCS. — P. 143-153.
Abstract:	We study representations of ideal languages by means of strongly connected synchronizing automata. For every finitely generated ideal language L we construct such an automaton with at most 2 n states, where n is the maximal length of words in L. Our constructions are based on the De Bruijn graph. © 2013 Springer-Verlag Berlin Heidelberg.
Keywords:	IDEAL LANGUAGE RESET COMPLEXITY SYNCHRONIZING AUTOMATON SYNCHRONIZING WORD AUTOMATA THEORY COMBINATORIAL MATHEMATICS SYNCHRONIZATION DE BRUIJN GRAPHS IDEAL LANGUAGE RESET COMPLEXITY STRONGLY CONNECTED SYNCHRONIZING AUTOMATA SYNCHRONIZING WORDS ROBOTS
URI:	http://elar.urfu.ru/handle/10995/102498
Access:	info:eu-repo/semantics/openAccess
SCOPUS ID:	84885997125
PURE ID:	856428 4db711af-3de7-4e28-9dcb-0eb3f0051c51
ISSN:	3029743
ISBN:	9783642405785
DOI:	10.1007/978-3-642-40579-2_16
Appears in Collections:	Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Files in This Item:

File	Description	Size	Format
2-s2.0-84885997125.pdf		176,43 kB	Adobe PDF	View/Open