Synchronizing data words for register automata
From MaRDI portal
Publication:5222876
DOI10.1145/3309760zbMATH Open1433.68199arXiv1710.02329OpenAlexW2926815817WikidataQ128155921 ScholiaQ128155921MaRDI QIDQ5222876FDOQ5222876
Karin Quaas, Mahsa Shirmohammadi
Publication date: 4 July 2019
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Abstract: 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? 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 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) distinct data (where 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.
Full work available at URL: https://arxiv.org/abs/1710.02329
Recommendations
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (4)
This page was built for publication: Synchronizing data words for register automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222876)
