Document Open Access Logo

Sliding Window Property Testing for Regular Languages

Authors Moses Ganardi, Danny Hucke, Markus Lohrey, Tatiana Starikovskaya

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.6.pdf
  • Filesize: 462 kB
  • 13 pages

Document Identifiers

Author Details

Moses Ganardi
  • Universität Siegen, Germany
Danny Hucke
  • Universität Siegen, Germany
Markus Lohrey
  • Universität Siegen, Germany
Tatiana Starikovskaya
  • DI/ENS, PSL Research University, Paris, France

Funding

  • Ganardi, Moses: Funded by DFG project LO 748/13-1.
  • Lohrey, Markus: Funded by DFG project LO 748/13-1.

Cite AsGet BibTex

Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding Window Property Testing for Regular Languages. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.6

Abstract

We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window n and a stream of symbols. At each time instant, we must decide whether the suffix of length n of the current stream ("the active window") belongs to a given regular language. Recent works [Moses Ganardi et al., 2018; Moses Ganardi et al., 2016] showed that the space complexity of an optimal deterministic sliding window algorithm for this problem is either constant, logarithmic or linear in the window size n and provided natural language theoretic characterizations of the space complexity classes. Subsequently, [Moses Ganardi et al., 2018] extended this result to randomized algorithms to show that any such algorithm admits either constant, double logarithmic, logarithmic or linear space complexity. In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We show that for every regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Streaming algorithms
  • approximation algorithms
  • regular 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. Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy. Regular Languages are Testable with a Constant Number of Queries. SIAM Journal on Computing, 30(6):1842-1862, 2000. URL: https://doi.org/10.1137/S0097539700366528.
  3. Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma. Streaming algorithms for language recognition problems. Theoretical Computer Science, 494:13-23, 2013. Google Scholar
  4. Vladimir Braverman, Rafail Ostrovsky, and Carlo Zaniolo. Optimal sampling from sliding windows. Journal of Computer and System Sciences, 78(1):260-272, 2012. Google Scholar
  5. Dany Breslauer and Zvi Galil. Real-Time Streaming String-Matching. ACM Transactions on Algorithms, 10(4):22:1-22:12, 2014. URL: https://doi.org/10.1145/2635814.
  6. Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya. Dictionary Matching in a Stream. In Proceedings of ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 361-372. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_31.
  7. Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya. The k-mismatch problem revisited. In Proceedings of SODA 2016, pages 2039-2052. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch142.
  8. Raphaël Clifford, Tomasz Kociumaka, and Ely Porat. The streaming k-mismatch problem. In Proceedings of SODA 2019, pages 1106-1125. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.68.
  9. Raphaël Clifford and Tatiana Starikovskaya. Approximate Hamming Distance in a Stream. In Proceedings of ICALP 2016, volume 55 of LIPIcs, pages 20:1-20:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.20.
  10. 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
  11. Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. Testing and Spot-Checking of Data Streams. Algorithmica, 34(1):67-80, 2002. URL: https://doi.org/10.1007/s00453-002-0959-4.
  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 ESA 2016, volume 57 of LIPIcs, pages 43:1-43:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  13. Moses Ganardi. Visibly Pushdown Languages over Sliding Windows. In Proceedings of 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.
  14. Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras. Automata theory on sliding windows. In Proceedings of STACS 2018, volume 96 of LIPIcs, pages 31:1-31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  15. Moses Ganardi, Danny Hucke, and Markus Lohrey. Querying Regular Languages over Sliding Windows. In Proceedings of FSTTCS 2016, volume 65 of LIPIcs, pages 18:1-18:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  16. Moses Ganardi, Danny Hucke, and Markus Lohrey. Randomized Sliding Window Algorithms for Regular Languages. In Proceedings of ICALP 2018, volume 107 of LIPIcs, pages 127:1-127:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  17. Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding window property testing for regular languages. Technical report, arXiv.org, 2020. URL: http://arxiv.org/abs/1909.10261.
  18. Moses Ganardi, Artur Jeż, and Markus Lohrey. Sliding Windows over Context-Free Languages. In Proceedings of MFCS 2018, volume 117 of LIPIcs, pages 15:1-15:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  19. Shay Golan, Tsvi Kopelowitz, and Ely Porat. Streaming Pattern Matching with d Wildcards. In Proceedings of ESA 2016, volume 57 of LIPIcs, pages 44:1-44:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.44.
  20. Shay Golan, Tsvi Kopelowitz, and Ely Porat. Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams. In Proceedings of ICALP 2018, volume 107 of LIPIcs, pages 65:1-65:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.65.
  21. Shay Golan and Ely Porat. Real-Time Streaming Multi-Pattern Search for Constant Alphabet. In Proceedings of ESA 2017, volume 87 of LIPIcs, pages 41:1-41:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.41.
  22. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property Testing and its Connection to Learning and Approximation. Journal of the ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  23. John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA, 1979. Google Scholar
  24. Rahul Jain and Ashwin Nayak. The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited. IEEE Transactions on Information Theory, 60(10):6646-6668, October 2014. URL: https://doi.org/10.1109/TIT.2014.2339859.
  25. Andreas Krebs, Nutan Limaye, and Srikanth Srinivasan. Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions. In Proceedings of MFCS 2011, volume 6907 of Lecture Notes in Computer Science, pages 412-423. Springer, 2011. Google Scholar
  26. 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
  27. Robert H. Morris. Counting Large Numbers of Events in Small Registers. Communications of the ACM, 21(10):840-842, 1978. URL: https://doi.org/10.1145/359619.359627.
  28. Benny Porat and Ely Porat. Exact and Approximate Pattern Matching in the Streaming Model. In Proceedings of FOCS 2009, pages 315-323. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.11.
  29. Michael O. Rabin. Probabilistic Automata. Information and Control, 6(3):230-245, 1963. Google Scholar
  30. Tatiana Starikovskaya. Communication and Streaming Complexity of Approximate Pattern Matching. In Proceedings of CPM 2017, volume 78 of LIPIcs, pages 13:1-13:11. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CPM.2017.13.
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