Synchronizing generalized monotonic automata / Ananichev DS,Volkov M // THEORETICAL COMPUTER SCIENCE. - 2005. - V. 330, l. 1. - P. 3-13.

ISSN/EISSN:

0304-3975 / нет данных

Type:

Article

Abstract:

In an earlier paper. we have studied reset words for synchronizing automata whose States admit a stable linear order. Here we show that the same bound on the length of the shortest reset word persists for synchronizing automata satisfying much weaker stability restriction. This result supports our conjecture concerning the length of reset words for synchronizing automata accepting only star-free languages. (C) 2004 Elsevier B.V. All rights reserved.

Author keywords:

synchronizing automata; order-preserving transformation; monotonic automata; congruence on an automaton; generalized monotonic automata; rank of a word with respect to an automaton; rank of an automat FINITE AUTOMATA; SEQUENCES; MONOIDS

DOI:

10.1016/j.tcs.2004.09.006

Web of Science ID:

ISI:000226684900002

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

Другие поля

Поле	Значение
Month	JAN 31
Publisher	ELSEVIER SCIENCE BV
Address	PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Language	English
Keywords-Plus	FINITE AUTOMATA; SEQUENCES; MONOIDS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	Dmitry.Ananichev@usu.ru Mikhai1.Volkov@usu.ru
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Number-of-Cited-References	17
Usage-Count-Since-2013	6
Journal-ISO	Theor. Comput. Sci.
Doc-Delivery-Number	892YC