M. Alon, I. Krivelevich, M. Newman, and . Szegedy, Regular languages are testable with a constant number of queries, SIAM Journal on Computing, vol.30, issue.6, 2000.

Y. Alon, M. Matias, and . Szegedy, The Space Complexity of Approximating the Frequency Moments, Journal of Computer and System Sciences, vol.58, issue.1, pp.137-147, 1999.
DOI : 10.1006/jcss.1997.1545

. Alur, Marrying words and trees, Proc. of 26th ACM Symposium on Principles of Database Systems, pp.233-242, 2007.

M. Alur, P. Arenas, K. Barceló, N. Etessami, L. Immerman et al., First-order and temporal logics for nested words, Proc. of 22nd IEEE Symposium on Logic in Computer Science, pp.151-160, 2007.

K. Alur, P. Etessami, and . Madhusudan, A Temporal Logic of Nested Calls and Returns, Proc. of 10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp.467-481, 2004.
DOI : 10.1007/978-3-540-24730-2_35

P. Alur and . Madhusudan, Adding nesting structure to words, Journal of the ACM, vol.56, issue.3, 2009.

N. Babu, G. Limaye, and . Varma, Streaming Algorithms for Some Problems in Log-Space
DOI : 10.1007/978-3-642-13562-0_10

W. Blum, P. Evans, S. Gemmell, M. Kannan, and . Naor, Checking the correctness of memories, Algorithmica, pp.90-99, 1995.

S. Blum and . Kannan, Designing programs that check their work, Journal of the ACM, vol.42, issue.1, pp.269-291, 1995.
DOI : 10.1145/200836.200880

M. Blum, R. Luby, and . Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, vol.47, issue.3, pp.549-59510, 1993.
DOI : 10.1016/0022-0000(93)90044-W

V. Braunmühl and R. Verbeek, Input-driven languages are recognized in log n space, Proc. of 4th Conference on Fundamentals of Computation Theory, pp.40-51, 1983.

S. Chu, A. Kannan, and . Mcgregor, Checking and Spot-Checking the Correctness of Priority Queues, Proc. of 34th International Colloquium on Automata, Languages and Programming, pp.728-739, 2007.
DOI : 10.1007/978-3-540-73420-8_63

. Dymond, Input-driven languages are in log n depth, Information Processing Letters, vol.26, issue.5, pp.247-250, 1988.
DOI : 10.1016/0020-0190(88)90148-2

S. Feigenbaum, M. Kannan, M. Strauss, and . Viswanathan, Testing and Spot-Checking of Data Streams, Algorithmica, vol.34, issue.1, pp.67-8010, 2002.
DOI : 10.1007/s00453-002-0959-4

F. Fischer, M. Magniez, and . De-rougemont, Approximate Satisfiability and Equivalence, SIAM Journal on Computing, vol.39, issue.6, pp.2251-2281, 2010.
DOI : 10.1137/070703776

S. Goldreich, D. Goldwasser, and . Ron, Property testing and its connection to learning and approximation, Proc. of 37th IEEE Symposium on Foundations of Computer Science, pp.339-348, 1996.

K. and F. Magniez, Validating XML documents in the streaming model with external memory, ACM Transactions on Database Systems, vol.38, issue.4, p.27, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00580814

. Libkin, Logics for unranked trees: An overview, Logical Methods in Computer Science, vol.2, issue.3, 2006.

M. Magniez and . De-rougemont, Property Testing of Regular Tree Languages, Algorithmica, vol.1, issue.4, pp.127-146, 2007.
DOI : 10.1007/s00453-007-9028-3

C. Magniez, A. Mathieu, and . Nayak, Recognizing Well-Parenthesized Expressions in the Streaming Model, SIAM Journal on Computing, vol.43, issue.6, pp.1880-1905, 2014.
DOI : 10.1137/130926122
URL : https://hal.archives-ouvertes.fr/hal-00639623

. Mehlorn, Pebbling mountain ranges and its application to DCFL-recognition, Proc. of 7th International Colloquium on Automata, Languages, and Programming, pp.422-435, 1980.
DOI : 10.1007/3-540-10003-2_89

. Muthukrishnan, Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, pp.117-23610, 2005.

A. Ndione, J. Lemay, and . Niehren, Approximate membership for regular languages modulo the edit distance, Theoretical Computer Science, vol.487, pp.37-49, 2013.
DOI : 10.1016/j.tcs.2013.03.004
URL : https://hal.archives-ouvertes.fr/hal-00801970

A. Ndione, J. Lemay, and . Niehren, Sublinear DTD Validity, Proc. of 19th International Conference on Language and Automata Theory and Applications, pp.739-751, 2015.
DOI : 10.1007/978-3-319-15579-1_58
URL : https://hal.archives-ouvertes.fr/hal-00803696

D. Parnas, R. Ron, and . Rubinfeld, Testing membership in parenthesis languages, Random Structures and Algorithms, vol.75, issue.1, pp.98-138, 2003.
DOI : 10.1002/rsa.10067

R. and P. Madhusudan, Visibly pushdown languages, Proc. of 36th ACM Symposium on Theory of Computing, pp.202-211, 2004.

C. Segoufin and . Sirangelo, Constant-Memory Validation of Streaming XML Documents Against DTDs, Proc. of 11th International Conference on Database Theory, pp.299-313, 2007.
DOI : 10.1007/11965893_21

V. Segoufin and . Vianu, Validating streaming XML documents, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '02, pp.53-64, 2002.
DOI : 10.1145/543613.543622