Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102436
Title: Complexity of checking whether two automata are synchronized by the same language
Authors: Maslennikova, M.
Issue Date: 2014
Publisher: Springer Verlag
Citation: Maslennikova M. Complexity of checking whether two automata are synchronized by the same language / M. Maslennikova. — DOI 10.1007/978-3-319-09704-6_27 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2014. — Vol. 8614 LNCS. — P. 306-317.
Abstract: A deterministic finite automaton A is said to be synchronizing if it has a reset word, i.e. a word that brings all states of the automaton A to a particular one. We prove that it is a PSPACE-complete problem to check whether the language of reset words for a given automaton coincides with the language of reset words for some particular automaton. © 2014 Springer International Publishing.
Keywords: IDEAL LANGUAGE
PSPACE-COMPLETENESS
RESET COMPLEXITY
RESET WORD
SYNCHRONIZING AUTOMATON
DISPERSION COMPENSATION
SYNCHRONIZATION
IDEAL LANGUAGE
PSPACE COMPLETENESS
RESET COMPLEXITY
RESET WORDS
SYNCHRONIZING AUTOMATA
AUTOMATA THEORY
URI: http://hdl.handle.net/10995/102436
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84905392482
PURE ID: 540101
4a0afc97-f005-4fc2-bf51-0df6b234ac5c
ISSN: 3029743
ISBN: 9783319097039
DOI: 10.1007/978-3-319-09704-6_27
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84905392482.pdf176,33 kBAdobe PDFView/Open


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