Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952264 | Theoretical Computer Science | 2017 | 11 Pages |
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 Äerný 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Arturo Carpi, Flavio D'Alessandro,