Document Open Access Logo

Synchronizing Data Words for Register Automata

Authors Parvaneh Babari, Karin Quaas, Mahsa Shirmohammadi

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2016.15.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • data words
  • register automata
  • synchronizing problem
  • Ackermann-completeness
  • bounded universality
  • regular-like expressions with squaring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Parvaneh Babari, Karin Quaas, and Mahsa Shirmohammadi. Synchronizing Data Words for Register Automata. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.15

Author Details

Parvaneh Babari
Karin Quaas
Mahsa Shirmohammadi

References

  1. Renzo Angles and Claudio Gutierrez. Survey of graph database models. ACM Comput. Surv., 40(1):1:1-1:39, February 2008. URL: http://dx.doi.org/10.1145/1322432.1322433.
  2. Pablo Barceló, Leonid Libkin, Anthony W. Lin, and Peter T. Wood. Expressive languages for path queries over graph-structured data. ACM Trans. Database Syst., 37(4):31:1-31:46, December 2012. URL: http://dx.doi.org/10.1145/2389241.2389250.
  3. Yaakov Benenson, Rivka Adar, Tamar Paz-Elizur, Zvi Livneh, and Ehud Shapiro. DNA molecule provides a computing machine with both data and fuel. Proc. National Acad. Sci. USA, 100:2191-2196, 2003. URL: http://dx.doi.org/10.1073/pnas.0535624100.
  4. Mikołaj Bojańczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin, and Claire David. Two-variable logic on words with data. In 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings, pages 7-16. IEEE Computer Society, 2006. URL: http://dx.doi.org/10.1109/LICS.2006.51.
  5. Mikolaj Bojanczyk and Pawel Parys. Xpath evaluation in linear time. J. ACM, 58(4):17:1-17:33, July 2011. URL: http://dx.doi.org/10.1145/1989727.1989731.
  6. Ahmed Bouajjani, Peter Habermehl, Yan Jurski, and Mihaela Sighireanu. Rewriting systems with data. In Erzsébet Csuhaj-Varjú and Zoltán Ésik, editors, Fundamentals of Computation Theory, 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings, volume 4639 of Lecture Notes in Computer Science, pages 1-22. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74240-1_1.
  7. Patricia Bouyer, Antoine Petit, and Denis Thérien. An algebraic approach to data languages and timed languages. Inf. Comput., 182(2):137-162, 2003. URL: http://dx.doi.org/10.1016/S0890-5401(03)00038-5.
  8. Ján Černý. Poznámka k homogénnym experimentom s konečnými automatmi. Matematicko-fyzikálny časopis, 14(3):208-216, 1964. Google Scholar
  9. Krishnendu Chatterjee and Laurent Doyen. Computation tree logic for synchronization properties. In To be appear in 43rd Internation Colloquim on Automata, Languages, and programming, ICALP 2016, 2016. Google Scholar
  10. Dmitry Chistikov, Pavel Martyugin, and Mahsa Shirmohammadi. Synchronizing automata over nested words. In Foundations of Software Science and Computation Structures - 19th International Conference, FOSSACS 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proceedings, volume 9634 of Lecture Notes in Computer Science, pages 252-268. Springer, 2016. Google Scholar
  11. Lorenzo Clemente and Slawomir Lasota. Timed pushdown automata revisited. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 738-749. IEEE, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.73.
  12. Stéphane Demri and Ranko Lazic. LTL with the freeze quantifier and register automata. ACM Trans. Comput. Log., 10(3), 2009. URL: http://dx.doi.org/10.1145/1507244.1507246.
  13. Stéphane Demri, Ranko Lazic, and David Nowak. On the freeze quantifier in constraint LTL: decidability and complexity. Inf. Comput., 205(1):2-24, 2007. URL: http://dx.doi.org/10.1016/j.ic.2006.08.003.
  14. Stéphane Demri, Ranko Lazic, and Arnaud Sangnier. Model checking memoryful linear-time logics over one-counter automata. Theor. Comput. Sci., 411(22-24):2298-2316, 2010. URL: http://dx.doi.org/10.1016/j.tcs.2010.02.021.
  15. Laurent Doyen, Line Juhl, Kim Guldstrand Larsen, Nicolas Markey, and Mahsa Shirmohammadi. Synchronizing words for weighted and timed automata. In Venkatesh Raman and S. P. Suresh, editors, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India, volume 29 of LIPIcs, pages 121-132. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2014.121.
  16. Laurent Doyen, Thierry Massart, and Mahsa Shirmohammadi. Infinite synchronizing words for probabilistic automata. In Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings, volume 6907 of Lecture Notes in Computer Science, pages 278-289. Springer, 2011. Google Scholar
  17. Diego Figueira. Satisfiability of downward xpath with data equality tests. In Proceedings of the Twenty-eighth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '09, pages 197-206, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1559795.1559827.
  18. Diego Figueira. Alternating register automata on finite words and trees. Logical Methods in Computer Science, 8(1), 2012. URL: http://dx.doi.org/10.2168/LMCS-8(1:22)2012.
  19. Diego Figueira, Santiago Figueira, Sylvain Schmitz, and Philippe Schnoebelen. Ackermannian and primitive-recursive bounds with Dickson’s lemma. In Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, LICS 2011, June 21-24, 2011, Toronto, Ontario, Canada, pages 269-278. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/LICS.2011.39.
  20. Michael Kaminski and Nissim Francez. Finite-memory automata. Theor. Comput. Sci., 134(2):329-363, 1994. URL: http://dx.doi.org/10.1016/0304-3975(94)90242-9.
  21. Jan Kretínský, Kim Guldstrand Larsen, Simon Laursen, and Jirí Srba. Polynomial time decidability of weighted synchronization under partial observability. In 26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, September 1.4, 2015, volume 42 of LIPIcs, pages 142-154. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  22. Kim Guldstrand Larsen, Simon Laursen, and Jirí Srba. Synchronizing strategies under partial observability. In CONCUR 2014 - Concurrency Theory - 25th International Conference, CONCUR 2014, Rome, Italy, September 2-5, 2014. Proceedings, volume 8704 of Lecture Notes in Computer Science, pages 188-202. Springer, 2014. Google Scholar
  23. Alexei Lisitsa and Igor Potapov. Temporal logic with predicate lambda-abstraction. In 12th International Symposium on Temporal Representation and Reasoning (TIME 2005), 23-25 June 2005, Burlington, Vermont, USA, pages 147-155. IEEE Computer Society, 2005. URL: http://dx.doi.org/10.1109/TIME.2005.34.
  24. Pavel V. Martyugin. Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA. In Computer Science - Theory and Applications, 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings, volume 6072 of Lecture Notes in Computer Science, pages 288-302. Springer, 2010. Google Scholar
  25. Frank Neven, Thomas Schwentick, and Victor Vianu. Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log., 5(3):403-435, 2004. URL: http://dx.doi.org/10.1145/1013560.1013562.
  26. Jean-Eric Pin. Sur les mots synthronisants dans un automate fini. Elektronische Informationsverarbeitung und Kybernetik, 14(6):297-303, 1978. Google Scholar
  27. Hiroshi Sakamoto and Daisuke Ikeda. Intractability of decision problems for finite-memory automata. Theor. Comput. Sci., 231(2):297-308, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(99)00105-X.
  28. Sylvain Schmitz. Complexity hierarchies beyond elementary. ACM Trans. Comput. Theory, 8(1):3:1-3:36, 2016. Google Scholar
  29. Mahsa Shirmohammadi. Phd thesis: Qualitative analysis of probabilistic synchronizing systems. 2014. Google Scholar
  30. Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: Preliminary report. In Alfred V. Aho, Allan Borodin, Robert L. Constable, Robert W. Floyd, Michael A. Harrison, Richard M. Karp, and H. Raymond Strong, editors, Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA, pages 1-9. ACM, 1973. URL: http://dx.doi.org/10.1145/800125.804029.
  31. Nikos Tzevelekos. Fresh-register automata. In Thomas Ball and Mooly Sagiv, editors, Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 295-306. ACM, 2011. URL: http://dx.doi.org/10.1145/1926385.1926420.
  32. Mikhail V. Volkov. Synchronizing automata and the cerny conjecture. In Carlos Martín-Vide, Friedrich Otto, and Henning Fernau, editors, Language and Automata Theory and Applications, Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers, volume 5196 of Lecture Notes in Computer Science, pages 11-27. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-88282-4_4.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact