{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:27:54Z","timestamp":1758274074580,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,27]],"date-time":"2019-03-27T00:00:00Z","timestamp":1553644800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["QU 316\/1-2"],"award-info":[{"award-number":["QU 316\/1-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>Register automata (RAs) are finite automata extended with a finite set of registers to store and compare data from an infinite domain. We study the concept of synchronizing data words in RAs: does there exist a data word that sends all states of the RA to a single state?<\/jats:p>\n          <jats:p>\n            For deterministic RAs with\n            <jats:italic>k<\/jats:italic>\n            registers (\n            <jats:italic>k<\/jats:italic>\n            -DRAs), we prove that inputting data words with 2\n            <jats:italic>k<\/jats:italic>\n            +1 distinct data from the infinite data domain is sufficient to synchronize. We show that the synchronization problem for DRAs is in general PSPACE-complete, and it is NLOGSPACE-complete for 1-DRAs. For nondeterministic RAs (NRAs), we show that Ackermann(\n            <jats:italic>n<\/jats:italic>\n            ) distinct data (where\n            <jats:italic>n<\/jats:italic>\n            is the size of the RA) might be necessary to synchronize. The synchronization problem for NRAs is in general undecidable; however, we establish Ackermann-completeness of the problem for 1-NRAs. Another main result is the NEXPTIME-completeness of the length-bounded synchronization problem for NRAs, where a bound on the length of the synchronizing data word, written in binary, is given. A variant of this last construction allows to prove that the length-bounded universality problem for NRAs is co-NEXPTIME-complete.\n          <\/jats:p>","DOI":"10.1145\/3309760","type":"journal-article","created":{"date-parts":[[2019,3,28]],"date-time":"2019-03-28T12:23:24Z","timestamp":1553775804000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Synchronizing Data Words for Register Automata"],"prefix":"10.1145","volume":"20","author":[{"given":"Karin","family":"Quaas","sequence":"first","affiliation":[{"name":"Universit\u00e4t Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahsa","family":"Shirmohammadi","sequence":"additional","affiliation":[{"name":"CNRS, IRIF, and University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"volume-title":"Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916)","year":"2016","author":"Babari Parvaneh","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389250"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0535624100"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.51"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989727.1989731"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74240-1_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00038-5"},{"key":"e_1_2_1_9_1","unstructured":"J\u00e1n \u010cern\u00fd. 1964. Pozn\u00e1mka k homog\u00e9nnym experimentom s kone\u010dn\u00fdmi automatmi. Matematicko-fyzik\u00e1lny \u010dasopis 14 3 (1964) 208--216.  J\u00e1n \u010cern\u00fd. 1964. Pozn\u00e1mka k homog\u00e9nnym experimentom s kone\u010dn\u00fdmi automatmi. Matematicko-fyzik\u00e1lny \u010dasopis 14 3 (1964) 208--216."},{"volume-title":"Foundations of Software Science and Computation Structures","series-title":"Lecture Notes in Computer Science","author":"Chistikov Dmitry","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.73"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1507244.1507246"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.08.003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.02.021"},{"volume-title":"Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201914)","year":"2014","author":"Doyen Laurent","key":"e_1_2_1_15_1"},{"volume-title":"Mathematical Foundations of Computer Science","series-title":"Lecture Notes in Computer Science","author":"Doyen Laurent","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559827"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Diego Figueira. 2012. Alternating register automata on finite words and trees. Log. Methods Comput. Sci. 8 1 (2012) Article 22.  Diego Figueira. 2012. Alternating register automata on finite words and trees. Log. Methods Comput. Sci. 8 1 (2012) Article 22.","DOI":"10.2168\/LMCS-8(1:22)2012"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.39"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90242-9"},{"volume-title":"Proceedings of the 26th International Conference on Concurrency Theory (CONCUR\u201915)","year":"2015","author":"Kret\u00ednsk\u00fd Jan","key":"e_1_2_1_21_1"},{"volume-title":"CONCUR 2014\u2014Concurrency Theory","series-title":"Lecture Notes in Computer Science","author":"Larsen Kim Guldstrand","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIME.2005.34"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13182-0_27"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013560.1013562"},{"key":"e_1_2_1_26_1","first-page":"297","article-title":"Sur les mots synthronisants dans un automate fini","volume":"14","author":"Pin Jean-Eric","year":"1978","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00105-X"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858784"},{"key":"e_1_2_1_29_1","unstructured":"Mahsa Shirmohammadi. 2014. Qualitative Analysis of Probabilistic Synchronizing Systems. Ph.D. Dissertation. Universite Libre de Bruxelles Belgium and Ecole Normale Superieure de Cachan France.  Mahsa Shirmohammadi. 2014. Qualitative Analysis of Probabilistic Synchronizing Systems. Ph.D. Dissertation. Universite Libre de Bruxelles Belgium and Ecole Normale Superieure de Cachan France."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926420"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88282-4_4"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309760","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:36Z","timestamp":1750204416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,27]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3309760"],"URL":"https:\/\/doi.org\/10.1145\/3309760","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2019,3,27]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}