{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:10:03Z","timestamp":1750198203728,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T00:00:00Z","timestamp":1616371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Centre, Poland","award":["2017\/25\/B\/ST6\/01920"],"award-info":[{"award-number":["2017\/25\/B\/ST6\/01920"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            We solve open problems concerning the Kleene star\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            of a finite set\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            of words over an alphabet\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . The\n            <jats:italic>Frobenius monoid<\/jats:italic>\n            problem is the question for a given finite set of words\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , whether the language\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            is cofinite. We show that it is PSPACE-complete. We also exhibit an infinite family of sets\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            such that the length of the longest words not in\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            (when\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            is cofinite) is exponential in the length of the longest words in\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            and subexponential in the sum of the lengths of words in\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . The\n            <jats:italic>factor universality<\/jats:italic>\n            problem is the question for a given finite set of words\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , whether every word over\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            is a factor (substring) of some word from\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . We show that it is also PSPACE-complete. Besides that, we exhibit an infinite family of sets\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            such that the length of the shortest words not being a factor of any word in\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            is exponential in the length of the longest words in\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            and subexponential in the sum of the lengths of words in\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . This essentially settles in the negative the longstanding Restivo\u2019s conjecture (1981) and its weak variations. All our solutions are based on one shared construction, and as an auxiliary general tool, we introduce the concept of\n            <jats:italic>set rewriting systems<\/jats:italic>\n            . Finally, we complement the results with upper bounds.\n          <\/jats:p>","DOI":"10.1145\/3447237","type":"journal-article","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T16:22:02Z","timestamp":1616430122000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words"],"prefix":"10.1145","volume":"68","author":[{"given":"Maksymilian","family":"Mika","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5349-468X","authenticated-orcid":false,"given":"Marek","family":"Szyku\u0142a","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/578775"},{"key":"e_1_2_1_2_1","first-page":"1","article-title":"The Frobenius problem, rational polytopes, and Fourier\u2013Dedekind sums","volume":"96","author":"Beck M.","year":"2002","unstructured":"M. Beck , R. Diaz , and S. Robins . 2002 . The Frobenius problem, rational polytopes, and Fourier\u2013Dedekind sums . J. Number Theory 96 (2002), 1 \u2013 21 . M. Beck, R. Diaz, and S. Robins. 2002. The Frobenius problem, rational polytopes, and Fourier\u2013Dedekind sums. J. Number Theory 96 (2002), 1\u201321.","journal-title":"J. Number Theory"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3233\/COM-150032"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"J. Berstel D. Perrin and C. Reutenauer. 2010. Codes and Automata. Cambridge University Press.  J. Berstel D. Perrin and C. Reutenauer. 2010. Codes and Automata. Cambridge University Press.","DOI":"10.1017\/CBO9781139195768"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00382-6"},{"key":"e_1_2_1_6_1","first-page":"3","article-title":"On the length of uncompletable words in unambiguous automata","volume":"53","author":"Boccuto A.","year":"2019","unstructured":"A. Boccuto and A. Carpi . 2019 . On the length of uncompletable words in unambiguous automata . RAIRO-Theor. Info. Appl. 53 , 3 \u2013 4 (2019), 115\u2013123. A. Boccuto and A. Carpi. 2019. On the length of uncompletable words in unambiguous automata. RAIRO-Theor. Info. Appl. 53, 3\u20134 (2019), 115\u2013123.","journal-title":"RAIRO-Theor. Info. Appl."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371684"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.08.042"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.030"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1256059464"},{"key":"e_1_2_1_11_1","unstructured":"G. Fici E. V. Pribavkina and J. Sakarovitch. 2010. On the Minimal Uncompletable Word Problem. Retrieved from https:\/\/arxiv.org\/abs\/1002.1928.  G. Fici E. V. Pribavkina and J. Sakarovitch. 2010. On the Minimal Uncompletable Word Problem. Retrieved from https:\/\/arxiv.org\/abs\/1002.1928."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032178.2032201"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90042-X"},{"key":"e_1_2_1_14_1","first-page":"271","article-title":"A synergic approach to the minimal uncompletable words problem","volume":"22","author":"Julia S.","year":"2017","unstructured":"S. Julia , A. Malapert , and J. Provillard . 2017 . A synergic approach to the minimal uncompletable words problem . J. Autom. Lang. Combinator. 22 , 4 (2017), 271 \u2013 286 . S. Julia, A. Malapert, and J. Provillard. 2017. A synergic approach to the minimal uncompletable words problem. J. Autom. Lang. Combinator. 22, 4 (2017), 271\u2013286.","journal-title":"J. Autom. Lang. Combinator."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01204720"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the STACS (LIPIcs), Susanne Albers and Pascal Weil (Eds.)","volume":"1","author":"Kao J.-Y.","unstructured":"J.-Y. Kao , J. Shallit , and Z. Xu . 2008. The Frobenius problem in a free monoid . In Proceedings of the STACS (LIPIcs), Susanne Albers and Pascal Weil (Eds.) , Vol. 1 . 421\u2013432. J.-Y. Kao, J. Shallit, and Z. Xu. 2008. The Frobenius problem in a free monoid. In Proceedings of the STACS (LIPIcs), Susanne Albers and Pascal Weil (Eds.), Vol. 1. 421\u2013432."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112400540"},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"On finite monoids over nonnegative integer matrices and short killing words","volume":"43","author":"Kiefer S.","year":"2019","unstructured":"S. Kiefer and C. Mascle . 2019 . On finite monoids over nonnegative integer matrices and short killing words . In Proceedings of the STACS (LIPIcs). 43 : 1 \u2013 43 :13. S. Kiefer and C. Mascle. 2019. On finite monoids over nonnegative integer matrices and short killing words. In Proceedings of the STACS (LIPIcs). 43:1\u201343:13.","journal-title":"Proceedings of the STACS (LIPIcs)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00233-017-9867-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01300131"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2385073.2385090"},{"volume-title":"Quaderni de \u201cLa Ricerca Scientifica.","author":"Restivo A.","key":"e_1_2_1_22_1","unstructured":"A. Restivo . 1981. Some remarks on complete subsets of a free monoid . In Quaderni de \u201cLa Ricerca Scientifica. \u201d Non-Commutative Structures in Algebra and Geometric Combinatorics. Vol. 109 . CNR Roma , 19\u201325. A. Restivo. 1981. Some remarks on complete subsets of a free monoid. In Quaderni de \u201cLa Ricerca Scientifica.\u201d Non-Commutative Structures in Algebra and Geometric Combinatorics. Vol. 109. CNR Roma, 19\u201325."},{"key":"e_1_2_1_23_1","volume-title":"BCTCS 2014","author":"Shallit J.","year":"2014","unstructured":"J. Shallit . [n.d.]. Open problems in automata theory: An idiosyncratic view, LMS Keynote Address in Discrete Mathematics , BCTCS 2014 , April 10 2014 , Loughborough, England. Retrieved from https:\/\/cs.uwaterloo.ca\/ shallit\/Talks\/bc4.pdf. J. Shallit. [n.d.]. Open problems in automata theory: An idiosyncratic view, LMS Keynote Address in Discrete Mathematics, BCTCS 2014, April 10 2014, Loughborough, England. Retrieved from https:\/\/cs.uwaterloo.ca\/ shallit\/Talks\/bc4.pdf."},{"key":"e_1_2_1_25_1","unstructured":"Z. Xu and J. Shallit. 2008. An NP-hardness Result on the Monoid Frobenius Problem. Retrieved from https:\/\/arxiv.org\/abs\/0805.4049.  Z. Xu and J. Shallit. 2008. An NP-hardness Result on the Monoid Frobenius Problem. Retrieved from https:\/\/arxiv.org\/abs\/0805.4049."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447237","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447237","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:27Z","timestamp":1750195707000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,22]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3447237"],"URL":"https:\/\/doi.org\/10.1145\/3447237","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2021,3,22]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}