Document Open Access Logo

Adaptive Synchronisation of Pushdown Automata

Authors A. R. Balasubramanian , K. S. Thejaswini

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2021.17.pdf
  • Filesize: 0.87 MB
  • 15 pages

Document Identifiers

Author Details

A. R. Balasubramanian
  • Technische Universität München, Germany
K. S. Thejaswini
  • Department of Computer Science, University of Warwick, Coventry, UK

Funding

  • Balasubramanian, A. R.: Supported by funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 787367 (PaVeS).
  • Thejaswini, K. S.: Supported by the EPSRC grant EP/P020992/1 (Solving Parity Games in Theory and Practice).

Acknowledgements

We would like to thank Dmitry Chistikov for referring us to previous works on this topic.

Cite As Get BibTex

A. R. Balasubramanian and K. S. Thejaswini. Adaptive Synchronisation of Pushdown Automata. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CONCUR.2021.17

Abstract

We introduce the notion of adaptive synchronisation for pushdown automata, in which there is an external observer who has no knowledge about the current state of the pushdown automaton, but can observe the contents of the stack. The observer would then like to decide if it is possible to bring the automaton from any state into some predetermined state by giving inputs to it in an adaptive manner, i.e., the next input letter to be given can depend on how the contents of the stack changed after the current input letter. We show that for non-deterministic pushdown automata, this problem is 2-EXPTIME-complete and for deterministic pushdown automata, we show EXPTIME-completeness. 
To prove the lower bounds, we first introduce (different variants of) subset-synchronisation and show that these problems are polynomial-time equivalent with the adaptive synchronisation problem. We then prove hardness results for the subset-synchronisation problems. For proving the upper bounds, we consider the problem of deciding if a given alternating pushdown system has an accepting run with at most k leaves and we provide an n^O(k²) time algorithm for this problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Grammars and context-free languages
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Adaptive synchronisation
  • Pushdown automata
  • Alternating pushdown systems

Metrics

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

Related Versions

References

  1. A. R. Balasubramanian and K. S. Thejaswini. Adaptive synchronisation of pushdown automata, 2021. URL: http://arxiv.org/abs/2102.06897.
  2. Marie-Pierre Béal, Eugen Czeizler, Jarkko Kari, and Dominique Perrin. Unambiguous automata. Math. Comput. Sci., 1(4):625-638, 2008. URL: https://doi.org/10.1007/s11786-007-0027-1.
  3. Yaakov Benenson, Rivka Adar, Tamar Paz-Elizur, Zvi Livneh, and Ehud Shapiro. Dna molecule provides a computing machine with both data and fuel. Proceedings of the National Academy of Sciences, 100(5):2191-2196, 2003. Google Scholar
  4. Ahmed Bouajjani, Javier Esparza, and Oded Maler. Reachability analysis of pushdown automata: Application to model-checking. In Antoni W. Mazurkiewicz and Józef Winkowski, editors, CONCUR '97: Concurrency Theory, 8th International Conference, Warsaw, Poland, July 1-4, 1997, Proceedings, volume 1243 of Lecture Notes in Computer Science, pages 135-150. Springer, 1997. URL: https://doi.org/10.1007/3-540-63141-0_10.
  5. Manfred Broy, Bengt Jonsson, Joost-Pieter Katoen, Martin Leucker, and Alexander Pretschner, editors. Model-Based Testing of Reactive Systems, Advanced Lectures [The volume is the outcome of a research seminar that was held in Schloss Dagstuhl in January 2004], volume 3472 of LNCS. Springer, 2005. Google Scholar
  6. Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114-133, 1981. URL: https://doi.org/10.1145/322234.322243.
  7. Dmitry Chistikov, Pavel Martyugin, and Mahsa Shirmohammadi. Synchronizing automata over nested words. J. Autom. Lang. Comb., 24(2-4):219-251, 2019. URL: https://doi.org/10.25596/jalc-2019-219.
  8. 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 für Informatik, 2014. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2014.121.
  9. Laurent Doyen, Thierry Massart, and Mahsa Shirmohammadi. The complexity of synchronizing markov decision processes. J. Comput. Syst. Sci., 100:96-129, 2019. URL: https://doi.org/10.1016/j.jcss.2018.09.004.
  10. David Eppstein. Reset sequences for monotonic automata. SIAM J. Comput., 19(3):500-510, 1990. Google Scholar
  11. Henning Fernau and Petra Wolf. Synchronization of deterministic visibly push-down automata. In Nitin Saxena and Sunil Simon, editors, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, December 14-18, 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference), volume 182 of LIPIcs, pages 45:1-45:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2020.45.
  12. Henning Fernau, Petra Wolf, and Tomoyuki Yamakami. Synchronizing deterministic push-down automata can be really hard. In Javier Esparza and Daniel Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 33:1-33:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.33.
  13. Patrice Godefroid and Mihalis Yannakakis. Analysis of boolean programs. In Nir Piterman and Scott A. Smolka, editors, Tools and Algorithms for the Construction and Analysis of Systems - 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings, volume 7795 of Lecture Notes in Computer Science, pages 214-229. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36742-7_16.
  14. F. C. Hennine. Fault detecting experiments for sequential circuits. In 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pages 95-110, 1964. Google Scholar
  15. Chris Keeler and Kai Salomaa. Alternating finite automata with limited universal branching. In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Milan, Italy, March 4-6, 2020, Proceedings, volume 12038 of Lecture Notes in Computer Science, pages 196-207. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-40608-0_13.
  16. Arun Lakhotia, Eric Uday Kumar, and M. Venable. A method for detecting obfuscated calls in malicious binaries. IEEE Transactions on Software Engineering, 31(11):955-968, 2005. URL: https://doi.org/10.1109/TSE.2005.120.
  17. Kim Guldstrand Larsen, Simon Laursen, and Jirí Srba. Synchronizing strategies under partial observability. In Paolo Baldan and Daniele Gorla, editors, 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. URL: https://doi.org/10.1007/978-3-662-44584-6_14.
  18. D. Lee and M. Yannakakis. Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE, 84(8):1090-1123, 1996. Google Scholar
  19. Balas K Natarajan. An algorithmic approach to the automated design of parts orienters. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 132-142. IEEE, 1986. Google Scholar
  20. Karin Quaas and Mahsa Shirmohammadi. Synchronizing data words for register automata. ACM Trans. Comput. Log., 20(2):11:1-11:27, 2019. URL: https://doi.org/10.1145/3309760.
  21. Fu Song and Tayssir Touili. Pushdown model checking for malware detection. Int. J. Softw. Tools Technol. Transf., 16(2):147-173, 2014. URL: https://doi.org/10.1007/s10009-013-0290-1.
  22. 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: https://doi.org/10.1007/978-3-540-88282-4_4.
  23. Igor Walukiewicz. Pushdown processes: Games and model-checking. Inf. Comput., 164(2):234-263, 2001. URL: https://doi.org/10.1006/inco.2000.2894.
  24. 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
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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