Dynamic Data Structures for Timed Automata Acceptance

Authors Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk, Gabriele Puppis, Cristian Riveros



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.20.pdf
  • Filesize: 0.69 MB
  • 18 pages

Document Identifiers

Author Details

Alejandro Grez
  • Pontificia Universidad Católica de Chile, Santiago, Chile
  • Millennium Institute for Foundational Research on Data, Santiago, Chile
Filip Mazowiecki
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
Michał Pilipczuk
  • University of Warsaw, Poland
Gabriele Puppis
  • University of Udine, Italy
Cristian Riveros
  • Pontificia Universidad Católica de Chile, Santiago, Chile
  • Millennium Institute for Foundational Research on Data, Santiago, Chile

Cite AsGet BibTex

Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk, Gabriele Puppis, and Cristian Riveros. Dynamic Data Structures for Timed Automata Acceptance. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.20

Abstract

We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton 𝒜 with amortized update time 2^{𝒪(|𝒜|)} per input symbol.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • timed automata
  • data stream
  • dynamic data structure

Metrics

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

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 434-443. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.53.
  2. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. SIAM J. Comput., 47(3):1098-1122, 2018. URL: https://doi.org/10.1137/15M1050987.
  3. Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams. Dynamic parameterized problems and algorithms. ACM Trans. Algorithms, 16(4):45:1-45:46, 2020. URL: https://doi.org/10.1145/3395037.
  4. Rajeev Alur and David L. Dill. A theory of timed automata. Theor. Comput. Sci., 126(2):183-235, 1994. URL: https://doi.org/10.1016/0304-3975(94)90010-8.
  5. Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom. Models and issues in data stream systems. In 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2002, pages 1-16, 2002. Google Scholar
  6. Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma. Streaming algorithms for language recognition problems. Theoretical Computer Science, 494:13-23, 2013. Google Scholar
  7. Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, and Till Tantau. Dynamic kernels for hitting sets and set packing. Electron. Colloquium Comput. Complex., 26:146, 2019. URL: https://eccc.weizmann.ac.il/report/2019/146.
  8. Béatrice Bérard and Catherine Dufourd. Timed automata and additive clock constraints. Inf. Process. Lett., 75(1-2):1-7, 2000. URL: https://doi.org/10.1016/S0020-0190(00)00075-2.
  9. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates. In 36th ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems, pages 303-318, 2017. Google Scholar
  10. Patricia Bouyer, Samy Jaziri, and Nicolas Markey. Efficient timed diagnosis using automata with timed domains. In 18th International Conference on Runtime Verification, RV 2018, pages 205-221, 2018. URL: https://doi.org/10.1007/978-3-030-03769-7_12.
  11. Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk, Manuel Sorge, Bartłomiej Wróblewski, and Anna Zych-Pawlewicz. Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. In 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 796-809. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.50.
  12. Lorenzo Clemente and Sławomir Lasota. Timed pushdown automata revisited. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, pages 738-749, 2015. URL: https://doi.org/10.1109/LICS.2015.73.
  13. Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM Journal on Computing, 31(6):1794-1813, 2002. Google Scholar
  14. Moses Ganardi. Language recognition in the sliding window model. PhD thesis, Universität Siegen, 2019. URL: https://doi.org/10.25819/ubsi/464.
  15. Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras. Automata theory on sliding windows. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, pages 31:1-31:14, 2018. Google Scholar
  16. Moses Ganardi, Danny Hucke, and Markus Lohrey. Querying regular languages over sliding windows. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, pages 18:1-18:14, 2016. Google Scholar
  17. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. Computing on data streams. External memory algorithms, 50:107-118, 1998. Google Scholar
  18. Muhammad Idris, Martín Ugarte, Stijn Vansummeren, Hannes Voigt, and Wolfgang Lehner. Efficient query processing for dynamically changing datasets. ACM SIGMOD Record, 48(1):33-40, 2019. Google Scholar
  19. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 1272-1287. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch89.
  20. Martin Leucker and Christian Schallhart. A brief account of runtime verification. J. Log. Algebr. Program., 78(5):293-303, 2009. URL: https://doi.org/10.1016/j.jlap.2008.08.004.
  21. Philip M Lewis, Richard Edwin Stearns, and Juris Hartmanis. Memory bounds for recognition of context-free and context-sensitive languages. In 6th Annual Symposium on Switching Circuit Theory and Logical Design, SWCT 1965, pages 191-202. IEEE, 1965. Google Scholar
  22. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized expressions in the streaming model. SIAM Journal on Computing, 43(6):1880-1905, 2014. Google Scholar
  23. Mihai Pătraşcu. Towards polynomial lower bounds for dynamic problems. In 42nd ACM Symposium on Theory of Computing, STOC 2010, pages 603-610. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806772.
  24. Kanat Tangwongsan, Martin Hirzel, and Scott Schneider. Low-latency sliding-window aggregation in worst-case constant time. In 11th ACM International Conference on Distributed and Event-based Systems, pages 66-77, 2017. Google Scholar
  25. Prasanna Thati and Grigore Rosu. Monitoring algorithms for metric temporal logic specifications. Electron. Notes Theor. Comput. Sci., 113:145-162, 2005. URL: https://doi.org/10.1016/j.entcs.2004.01.029.
  26. Stavros Tripakis. Fault diagnosis for timed automata. In 7th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, FTRTFT 2002, pages 205-224, 2002. URL: https://doi.org/10.1007/3-540-45739-9_14.
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