{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T09:48:25Z","timestamp":1775036905839,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00224-024-10204-9","type":"journal-article","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T07:15:24Z","timestamp":1775027724000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Completely Distinguishable Automata and the Set of Synchronizing Words"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7866-075X","authenticated-orcid":false,"given":"Stefan","family":"Hoffmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,1]]},"reference":[{"key":"10204_CR1","doi-asserted-by":"publisher","unstructured":"Ara\u00fajo, J., Cameron, P.J.: Primitive groups synchronize non-uniform maps of extreme ranks. J. Comb. Theory, Ser. B. 106, 98\u2013114 (2014). ISSN: 0095-8956. https:\/\/doi.org\/10.1016\/j.jctb.2014.01.006","DOI":"10.1016\/j.jctb.2014.01.006"},{"issue":"2","key":"10204_CR2","doi-asserted-by":"publisher","first-page":"101","DOI":"10.4171\/EMSS\/4-2-1","volume":"4","author":"J Ara\u00fajo","year":"2017","unstructured":"Ara\u00fajo, J., Cameron, P.J., Steinberg, B.: Between primitive and 2-transitive: Synchronization and its friends. EMS Surv. Math. Sci. 4(2), 101\u2013184 (2017). https:\/\/doi.org\/10.4171\/EMSS\/4-2-1","journal-title":"EMS Surv. Math. Sci."},{"key":"10204_CR3","doi-asserted-by":"crossref","unstructured":"Berstel, J., Perrin, D., Reutenauer, C.: Codes and automata, vol. 129. Cambridge University Press, Encyclopedia of mathematics and its applications (2009)978-0-521-88831-8. doi: 10.1017\/CBO9781139195768","DOI":"10.1017\/CBO9781139195768"},{"key":"10204_CR4","doi-asserted-by":"publisher","unstructured":"Bondar, E.A., Volkov, M.V.: Completely reachable automata. In: C\u00e2mpeanu, C., Manea, F., Shallit, J.O. (eds.) Descriptional Complexity of Formal Systems - 18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016, Proceedings, vol. 9777, pp. 1\u201317. Lecture Notes in Computer Science (2016). Springer. ISBN: 978-3-319-41113-2. https:\/\/doi.org\/10.1007\/978-3-319-41114-9_1","DOI":"10.1007\/978-3-319-41114-9_1"},{"issue":"6","key":"10204_CR5","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1142\/S0129054123450053","volume":"34","author":"EA Bondar","year":"2023","unstructured":"Bondar, E.A., Casas, D., Volkov, M.V.: Completely reachable automata: An interplay between automata, graphs, and trees. Int. J. Found. Comput. Sci. 34(6), 655\u2013690 (2023). https:\/\/doi.org\/10.1142\/S0129054123450053","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10204_CR6","unstructured":"Cern\u00fd, J., Pirick\u00e1, A., Rosenauerov\u00e1, B.: On directable automata. Kybernetika 7(4), 289\u2013298 (1971). http:\/\/www.kybernetika.cz\/content\/1971\/4\/289"},{"key":"10204_CR7","unstructured":"\u010cern\u00fd, J.: Pozn\u00e1mka k homog\u00e9nnym experimentom s kone\u010dn\u00fdmi automatmi. Matematicko-fyzik\u00e1lny \u010dasopis 14(3), 208\u2013216 (1964). (Translation: A Note on Homogeneous Experiments with Finite Automata. Journal of Automata, Languages and Combinatorics 24(2-4), 123\u2013132)"},{"key":"10204_CR8","doi-asserted-by":"publisher","unstructured":"Don, H.: The \u010cern\u00fd conjecture and 1-contracting automata. Electron. J. Comb. 23(P3.12), P3.12 (2016). https:\/\/doi.org\/10.37236\/5616","DOI":"10.37236\/5616"},{"issue":"3","key":"10204_CR9","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/0219033","volume":"19","author":"D Eppstein","year":"1990","unstructured":"Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19(3), 500\u2013510 (1990). https:\/\/doi.org\/10.1137\/0219033","journal-title":"SIAM J. Comput."},{"key":"10204_CR10","doi-asserted-by":"publisher","unstructured":"Ferens, R., Szyku\u0142a, M.: Completely reachable automata: A polynomial algorithm and quadratic upper bounds. In: Etessami, K., Feige, U., Puppis, G. (eds.) 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, vol. 261, pp. 59:1\u201359:17. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2023.59","DOI":"10.4230\/LIPIcs.ICALP.2023.59"},{"key":"10204_CR11","doi-asserted-by":"publisher","unstructured":"Fernau, H., et\u00a0al.: Computational complexity of synchronization under regular constraints. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, vol. 138, pp. 63:1\u201363:14. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). ISBN: 978-3-95977-117-7. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.63","DOI":"10.4230\/LIPIcs.MFCS.2019.63"},{"key":"10204_CR12","doi-asserted-by":"publisher","unstructured":"Gao, Y., et\u00a0al.: A survey on operational state complexity. J. Autom. Lang. Comb. 21(4), 251\u2013310 (2017). https:\/\/doi.org\/10.25596\/jalc-2016-251","DOI":"10.25596\/jalc-2016-251"},{"issue":"2\u20134","key":"10204_CR13","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/BF01891840","volume":"10","author":"KY Goldberg","year":"1993","unstructured":"Goldberg, K.Y.: Orienting polygonal parts without sensors. Algorithmica 10(2\u20134), 210\u2013225 (1993). https:\/\/doi.org\/10.1007\/BF01891840","journal-title":"Algorithmica"},{"key":"10204_CR14","doi-asserted-by":"publisher","unstructured":"Hoffmann, S.: Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words. In: Leporati, A., et\u00a0al. (eds.) Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Milan, Italy, March 1-5, 2021, Proceedings, vol. 12638, pp. 305\u2013317. Lecture Notes in Computer Science. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-68195-1_24","DOI":"10.1007\/978-3-030-68195-1_24"},{"key":"10204_CR15","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2021.08.030","volume":"890","author":"S Hoffmann","year":"2021","unstructured":"Hoffmann, S.: Constrained synchronization and commutativity. Theoret. Comput. Sci. 890, 147\u2013170 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.08.030","journal-title":"Theoret. Comput. Sci."},{"key":"10204_CR16","doi-asserted-by":"publisher","unstructured":"Hoffmann, S.: Sync-maximal permutation groups equal primitive permutation groups. In: Han, Y.-S., Ko, S.-K. (eds.) Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings, vol. 13037, pp. 38\u201350. Lecture Notes in Computer Science. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-93489-7_4","DOI":"10.1007\/978-3-030-93489-7_4"},{"key":"10204_CR17","doi-asserted-by":"publisher","unstructured":"Hoffmann, S.: Reset complexity and completely reachable automata with simple idempotents. In: Han, Y.-S., Vaszil, G. (eds.) Descriptional Complexity of Formal Systems - 24rd IFIP WG 1.02 International Conference, DCFS 2022, August 29 - 31, 2022, Debrecen, Hungary, Proceedings, vol. 13439, pp. 85\u201399. Lecture Notes in Computer Science. Springer (2022).https:\/\/doi.org\/10.1007\/978-3-031-13257-5_7","DOI":"10.1007\/978-3-031-13257-5_7"},{"key":"10204_CR18","doi-asserted-by":"publisher","unstructured":"Hoffmann, S.: Binary and circular automata having maximal state complexity for the set of synchronizing words. In: Information and Computation, vol. 295, p. 105076. Special Issue: Selected papers of the 15th International Conference on Language and Automata Theory and Applications, LATA 2021. ISSN: 0890-5401 (2023)https:\/\/doi.org\/10.1016\/j.ic.2023.105076","DOI":"10.1016\/j.ic.2023.105076"},{"key":"10204_CR19","doi-asserted-by":"publisher","unstructured":"Hoffmann, S.: Completely distinguishable automata and the set of synchronizing words. In: Drewes, F., Volkov, M. (eds.) Developments in Language Theory - 27th International Conference, DLT 2023, Ume\u00e5, Sweden, June 12-16, 2023, Proceedings, vol. 13911, pp. 128\u2013142. Lecture Notes in Computer Science. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-33264-7_11","DOI":"10.1007\/978-3-031-33264-7_11"},{"key":"10204_CR20","doi-asserted-by":"publisher","unstructured":"Hoffmann, S.: New characterizations of primitive permutation groups with applications to synchronizing automata. In: Information and Computation, vol. 295, p. 105086. Special Issue: Selected papers of the 15th International Conference on Language and Automata Theory and Applications, LATA 2021. ISSN: 0890-5401.https:\/\/doi.org\/10.1016\/j.ic.2023.105086 (2023)","DOI":"10.1016\/j.ic.2023.105086"},{"issue":"2","key":"10204_CR21","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.ic.2017.09.003","volume":"259","author":"M Holzer","year":"2018","unstructured":"Holzer, M., Jakobi, S.: On the computational complexity of problems related to distinguishability sets. Inf. Comput. 259(2), 225\u2013236 (2018). https:\/\/doi.org\/10.1016\/j.ic.2017.09.003","journal-title":"Inf. Comput."},{"key":"10204_CR22","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Company (1979)"},{"issue":"1","key":"10204_CR23","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"ND Jones","year":"1975","unstructured":"Jones, N.D.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11(1), 68\u201385 (1975). https:\/\/doi.org\/10.1016\/S0022-0000(75)80050-X","journal-title":"J. Comput. Syst. Sci."},{"issue":"9\u201310","key":"10204_CR24","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1016\/j.ic.2008.03.005","volume":"206","author":"H J\u00fcrgensen","year":"2008","unstructured":"J\u00fcrgensen, H.: Synchronization. Inf. Comput. 206(9\u201310), 1033\u20131044 (2008). https:\/\/doi.org\/10.1016\/j.ic.2008.03.005","journal-title":"Inf. Comput."},{"key":"10204_CR25","doi-asserted-by":"publisher","unstructured":"Kari, J., Volkov, M.V.: \u010cern\u00fd\u2019s conjecture and the road colouring problem. In: Pin, J.\u00c9. (ed.) Handbook of Automata Theory, Volume I, pp. 525\u2013565. European Mathematical Society Publishing House (2021). https:\/\/doi.org\/10.4171\/automata","DOI":"10.4171\/automata"},{"issue":"6\u20137","key":"10204_CR26","doi-asserted-by":"publisher","first-page":"1177","DOI":"10.1142\/S0129054119400343","volume":"30","author":"MI Maslennikova","year":"2019","unstructured":"Maslennikova, M.I.: Reset complexity of ideal languages over a binary alphabet. Int. J. Found. Comput. Sci. 30(6\u20137), 1177\u20131196 (2019). https:\/\/doi.org\/10.1142\/S0129054119400343","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10204_CR27","doi-asserted-by":"publisher","unstructured":"Casas, D., Volkov, M.V.: Binary completely reachable automata. In: Casta\u00f1eda, A., Rodr\u00edguez-Henr\u00edquez, F. (eds.) LATIN 2022: Theoretical Informatics - 15th Latin American Symposium, Guanajuato, Mexico, Proceedings, vol. 13568, pp. 345\u2013358. Lecture Notes in Computer Science. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-20624-5_21","DOI":"10.1007\/978-3-031-20624-5_21"},{"key":"10204_CR28","doi-asserted-by":"publisher","unstructured":"Natarajan, B.K.: An algorithmic approach to the automated design of parts orienters. In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pp. 132\u2013142. IEEE Computer Society (1986).https:\/\/doi.org\/10.1109\/SFCS.1986.5","DOI":"10.1109\/SFCS.1986.5"},{"key":"10204_CR29","doi-asserted-by":"publisher","unstructured":"Neumann, P.M.: The mathematical writings of \u00c9variste Galois. Heritage of European Mathematics. European Mathematical Society (2011). https:\/\/doi.org\/10.4171\/104","DOI":"10.4171\/104"},{"key":"10204_CR30","unstructured":"Rystsov, I.K.: On minimizing the length of synchronizing words for finite automata. In: Theory of Designing of Computing Systems, (in Russian), pp. 75\u201382. Institute of Cybernetics of Ukrainian Acad. Sci. (1980)"},{"key":"10204_CR31","doi-asserted-by":"publisher","unstructured":"Rystsov, I.K.: Estimation of the length of reset words for automata with simple idempotents. Cybernetics and Systems Analysis 36(3), 339\u2013344 (2000). ISSN: 1573-8337. https:\/\/doi.org\/10.1007\/BF02732984","DOI":"10.1007\/BF02732984"},{"issue":"1","key":"10204_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10559-022-00428-3","volume":"58","author":"IK Rystsov","year":"2022","unstructured":"Rystsov, I.K.: Cerny\u2019s conjecture for automata with simple idempotents. Cybern. Syst. Anal. 58(1), 1\u20137 (2022). https:\/\/doi.org\/10.1007\/s10559-022-00428-3","journal-title":"Cybern. Syst. Anal."},{"key":"10204_CR33","doi-asserted-by":"publisher","unstructured":"Sandberg, S.: Homing and synchronizing sequences. In: Broy, M., et\u00a0al. (eds.) Model-based Testing of Reactive Systems, Advanced Lectures [The volume is the outcome of a research seminar that was held in Schloss Dagstuhl in January 2004], vol. 3472, pp. 5\u201333. Lecture Notes in Computer Science. Springer (2005). https:\/\/doi.org\/10.25596\/jalc-2019-367","DOI":"10.25596\/jalc-2019-367"},{"key":"10204_CR34","doi-asserted-by":"publisher","unstructured":"Shitov, Y.: An improvement to a recent upper bound for synchronizing words of finite automata. J. Autom. Lang. Comb. 24(2\u20134), 367\u2013373 (2019). https:\/\/doi.org\/10.25596\/jalc-2019-367","DOI":"10.25596\/jalc-2019-367"},{"key":"10204_CR35","doi-asserted-by":"publisher","unstructured":"Starke, P.H.: Eine Bemerkung \u00fcber homogene Experimente. Elektronische Informationverarbeitung und Kybernetik (later Journal of Information Processing and Cybernetics) 2(2), 61\u201382 (1966). (Translation: A remark about homogeneous experiments. Journal of Automata, Languages and Combinatorics 24(2-4), 133 \u2013 237 (2019)). https:\/\/doi.org\/10.25596\/JALC-2019-133","DOI":"10.25596\/JALC-2019-133"},{"key":"10204_CR36","doi-asserted-by":"publisher","unstructured":"Szyku\u0142a, M.: Improving the upper bound on the length of the shortest reset word. In: Niedermeier, R., Vall\u00e9e, B. (eds.) 35th Symposium on Theoretical Aspects of Computer Science, STACS, vol. 96, pp. 56:1\u201356:13. LIPIcs. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). ISBN: 978-3-95977-062-0. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.56","DOI":"10.4230\/LIPIcs.STACS.2018.56"},{"key":"10204_CR37","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s11856-009-0062-5","volume":"172","author":"AN Trahtman","year":"2009","unstructured":"Trahtman, A.N.: The road coloring problem. Israel J. Math. 172, 51\u201360 (2009). https:\/\/doi.org\/10.1007\/s11856-009-0062-5","journal-title":"Israel J. Math."},{"key":"10204_CR38","doi-asserted-by":"publisher","unstructured":"Volkov, M.V.: Synchronizing automata and the \u010cern\u00fd conjecture. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.) Language and Automata Theory and Applications, 2nd Int. Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers, vol. 5196, pp. 11\u201327. Lecture Notes in Computer Science. Springer. ISBN: 978-3-540-88281-7 (2008). https:\/\/doi.org\/10.1007\/978-3-540-88282-4_4","DOI":"10.1007\/978-3-540-88282-4_4"},{"key":"10204_CR39","doi-asserted-by":"publisher","unstructured":"Volkov, M.V.: Preface. J. Autom. Lang. Comb. 24(2-4), 119\u2013121 (2019).https:\/\/doi.org\/10.25596\/jalc-2019-119","DOI":"10.25596\/jalc-2019-119"},{"issue":"2","key":"10204_CR40","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125(2), 315\u2013328 (1994). https:\/\/doi.org\/10.1016\/0304-3975(92)00011-F","journal-title":"Theoret. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10204-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10204-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10204-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T07:15:27Z","timestamp":1775027727000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10204-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,1]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10204"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10204-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,1]]},"assertion":[{"value":"18 November 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2026","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"20"}}