{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:35:56Z","timestamp":1740137756917,"version":"3.37.3"},"reference-count":21,"publisher":"EDP Sciences","issue":"3-4","license":[{"start":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T00:00:00Z","timestamp":1556236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2019,3,27]]},"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:p>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 <jats:italic>M<\/jats:italic> is a monoid of {0, 1}-matrices of dimension <jats:italic>n<\/jats:italic> generated by a set <jats:italic>S<\/jats:italic>, then there is a matrix of <jats:italic>M<\/jats:italic> containing a relatively maximal row which can be expressed as a product of <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>) matrices of <jats:italic>S<\/jats:italic>. 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 <jats:italic>A<\/jats:italic>. It is a deterministic automaton, which is complete if and only if <jats:italic>A<\/jats:italic> is. We prove that the minimal length of the uncompletable words of <jats:italic>A<\/jats:italic> is polynomially bounded by the number of states of <jats:italic>A<\/jats:italic> and the minimal length of the uncompletable words of the associated maximal row automaton.<\/jats:p>","DOI":"10.1051\/ita\/2019002","type":"journal-article","created":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T07:51:05Z","timestamp":1556265065000},"page":"115-123","source":"Crossref","is-referenced-by-count":1,"title":["On the length of uncompletable words in unambiguous automata"],"prefix":"10.1051","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3795-8856","authenticated-orcid":false,"given":"Antonio","family":"Boccuto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3204-488X","authenticated-orcid":false,"given":"Arturo","family":"Carpi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2019,4,26]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1007\/s11786-007-0027-1","volume":"1","author":"B\u00e9al","year":"2008","journal-title":"Math. Comput. Sci"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Berstel J., \nPerrin D. and \nReutenauer C., \nCodes and automata. \nCambridge Univ. Press, \nCambridge \n(2010).","DOI":"10.1017\/CBO9781139195768"},{"key":"R3","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(80)90062-6","volume":"12","author":"Bo\u00eb","year":"1980","journal-title":"Theoret. Comput. Sci"},{"key":"R4","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0304-3975(88)90114-4","volume":"60","author":"Carpi","year":"1988","journal-title":"Theoret. Comput. Sci"},{"key":"R5","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/s00236-009-0106-7","volume":"46","author":"Carpi","year":"2009","journal-title":"Acta Inform"},{"key":"R6","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/j.aam.2012.07.003","volume":"50","author":"Carpi","year":"2013","journal-title":"Adv. Appl. Math"},{"key":"R7","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2015.08.042","volume":"664","author":"Carpi","year":"2017","journal-title":"Theoret. Comput. Sci"},{"key":"R8","first-page":"208","volume":"14","author":"\u010cern\u00fd","year":"1964","journal-title":"Mat. fyz. \u010das. SAV"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"C\u00e9sari Y., Sur l\u2019application du th\u00e9or\u00e8me de Suschkevitch \u00e0 l\u2019\u00e9tude des codes rationnells complets, in Automata, Languages and Programming. Vol. 370 of \nLecture Notes in Computer Science. \nSpringer, \nBerlin \n(1974) 342\u2013350.","DOI":"10.1007\/978-3-662-21545-6_26"},{"key":"R10","unstructured":"Fici G., \nPribavkina E.V. and \nSakarovitch J., \nOn the minimal uncompletable word problem. Preprint arXiv:1002.1928 \n(2010)."},{"key":"R11","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1051\/ro\/1982160403651","volume":"16","author":"Goral\u010dik","year":"1982","journal-title":"RAIRO: ITA"},{"key":"R12","doi-asserted-by":"crossref","first-page":"95","DOI":"10.3233\/FI-2014-1034","volume":"132","author":"Gusev","year":"2014","journal-title":"Fund. Inform"},{"key":"R13","unstructured":"Gusev V.V. and \nPribavkina E.V., On Non-complete Sets and Restivo\u2019s Conjecture, in Developments in Language Theory. Vol. 6795 of \nLecture Notes in Computer Science. \nSpringer, \nBerlin \n(2011) 239\u2013250."},{"key":"R14","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.tcs.2007.10.033","volume":"391","author":"N\u00e9raud","year":"2008","journal-title":"Theoret. Comput. Sci"},{"key":"R15","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0304-3975(99)00160-7","volume":"255","author":"N\u00e9raud","year":"2001","journal-title":"Theoret. Comput. Sci"},{"key":"R16","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1002\/sapm1970491105","volume":"49","author":"Paterson","year":"1970","journal-title":"Stud. Appl. Math"},{"key":"R17","first-page":"535","volume":"17","author":"Pin","year":"1983","journal-title":"Ann. Discrete Math"},{"key":"R18","doi-asserted-by":"crossref","first-page":"422","DOI":"10.4213\/mzm6191","volume":"90","author":"Pribavkina","year":"2011","journal-title":"Math. Zametki"},{"key":"R19","unstructured":"Restivo A., Codes and complete sets, Th\u00e9orie des codes, Actes de la VII \u00c9cole de Printemps d\u2019informatique th\u00e9orique, Jougne, edited by \nPerrin D.. \nLITP et le centre d\u2019\u00e9dition et de documentation de l\u2019 ENSTA \n(1979)."},{"key":"R20","unstructured":"Restivo A., Some remarks on complete subsets of a free monoid, in Non-Commutative Structures in \nAlgebra and Geometric Combinatorics, International Colloquium, Arco Felice, July 1978, in Vol. 109 of Quaderni de \u201cLa Ricerca Scientifica\u201d, CNR. Edited by \nde Luca A. \n(1981) 19\u201325."},{"key":"R21","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1051\/ita\/1989230201351","volume":"23","author":"Restivo","year":"1989","journal-title":"Theoret. Inform. Appl"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2019002\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T17:36:11Z","timestamp":1584639371000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2019002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,26]]},"references-count":21,"journal-issue":{"issue":"3-4"},"alternative-id":["ita180036"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2019002","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"type":"print","value":"0988-3754"},{"type":"electronic","value":"1290-385X"}],"subject":[],"published":{"date-parts":[[2019,4,26]]}}}