Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111370
Title: Approximating the Minimum Length of Synchronizing Words is Hard
Authors: Berlinkov, M. V.
Issue Date: 2010
Publisher: Springer Berlin Heidelberg
Citation: Berlinkov M. V. Approximating the Minimum Length of Synchronizing Words is Hard / M. V. Berlinkov. — DOI 10.14704/WEB/V18SI04/WEB18172 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2010. — Vol. 6072 LNCS. — P. 37-47.
Abstract: We prove that, unless P = NP, no polynomial-time algorithm can approximate the minimum length of synchronizing words for a given synchronizing automaton within a constant factor. © 2010 Springer-Verlag.
Keywords: CONSTANT FACTORS
POLYNOMIAL-TIME ALGORITHMS
SYNCHRONIZING AUTOMATA
COMPUTATION THEORY
URI: http://hdl.handle.net/10995/111370
Access: info:eu-repo/semantics/openAccess
Conference name: 5th International Computer Science Symposium in Russia, CSR 2010
Conference date: 16 June 2010 through 20 June 2010
SCOPUS ID: 77954618795
ISSN: 0302-9743
ISBN: 3642131816
9783642131813
DOI: 10.14704/WEB/V18SI04/WEB18172
metadata.dc.description.sponsorship: The author acknowledges support from the Federal Education Agency of Russia, grant 2.1.1/3537, and from the Russian Foundation for Basic Research, grant 09-01-12142.
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

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


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