Document Open Access Logo

Low-Latency Sliding Window Algorithms for Formal Languages

Authors Moses Ganardi , Louis Jachiet , Markus Lohrey , Thomas Schwentick

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.38.pdf
  • Filesize: 0.8 MB
  • 23 pages

Document Identifiers

Author Details

Moses Ganardi
  • Max Planck Institute for Software Systems, Kaiserslautern, Germany
Louis Jachiet
  • LTCI, Télécom Paris, Institut Polytechnique de Paris, France
Markus Lohrey
  • Universität Siegen, Germany
Thomas Schwentick
  • TU Dortmund University, Germany

Funding

  • Lohrey, Markus: Partly supported by the DFG project LO748/13-1.

Cite AsGet BibTex

Moses Ganardi, Louis Jachiet, Markus Lohrey, and Thomas Schwentick. Low-Latency Sliding Window Algorithms for Formal Languages. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 38:1-38:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.38

Abstract

Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For every regular language L it is shown that there exists a constant-latency solution that supports adding and removing symbols independently on both ends of the window (the so-called two-way variable-size model). We prove that this result extends to all visibly pushdown languages. For deterministic 1-counter languages we present a 𝒪(log n) latency sliding window algorithm for the two-way variable-size model where n refers to the window size. We complement these results with a conditional lower bound: there exists a fixed real-time deterministic context-free language L such that, assuming the OMV (online matrix vector multiplication) conjecture, there is no sliding window algorithm for L with latency n^(1/2-ε) for any ε > 0, even in the most restricted sliding window model (one-way fixed-size model). The above mentioned results all refer to the unit-cost RAM model with logarithmic word size. For regular languages we also present a refined picture using word sizes 𝒪(1), 𝒪(log log n), and 𝒪(log n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Theory of computation → Grammars and context-free languages
  • Theory of computation → Streaming models
Keywords
  • Streaming algorithms
  • regular languages
  • context-free languages

Metrics

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

Related Versions

References

  1. Charu C. Aggarwal. Data Streams - Models and Algorithms. Springer, 2007. Google Scholar
  2. Rajeev Alur and P. Madhusudan. Visibly pushdown languages. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC 2004, pages 202-211. ACM, 2004. URL: https://doi.org/10.1145/1007352.1007390.
  3. Antoine Amarilli, Louis Jachiet, and Charles Paperman. Dynamic membership for regular languages. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 116:1-116:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.116.
  4. Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma. Streaming algorithms for language recognition problems. Theoretical Computer Science, 494:13-23, 2013. URL: https://doi.org/10.1016/j.tcs.2012.12.028.
  5. Ajesh Babu, Nutan Limaye, and Girish Varma. Streaming algorithms for some problems in log-space. In Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010, volume 6108 of Lecture Notes in Computer Science, pages 94-104. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13562-0_10.
  6. Gabriel Bathie and Tatiana Starikovskaya. Property testing of regular languages with applications to streaming property testing of visibly pushdown languages. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 119:1-119:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.119.
  7. Stanislav Böhm, Stefan Göller, and Petr Jancar. Equivalence of deterministic one-counter automata is NL-complete. In Proceedings of the 45th ACM Symposium on Theory of Computing, STOC 2013, pages 131-140. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488626.
  8. Stefano Crespi-Reghizzi and Dino Mandrioli. Operator precedence and the visibly pushdown property. Journal of Computer and System Sciences, 78(6):1837-1867, 2012. URL: https://doi.org/10.1016/j.jcss.2011.12.006.
  9. Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM Journal on Computing, 31(6):1794-1813, 2002. URL: https://doi.org/10.1137/S0097539701398363.
  10. Eldar Fischer, Frédéric Magniez, and Tatiana Starikovskaya. Improved bounds for testing Dyck languages. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 1529-1544. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.100.
  11. Robert W. Floyd. Syntactic analysis and operator precedence. Journal of the ACM, 10(3):316-333, 1963. URL: https://doi.org/10.1145/321172.321179.
  12. Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre. Streaming property testing of visibly pushdown languages. In Proceedings of the 24th Annual European Symposium on Algorithms, ESA 2016, volume 57 of LIPIcs, pages 43:1-43:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.43.
  13. Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, and Søren Skyum. Dynamic algorithms for the Dyck languages. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, WADS 1995, volume 955 of Lecture Notes in Computer Science, pages 98-108. Springer, 1995. URL: https://doi.org/10.1007/3-540-60220-8_54.
  14. Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems. Journal of the ACM, 44(2):257-271, 1997. URL: https://doi.org/10.1145/256303.256309.
  15. Moses Ganardi. Visibly pushdown languages over sliding windows. In Rolf Niedermeier and Christophe Paul, editors, Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 of LIPIcs, pages 29:1-29:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.29.
  16. Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras. Automata theory on sliding windows. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, volume 96 of LIPIcs, pages 31:1-31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.31.
  17. Moses Ganardi, Danny Hucke, and Markus Lohrey. Querying regular languages over sliding windows. In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, volume 65 of LIPIcs, pages 18:1-18:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.18.
  18. Moses Ganardi, Danny Hucke, and Markus Lohrey. Querying languages over sliding windows. CoRR, abs/1702.04376v1, 2017. URL: http://arxiv.org/abs/1702.04376.
  19. Moses Ganardi, Danny Hucke, and Markus Lohrey. Randomized sliding window algorithms for regular languages. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107 of LIPIcs, pages 127:1-127:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.127.
  20. Moses Ganardi, Louis Jachiet, Markus Lohrey, and Thomas Schwentick. Low-latency sliding window algorithms for formal languages. CoRR, abs/2209.14835, 2022. URL: http://arxiv.org/abs/2209.14835.
  21. Moses Ganardi, Artur Jez, and Markus Lohrey. Sliding windows over context-free languages. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, volume 117 of LIPIcs, pages 15:1-15:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  22. Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk, Gabriele Puppis, and Cristian Riveros. Dynamic Data Structures for Timed Automata Acceptance. In Proceedings of the 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, volume 214 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.IPEC.2021.20.
  23. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 21-30. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746609.
  24. Donald E. Knuth. On the translation of languages from left to right. Information and Control, 8(6):607-639, 1965. URL: https://doi.org/10.1016/S0019-9958(65)90426-2.
  25. Donald E. Knuth. The art of computer programming, Volume I: Fundamental Algorithms, 3rd Edition. Addison-Wesley, 1997. URL: https://www.worldcat.org/oclc/312910844.
  26. Andreas Krebs, Nutan Limaye, and Srikanth Srinivasan. Streaming algorithms for recognizing nearly well-parenthesized expressions. In Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011, volume 6907 of Lecture Notes in Computer Science, pages 412-423. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22993-0_38.
  27. 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. URL: https://doi.org/10.1137/130926122.
  28. Kanat Tangwongsan, Martin Hirzel, and Scott Schneider. Low-latency sliding-window aggregation in worst-case constant time. In Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems, DEBS 2017, pages 66-77. ACM, 2017. URL: https://doi.org/10.1145/3093742.3095107.
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 Imprint Privacy Contact