On incomplete and synchronizing finite sets
From MaRDI portal
Publication:517035
DOI10.1016/J.TCS.2015.08.042zbMATH Open1359.68161arXiv1612.07881OpenAlexW1888551009MaRDI QIDQ517035FDOQ517035
Authors: Arturo Carpi, Flavio D'Alessandro 
Publication date: 16 March 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1612.07881
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
- Synchronizing Automata and the Černý Conjecture
- A quadratic upper bound on the size of a synchronizing word in one-cluster automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Equivalence of topological Markov shifts
- On the hybrid Černý-road coloring problem and Hamiltonian paths
- Slowly synchronizing automata and digraphs
- The road coloring problem
- Theory of finite automata
- Strongly transitive automata and the Černý conjecture
- On synchronizing unambiguous automata
- Minimal complete sets of words
- Independent sets of words and the synchronization problem
- The Synchronization Problem for Locally Strongly Transitive Automata
- The Synchronization Problem for Strongly Transitive Automata
- A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
- On non-complete sets and Restivo's conjecture
Cited In (6)
- On Nonnegative Integer Matrices and Short Killing Words
- On the length of uncompletable words in unambiguous automata
- On non-complete sets and Restivo's conjecture
- On finite monoids over nonnegative integer matrices and short killing words
- In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
- 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)
