Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102294
Title: On two algorithmic problems about synchronizing automata (Short Paper)
Authors: Berlinkov, M. V.
Issue Date: 2014
Publisher: Springer Verlag
Citation: Berlinkov M. V. On two algorithmic problems about synchronizing automata (Short Paper) / M. V. Berlinkov. — DOI 10.1007/978-3-319-09698-8_6 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2014. — Vol. 8633 LNCS. — P. 61-67.
Abstract: Under the assumption P=NP, we prove that two natural problems from the theory of synchronizing automata cannot be solved in polynomial time. The first problem is to decide whether a given reachable partial automaton is synchronizing. The second one is, given an n-state binary complete synchronizing automaton, to compute its reset threshold within performance ratio less than d ln (n) for a specific constant d>0. © 2014 Springer International Publishing Switzerland.
Keywords: ALGORITHMS
POLYNOMIAL APPROXIMATION
ALGORITHMIC PROBLEMS
PARTIAL AUTOMATON
PERFORMANCE RATIO
POLYNOMIAL-TIME
SYNCHRONIZING AUTOMATA
AUTOMATA THEORY
URI: http://hdl.handle.net/10995/102294
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84958541625
PURE ID: 367054
3e49a695-6032-4799-a303-0f91cd3bd7c8
ISSN: 3029743
ISBN: 9783319096971
DOI: 10.1007/978-3-319-09698-8_6
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84958541625.pdf132,23 kBAdobe PDFView/Open


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