On the length of uncompletable words in unambiguous automata

Boccuto, Antonio; Carpi, Arturo

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 3-4, pp. 115-123.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

This paper deals with uncomplete unambiguous automata. In this setting, we investigate the minimal length of uncompletable words. This problem is connected with a well-known conjecture formulated by A. Restivo. We introduce the notion of relatively maximal row for a suitable monoid of matrices. We show that, if $M$ is a monoid of $\{0,1\}$-matrices of dimension $n$ generated by a set $S$, then there is a matrix of $M$ containing a relatively maximal row which can be expressed as a product of $O\left(n^3\right)$ matrices of ) matrices of S. As an application, we derive some upper bound to the minimal length of an uncompletable word of an uncomplete unambiguous automaton, in the case that its transformation monoid contains a relatively maximal row which is not maximal. Finally we introduce the maximal row automaton associated with an unambiguous automaton $S$. As an application, we derive some upper bound to the minimal length of an uncompletable word of an uncomplete unambiguous automaton, in the case that its transformation monoid contains a relatively maximal row which is not maximal. Finally we introduce the maximal row automaton associated with an unambiguous automaton $𝒜$. It is a deterministic automaton, which is complete if and only if $𝒜$ is. We prove that the minimal length of the uncompletable words of $A$ is polynomially bounded by the number of states of $𝒜$ and the minimal length of the uncompletable words of the associated maximal row automaton.

[1] M.-P. Béal, E. Czeizler, J. Kari and D. Perrin, Unambiguous automata. Math. Comput. Sci. 1 (2008) 625–638. | DOI | MR | Zbl

[2] J. Berstel, D. Perrin and C. Reutenauer, Codes and automata. Cambridge Univ. Press, Cambridge (2010). | MR | Zbl

[3] J.M. Boë, A. De Luca and A. Restivo, Minimal complete sets of words. Theoret. Comput. Sci. 12 (1980) 325–332. | DOI | MR | Zbl

[4] A. Carpi, On synchronizing unambiguous automata. Theoret. Comput. Sci. 60 (1988) 285–296. | DOI | MR | Zbl

[5] A. Carpi and F. D’Alessandro, Strongly transitive automata and the Černý conjecture. Acta Inform. 46 (2009) 591–607. | DOI | MR | Zbl

[6] A. Carpi and F. D’Alessandro, Independent sets of words and the synchronization problem. Adv. Appl. Math. 50 (2013) 339–355. | DOI | MR | Zbl

[7] A. Carpi and F. D’Alessandro, On incomplete and synchronizing finite sets. Theoret. Comput. Sci. 664 (2017) 67–77. | DOI | MR | Zbl

[8] J. Černý, Poznámka k homogénnym experimentom s konecnymi automatmi. Mat. fyz. čas. SAV 14 (1964) 208–215. | Zbl

[9] Y. Césari, Sur l’application du théorème de Suschkevitch à l’étude des codes rationnells complets, in Automata, Languages and Programming. Vol. 370 of Lecture Notes in Computer Science. Springer, Berlin (1974) 342–350. | DOI | MR | Zbl

[10] G. Fici, E.V. Pribavkina and J. Sakarovitch, On the minimal uncompletable word problem. Preprint (2010). | arXiv

[11] P. Goralčik, Z. Hedrlin, V. Koubek and J. Ryšlinková, A game of composing binary relations. RAIRO: ITA 16 (1982) 365–369. | Numdam | MR | Zbl

[12] V.V. Gusev, M.I. Maslennikova and E.V. Pribavkina, Principal Ideal Languages and Synchronizing Automata. Fund. Inform. 132 (2014) 95–108. | MR | Zbl

[13] V.V. Gusev and E.V. Pribavkina, On Non-complete Sets and Restivo’s Conjecture, in Developments in Language Theory. Vol. 6795 of Lecture Notes in Computer Science. Springer, Berlin (2011) 239–250. | DOI | MR | Zbl

[14] J. Néraud, Completing circular codes in regular submonoids. Theoret. Comput. Sci. 391 (2008) 90–98. | DOI | MR | Zbl

[15] J. Néraud and C. Selmi, On codes with a finite deciphering delay: constructing uncompletable words. Theoret. Comput. Sci. 255 (2001) 67–77. | DOI | MR | Zbl

[16] M.S. Paterson, Unsolvability in 3 × 3 matrices. Stud. Appl. Math. 49 (1970) 105–107. | DOI | MR | Zbl

[17] J.-E. Pin, On two combinatorial problems arising from automata theory. Ann. Discrete Math. 17 (1983) 535–548. | MR | Zbl

[18] E.V. Pribavkina, Slowly synchronizing automata with zero and incomplete sets (Russian). Math. Zametki 90 (2011) 422–430; [translation in Math. Notes 90 (2011) 411–417]. | MR | Zbl

[19] A. Restivo, Codes and complete sets, Théorie des codes, Actes de la VII École de Printemps d’informatique théorique, Jougne, edited by D. Perrin. LITP et le centre d’édition et de documentation de l’ ENSTA (1979).

[20] A. Restivo, Some remarks on complete subsets of a free monoid, in Non-Commutative Structures in Algebra and Geometric Combinatorics, International Colloquium, Arco Felice, July 1978, in Vol. 109 of Quaderni de “La Ricerca Scientifica”, CNR. Edited by A. De Luca (1981) 19–25. | MR | Zbl

[21] A. Restivo, S. Salemi, T. Sportelli, Completing codes. Theoret. Inform. Appl. 23 (1989) 135–147. | DOI | Numdam | MR | Zbl