2026-07-21T19:28:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6499 2024-03-06T10:38:15Z ddc:004 open_access

Synchronizing Data Words for Register Automata Babari, Parvaneh Quaas, Karin Shirmohammadi, Mahsa data words register automata synchronizing problem Ackermann-completeness bounded universality regular-like expressions with squaring Register automata (RAs) are finite automata extended with a finite set of registers to store and compare data. 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? For deterministic RAs with k registers (k-DRAs), we prove that inputting data words with 2k+1 distinct data, from the infinite data domain, is sufficient to synchronize. We show that the synchronizing problem for DRAs is in general PSPACE-complete, and is NLOGSPACE-complete for 1-DRAs. For nondeterministic RAs (NRAs), we show that Ackermann(n) distinct data (where n is the size of RA) might be necessary to synchronize. The synchronizing problem for NRAs is in general undecidable, however, we establish Ackermann-completeness of the problem for 1-NRAs. Our most substantial achievement is proving NEXPTIME-completeness of the length-bounded synchronizing problem in NRAs (length encoded in binary). A variant of this last construction allows to prove that the bounded universality problem in NRAs is co-NEXPTIME-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Parvaneh Babari and Karin Quaas and Mahsa Shirmohammadi 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.15 urn:nbn:de:0030-drops-64996 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.15 eng https://creativecommons.org/licenses/by/3.0/legalcode