Synchronizing Data Words for Register Automata
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...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2016
|
| _version_ | 1797084812682461184 |
|---|---|
| author | Shirmohammadi, M Babari, P Quaas, K |
| author_facet | Shirmohammadi, M Babari, P Quaas, K |
| author_sort | Shirmohammadi, M |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T02:00:19Z |
| format | Conference item |
| id | oxford-uuid:9d2637df-d69f-47ba-a439-82b038694fbe |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:00:19Z |
| publishDate | 2016 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:9d2637df-d69f-47ba-a439-82b038694fbe2022-03-27T00:40:52ZSynchronizing Data Words for Register AutomataConference itemhttp://purl.org/coar/resource_type/c_5794uuid:9d2637df-d69f-47ba-a439-82b038694fbeSymplectic Elements at OxfordSchloss Dagstuhl2016Shirmohammadi, MBabari, PQuaas, KRegister 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. |
| spellingShingle | Shirmohammadi, M Babari, P Quaas, K Synchronizing Data Words for Register Automata |
| title | Synchronizing Data Words for Register Automata |
| title_full | Synchronizing Data Words for Register Automata |
| title_fullStr | Synchronizing Data Words for Register Automata |
| title_full_unstemmed | Synchronizing Data Words for Register Automata |
| title_short | Synchronizing Data Words for Register Automata |
| title_sort | synchronizing data words for register automata |
| work_keys_str_mv | AT shirmohammadim synchronizingdatawordsforregisterautomata AT babarip synchronizingdatawordsforregisterautomata AT quaask synchronizingdatawordsforregisterautomata |