Document Open Access Logo

Property Testing of Regular Languages with Applications to Streaming Property Testing of Visibly Pushdown Languages

Authors Gabriel Bathie, Tatiana Starikovskaya

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.119.pdf
  • Filesize: 0.76 MB
  • 17 pages

Document Identifiers

Author Details

Gabriel Bathie
  • École normale supérieure de Lyon, France
Tatiana Starikovskaya
  • DIENS, École normale supérieure de Paris, PSL Research University, France

Funding

This work was partially funded by the grants ANR-19-CE48-0016 and ANR-20-CE48-0001 from the French National Research Agency (ANR).

Cite As Get BibTex

Gabriel Bathie and Tatiana Starikovskaya. Property Testing of Regular Languages with Applications to Streaming Property Testing of Visibly Pushdown Languages. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 119:1-119:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.119

Abstract

In this work, we revisit the problem of testing membership in regular languages, first studied by Alon et al. [Alon et al., 2001]. We develop a one-sided error property tester for regular languages under weighted edit distance that makes 𝒪(ε^{-1} log(1/ε)) non-adaptive queries, assuming that the language is described by an automaton of constant size. Moreover, we show a matching lower bound, essentially closing the problem for the edit distance. As an application, we improve the space bound of the current best streaming property testing algorithm for visibly pushdown languages from 𝒪(ε^{-4} log⁶ n) to 𝒪(ε^{-3} log⁵ n log log n), where n is the size of the input. Finally, we provide a Ω(max(ε^{-1}, log n)) lower bound on the memory necessary to test visibly pushdown languages in the streaming model, significantly narrowing the gap between the known bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
Keywords
  • property testing
  • regular languages
  • streaming algorithms
  • visibly pushdown languages

Metrics

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

References

  1. 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, 2001. URL: https://doi.org/10.1137/S0097539700366528.
  2. Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma. Streaming algorithms for language recognition problems. Theoretical Computer Science, 494:13-23, 2013. Google Scholar
  3. Eldar Fischer, Frédéric Magniez, and Michael de Rougemont. Approximate satisfiability and equivalence. SIAM Journal on Computing, 39(6):2251-2281, 2010. Google Scholar
  4. Eldar Fischer, Frédéric Magniez, and Tatiana Starikovskaya. Improved bounds for testing Dyck languages. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1529-1544. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.100.
  5. Nathanaël François, Frédéric Magniez, Michel De Rougemont, and Olivier Serre. Streaming property testing of visibly pushdown languages. CoRR, abs/1505.03334, 2015. URL: http://arxiv.org/abs/1505.03334.
  6. 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, volume 57 of LIPIcs, pages 43:1-43:17, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.43.
  7. Moses Ganardi. Language recognition in the sliding window model. PhD thesis, University of Siegen, Germany, 2019. Google Scholar
  8. Moses Ganardi. Visibly pushdown languages over sliding windows. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, volume 126 of LIPIcs, pages 29:1-29:17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.29.
  9. Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras. Automata theory on sliding windows. In Proceedings of 35th International Symposium on Theoretical Aspects of Computer Science, volume 96 of LIPIcs, pages 31:1-31:14, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.31.
  10. 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, volume 65 of LIPIcs, pages 18:1-18:14, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.18.
  11. 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, volume 107 of LIPIcs, pages 127:1-127:13, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.127.
  12. Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding window property testing for regular languages. In Proceedings of the 30th International Symposium on Algorithms and Computation, volume 149 of LIPIcs, pages 6:1-6:13, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.6.
  13. Moses Ganardi, Artur Jeż, and Markus Lohrey. Sliding windows over context-free languages. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, volume 117 of LIPIcs, pages 15:1-15:15, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.15.
  14. 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.
  15. Bala Kalyanasundaram and Georg Schintger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545-557, 1992. Google Scholar
  16. 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, volume 6907 of LNCS, pages 412-423, 2011. Google Scholar
  17. Frédéric Magniez and Michel de Rougemont. Property testing of regular tree languages. Algorithmica, 49(2):127-146, 2007. URL: https://doi.org/10.1007/s00453-007-9028-3.
  18. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized expressions in the streaming model. SIAM J. Comput., 43(6):1880-1905, 2014. URL: https://doi.org/10.1137/130926122.
  19. Antoine Ndione, Aurélien Lemay, and Joachim Niehren. Approximate membership for regular languages modulo the edit distance. Theor. Comput. Sci., 487:37-49, 2013. URL: https://doi.org/10.1016/j.tcs.2013.03.004.
  20. Antoine Ndione, Aurélien Lemay, and Joachim Niehren. Sublinear DTD validity. In International Conference on Language and Automata Theory and Applications, volume 8977 of LNCS, pages 739-751, 2015. URL: https://doi.org/10.1007/978-3-319-15579-1_58.
  21. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Testing membership in parenthesis languages. Random Struct. Algorithms, 22(1):98-138, 2003. URL: https://doi.org/10.1002/rsa.10067.
  22. Michael O. Rabin. Probabilistic automata. Information and control, 6(3):230-245, 1963. Google Scholar
  23. Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pages 222-227, 1977. 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