Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111871
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBéal, M. -P.en
dc.contributor.authorBerlinkov, M. V.en
dc.contributor.authorPerrin, D.en
dc.date.accessioned2022-05-12T08:24:22Z-
dc.date.available2022-05-12T08:24:22Z-
dc.date.issued2011-
dc.identifier.citationBéal M. -P. A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata / M. -P. Béal, M. V. Berlinkov, D. Perrin // International Journal of Foundations of Computer Science. — 2011. — Vol. 22. — Iss. 2. — P. 277-288.en
dc.identifier.issn0129-0541-
dc.identifier.otherAll Open Access, Green3
dc.identifier.urihttp://hdl.handle.net/10995/111871-
dc.description.abstractČerný's conjecture asserts the existence of a synchronizing word of length at most (n - 1)2 for any synchronized n-state deterministic automaton. We prove a quadratic upper bound on the length of a synchronizing word for any synchronized n-state deterministic automaton satisfying the following additional property: there is a letter a such that for any pair of states p, q, one has p·ar = q·as for some integers r, s (for a state p and a word w, we denote by p·w the state reached from p by the path labeled w). As a consequence, we show that for any finite synchronized prefix code with an n-state decoder, there is a synchronizing word of length O(n2). This applies in particular to Huffman codes. © 2011 World Scientific Publishing Company.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.publisherWorld Scientific Pub Co Pte Lten
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceInt. J. Found. Comput. Sci.2
dc.sourceInternational Journal of Foundations of Computer Scienceen
dc.subjectČERNÝ'S CONJECTUREen
dc.subjectROAD COLORING PROBLEMen
dc.subjectSYNCHRONIZED AUTOMATAen
dc.titleA Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automataen
dc.typeConference Paperen
dc.typeinfo:eu-repo/semantics/conferenceObjecten
dc.typeinfo:eu-repo/semantics/submittedVersionen
dc.identifier.scopus79952131123-
local.contributor.employeeBéal, M.-P., Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, CNRS, 77454 Marne-la-Vallée Cedex 2, France; Berlinkov, M.V., Department of Algebra and Discrete Mathematics, Ural State University, 620083 Ekaterinburg, Russian Federation; Perrin, D., Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, CNRS, 77454 Marne-la-Vallée Cedex 2, Franceen
local.description.firstpage277-
local.description.lastpage288-
local.issue2-
local.volume22-
local.contributor.departmentUniversité Paris-Est, Laboratoire d'Informatique Gaspard-Monge, CNRS, 77454 Marne-la-Vallée Cedex 2, France; Department of Algebra and Discrete Mathematics, Ural State University, 620083 Ekaterinburg, Russian Federationen
local.identifier.eid2-s2.0-79952131123-
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-79952131123.pdf259,74 kBAdobe PDFView/Open


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