Collapsing words vs. synchronizing words / Ananichev DS,Volkov MV // . - 2002. - V. 2295, l. . - P. 166-174.

ISSN/EISSN:

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

Type:

Article; Proceedings Paper

Abstract:

We investigate the relationships between two types of words that have recently arisen in studying ``black-box{''} versions of the famous Cerny problem on synchronizing automata. Considering the languages formed by words of each of these types, we verify that one of them is regular while the other is not, thus showing that the two notions in question are different. We also discuss certain open problems concerning words of minimum length in these languages.

Author keywords:

нет данных

DOI:

нет данных

Web of Science ID:

ISI:000181141300013

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

Другие поля

Поле	Значение
Editor	Kuich, W and Rozenberg, G and Salomaa, A
Booktitle	DEVELOPMENTS IN LANGUAGE THEORY
Series	LECTURE NOTES IN COMPUTER SCIENCE
Note	5th International Conference on Developments in Language Theory (DLT 2001), TECH UNIV WIEN, VIENNA, AUSTRIA, JUL 16-21, 2001
Publisher	SPRINGER-VERLAG BERLIN
Address	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
Language	English
ISBN	3-540-43453-4
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Artificial Intelligence; Computer Science, Theory \& Methods
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Number-of-Cited-References	13
Doc-Delivery-Number	BW19J