Abstract: This paper situates itself in the theory of variable length codes and of finite automata where the concepts of completeness and synchronization play a central role. In this theoretical setting, we investigate the problem of finding upper bounds to the minimal length of synchronizing words and incompletable words of a finite language X in terms of the length of the words of X. This problem is related to two well-known conjectures formulated by Cerny and Restivo, respectively. In particular, if Restivo's conjecture is true, our main result provides a quadratic bound for the minimal length of a synchronizing pair of any finite synchronizing complete code with respect to the maximal length of its words.
Recommendations
- A synergic approach to the minimal uncompletable words problem
- Subset synchronization and careful synchronization of binary finite automata
- Strongly connected synchronizing automata and the language of minimal reset words
- In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
- On non-complete sets and Restivo's conjecture
Cites work
- scientific article; zbMATH DE number 3605922 (Why is no real title available?)
- scientific article; zbMATH DE number 3222112 (Why is no real title available?)
- A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
- A quadratic upper bound on the size of a synchronizing word in one-cluster automata
- Equivalence of topological Markov shifts
- Independent sets of words and the synchronization problem
- Minimal complete sets of words
- On non-complete sets and Restivo's conjecture
- On synchronizing unambiguous automata
- On the hybrid Černý-road coloring problem and Hamiltonian paths
- Slowly synchronizing automata and digraphs
- Strongly transitive automata and the Černý conjecture
- Synchronizing Automata and the Černý Conjecture
- The Synchronization Problem for Locally Strongly Transitive Automata
- The Synchronization Problem for Strongly Transitive Automata
- The road coloring problem
- Theory of finite automata
Cited in
(6)- On non-complete sets and Restivo's conjecture
- On Nonnegative Integer Matrices and Short Killing Words
- On the length of uncompletable words in unambiguous automata
- In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
- On finite monoids over nonnegative integer matrices and short killing words
- A synergic approach to the minimal uncompletable words problem
This page was built for publication: On incomplete and synchronizing finite sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517035)
