Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102482
Title: Approximating the Minimum Length of Synchronizing Words Is Hard
Authors: Berlinkov, M. V.
Issue Date: 2014
Citation: Berlinkov M. V. Approximating the Minimum Length of Synchronizing Words Is Hard / M. V. Berlinkov. — DOI 10.1007/s00224-013-9511-y // Theory of Computing Systems. — 2014. — Vol. 54. — Iss. 2. — P. 211-223.
Abstract: We prove that, unless P=NP, no polynomial-time algorithm can approximate the minimum length of reset words for a given synchronizing automaton within a constant factor. © 2013 Springer Science+Business Media New York.
Keywords: POLYNOMIAL-TIME APPROXIMATION
SYNCHRONIZING AUTOMATA
URI: http://hdl.handle.net/10995/102482
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84895057541
PURE ID: 336062
2a1af4f8-c31b-4773-a54e-12357bdc2b1b
ISSN: 14324350
DOI: 10.1007/s00224-013-9511-y
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84895057541.pdf197,3 kBAdobe PDFView/Open


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