Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/51038
Title: Complexity of problems concerning reset words for cyclic and Eulerian automata
Authors: Martyugin, Pavel
Issue Date: 2012
Citation: Martyugin P. Complexity of problems concerning reset words for cyclic and Eulerian automata / Pavel Martyugin // Theoretical Computer Science. — 2012. — Vol. 450. — P. 3-9.
Abstract: A word is called a reset word for a deterministic finite automaton if it maps all states of this automaton to one state. We consider two classes of automata: cyclic automata and Eulerian automata. For these classes we study the computational complexity of the following problems: does there exist a reset word of given length for a given automaton? what is the minimal length of the reset words for a given automaton? © 2012 Elsevier B.V. All rights reserved.
Keywords: AUTOMATA
COMPUTATIONAL COMPLEXITY
RESET WORDS
SYNCHRONIZATION
URI: http://hdl.handle.net/10995/51038
https://elar.urfu.ru/handle/10995/51038
Access: info:eu-repo/semantics/restrictedAccess
SCOPUS ID: 84863626448
WOS ID: 000307126400003
PURE ID: 1075470
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2012.04.022
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
10.1016j.tcs.2012.04.022_2012.pdf286,11 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.