Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102482
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBerlinkov, M. V.en
dc.date.accessioned2021-08-31T15:03:48Z-
dc.date.available2021-08-31T15:03:48Z-
dc.date.issued2014-
dc.identifier.citationBerlinkov 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.en
dc.identifier.issn14324350-
dc.identifier.otherFinal2
dc.identifier.otherAll Open Access, Green3
dc.identifier.otherhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84895057541&doi=10.1007%2fs00224-013-9511-y&partnerID=40&md5=1a8477fb9c1edb079ca279271dbd9de7
dc.identifier.otherhttp://arxiv.org/pdf/0909.3787m
dc.identifier.urihttp://hdl.handle.net/10995/102482-
dc.description.abstractWe 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.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceTheory Comput. Syst.2
dc.sourceTheory of Computing Systemsen
dc.subjectPOLYNOMIAL-TIME APPROXIMATIONen
dc.subjectSYNCHRONIZING AUTOMATAen
dc.titleApproximating the Minimum Length of Synchronizing Words Is Harden
dc.typeArticleen
dc.typeinfo:eu-repo/semantics/articleen
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.doi10.1007/s00224-013-9511-y-
dc.identifier.scopus84895057541-
local.contributor.employeeBerlinkov, M.V., Institute of Mathematics and Computer Science, Ural Federal University, 620000 Ekaterinburg, Russian Federation
local.description.firstpage211-
local.description.lastpage223-
local.issue2-
local.volume54-
local.contributor.departmentInstitute of Mathematics and Computer Science, Ural Federal University, 620000 Ekaterinburg, Russian Federation
local.identifier.pure336062-
local.identifier.pure2a1af4f8-c31b-4773-a54e-12357bdc2b1buuid
local.identifier.eid2-s2.0-84895057541-
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.