Synchronizing monotonic automata / Ananichev DS,Volkov MV // THEORETICAL COMPUTER SCIENCE. - 2004. - V. 327, l. 3. - P. 225-239.

ISSN/EISSN:

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

Type:

Article; Proceedings Paper

Abstract:

We show that if the state set Q of a synchronizing automaton A = admits a linear order such that for each letter a is an element of Z the transformation delta(\_, a) of Q preserves this order, then A possesses a reset word of length \textbackslash{}Q\textbackslash{} - 1. We also consider two natural generalizations of the notion of a reset word and provide for them results of a similar flavour. (C) 2004 Elsevier B.V. All rights reserved.

Author keywords:

synchronizing automata; order preserving transformation; monotonic automata; rank of a word; interval rank of a word COMPUTING MACHINE

DOI:

10.1016/j.tcs.2004.03.068

Web of Science ID:

ISI:000224865300002

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

Другие поля

Поле	Значение
Month	NOV 2
Note	7th International Conference on Developments in Language Theory, SZEGED, HUNGARY, JUL 07-11, 2003
Organization	Univ Szeged, Dept Informat; Minist Educ Hungary; Fund Szeged; Hewlett-Packard Hungary Ltd
Publisher	ELSEVIER SCIENCE BV
Address	PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Language	English
Keywords-Plus	COMPUTING MACHINE
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	dmitry.anamchev@usu.ru mikhail.volkov@usu.ru
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Number-of-Cited-References	13
Usage-Count-Since-2013	1
Journal-ISO	Theor. Comput. Sci.
Doc-Delivery-Number	867TM