A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
| Autor: | Dominique Perrin, Marie-Pierre Béal, Mikhail V. Berlinkov |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Department of Algebra and Discrete Mathematics, Ural State University, Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM) |
| Rok vydání: | 2011 |
| Předmět: |
road coloring problem
Prefix code Discrete mathematics Černý's conjecture [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 010102 general mathematics Synchronizing word 0102 computer and information sciences State (functional analysis) Huffman coding 01 natural sciences Upper and lower bounds Combinatorics symbols.namesake 010201 computation theory & mathematics Deterministic automaton Path (graph theory) Computer Science (miscellaneous) symbols 0101 mathematics Computer Science::Formal Languages and Automata Theory synchronized automata Word (computer architecture) Mathematics |
| Zdroj: | International Journal of Foundations of Computer Science International Journal of Foundations of Computer Science, World Scientific Publishing, 2011, 22 (2), pp.277-288. ⟨10.1142/S0129054111008039⟩ |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054111008039 |
| Popis: | Č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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|