R. Alur, Marrying words and trees, 26th ACM SIGMOD-SIGACT- SIGART Symposium on Principles of Database Systems, pp.233-242
DOI : 10.1007/978-3-540-74510-5_3
URL : http://repository.upenn.edu/cgi/viewcontent.cgi?article=1549&context=cis_papers

R. Alur and P. Madhusudan, Visibly pushdown languages, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , STOC '04, pp.202-211, 2004.
DOI : 10.1145/1007352.1007390
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.3757

R. Alur and P. Madhusudan, Adding nesting structure to words, Journal of the ACM, vol.56, issue.3, pp.1-43, 2009.
DOI : 10.1145/1516512.1516518

Z. Bar-yossef, M. Fontoura, and V. Josifovski, Buffering in query evaluation over XML streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '05, pp.216-227, 2005.
DOI : 10.1145/1065167.1065195

Z. Bar-yossef, M. Fontoura, and V. Josifovski, On the memory requirements of XPath evaluation over XML streams, Journal of Computer and System Sciences, vol.73, issue.3, pp.391-441, 2007.
DOI : 10.1016/j.jcss.2006.10.002

C. Barton, P. Charles, D. Goyal, M. Raghavachari, M. Fontoura et al., Streaming XPath processing with forward and backward axes, Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405), pp.455-466, 2003.
DOI : 10.1109/ICDE.2003.1260813

M. Benedikt and A. Jeffrey, Efficient and Expressive Tree Filters, Foundations of Software Technology and Theoretical Computer Science, pp.461-472, 2007.
DOI : 10.1007/978-3-540-77050-3_38

M. Benedikt, A. Jeffrey, and R. Ley-wild, Stream firewalling of xml constraints, Proceedings of the 2008 ACM SIGMOD international conference on Management of data , SIGMOD '08, pp.487-498, 2008.
DOI : 10.1145/1376616.1376667

M. Benedikt and L. Libkin, Tree extension algebras: logics, automata, and query languages, Proceedings 17th Annual IEEE Symposium on Logic in Computer Science, pp.203-214, 2002.
DOI : 10.1109/LICS.2002.1029829

M. Benedikt, L. Libkin, and F. Neven, Logical definability and query languages over ranked and unranked trees, ACM Transactions on Computational Logic, vol.8, issue.2, 2007.
DOI : 10.1145/1227839.1227843
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.367.1110

A. Berlea, Online evaluation of regular tree queries, Nordic Journal of Computing, vol.13, issue.4, pp.1-26, 2006.

T. Bray, J. Paoli, C. M. Sperberg-mcqueen, E. Maler, and F. Yergeau, Extensible markup language (xml) 1, 2006.

J. Carme, A. Lemay, and J. Niehren, Learning Node Selecting Tree Transducer from Completely Annotated Examples, 7th International Colloquium on Grammatical Inference, pp.91-102, 2004.
DOI : 10.1007/978-3-540-30195-0_9
URL : https://hal.archives-ouvertes.fr/inria-00536528

J. Carme, J. Niehren, and M. Tommasi, Querying Unranked Trees with Stepwise Tree Automata, 19th International Conference on Rewriting Techniques and Applications, pp.105-118, 2004.
DOI : 10.1007/978-3-540-25979-4_8
URL : https://hal.archives-ouvertes.fr/inria-00536529

S. Ceri, G. Gottlob, and L. Tanca, What you always wanted to know about Datalog (and never dared to ask), IEEE Transactions on Knowledge and Data Engineering, vol.1, issue.1, pp.146-166, 1989.
DOI : 10.1109/69.43410

J. Champavère, R. Gilleron, A. Lemay, and J. Niehren, Efficient inclusion checking for deterministic tree automata and XML Schemas, Information and Computation, vol.207, issue.11, pp.1181-1208
DOI : 10.1016/j.ic.2009.03.003

Y. Chen, S. B. Davidson, and Y. Zheng, An Efficient XPath Query Processor for XML Streams, 22nd International Conference on Data Engineering, p.79, 2006.

H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard et al., Tree automata techniques and applications. Available online since, 1997.

E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys, vol.33, issue.3, pp.374-425, 2001.
DOI : 10.1145/502807.502810

M. Dauchet and S. Tison, The theory of ground rewrite systems is decidable, [1990] Proceedings. Fifth Annual IEEE Symposium on Logic in Computer Science, pp.242-248, 1990.
DOI : 10.1109/LICS.1990.113750

M. Fernandez, P. Michiels, J. Siméon, and M. Stark, XQuery streamingàstreamingà la carte, 23nd International Conference on Data Engineering, pp.256-265, 2007.
DOI : 10.1109/icde.2007.367871
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.128.2202

E. Filiot, J. Raskin, P. Reynier, F. Servais, and J. Talbot, Properties of Visibly Pushdown Transducers, 35th International Symposium on Mathematical Foundations of Computer Science (MFCS'10, 2010.
DOI : 10.1007/978-3-642-15155-2_32
URL : https://hal.archives-ouvertes.fr/inria-00492241

M. Frick, M. Grohe, and C. Koch, Query evaluation on compressed trees, 18th Annual IEEE Symposium of Logic in Computer Science, 2003. Proceedings., pp.188-197, 2003.
DOI : 10.1109/LICS.2003.1210058
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.127.5196

O. Gauwin, Streaming Tree Automata and XPath, 2009.
DOI : 10.1016/j.ipl.2008.08.002
URL : https://hal.archives-ouvertes.fr/tel-00421911

O. Gauwin and J. Niehren, Streamable Fragments of Forward XPath, 2010.
DOI : 10.1007/11965893_1
URL : https://hal.archives-ouvertes.fr/inria-00442250

O. Gauwin, J. Niehren, and Y. Roos, Streaming tree automata, Information Processing Letters, vol.109, issue.1, pp.13-17, 2008.
DOI : 10.1016/j.ipl.2008.08.002
URL : https://hal.archives-ouvertes.fr/inria-00288445

O. Gauwin, J. Niehren, and S. Tison, Bounded Delay and Concurrency for Earliest Query Answering, 3rd International Conference on Language and Automata Theory and Applications, pp.350-361, 2009.
DOI : 10.1007/978-3-540-30195-0_9
URL : https://hal.archives-ouvertes.fr/inria-00348463

O. Gauwin, J. Niehren, and S. Tison, Earliest??Query??Answering for Deterministic Nested Word Automata, 17th International Symposium on Fundamentals of Computer Theory, pp.121-132, 2009.
DOI : 10.1007/978-3-642-03409-1_12
URL : https://hal.archives-ouvertes.fr/inria-00390236

G. Gottlob, E. Gr, and H. Veith, Datalog LITE: a deductive query language with linear time model checking, ACM Transactions on Computational Logic, vol.3, issue.1, pp.42-79, 2002.
DOI : 10.1145/504077.504079

G. Gottlob, C. Koch, and R. Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems, vol.30, issue.2, pp.444-491, 2005.
DOI : 10.1145/1071610.1071614

G. Gou and R. Chirkova, Efficient algorithms for evaluating xpath over streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data , SIGMOD '07, pp.269-280, 2007.
DOI : 10.1145/1247480.1247512

A. Kumar, G. , and D. Suciu, Stream processing of XPath queries with predicates, SIGMOD '03: Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pp.419-430, 2003.

V. Josifovski, M. Fontoura, and A. Barta, Querying XML streams, The VLDB Journal, vol.11, issue.2, pp.197-210, 2005.
DOI : 10.1007/s00778-004-0123-7

C. Koch, Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage, Proc. VLDB 2003, 2003.
DOI : 10.1016/B978-012722442-8/50030-6

W. Martens, F. Neven, T. Schwentick, and G. J. Bex, Expressiveness and complexity of XML Schema, ACM Transactions on Database Systems, vol.31, issue.3, pp.770-813, 2006.
DOI : 10.1145/1166074.1166076

W. Martens and J. Niehren, On the minimization of XML Schemas and tree automata for unranked trees, Journal of Computer and System Sciences, vol.73, issue.4, pp.550-583, 2007.
DOI : 10.1016/j.jcss.2006.10.021
URL : https://hal.archives-ouvertes.fr/inria-00088406

M. Murata, D. Lee, and M. Mani, Taxonomy of XML schema languages using formal language theory, Extreme Markup Languages, 2001.
DOI : 10.1145/1111627.1111631

A. Neumann and H. Seidl, Locating Matches of Tree Patterns in Forests, Foundations of Software Technology and Theoretical Computer Science, pp.134-145, 1998.
DOI : 10.1007/978-3-540-49382-2_12

J. Niehren, L. Planque, J. Talbot, and S. Tison, N-Ary Queries by Tree Automata, 10th International Symposium on Database Programming Languages, pp.217-231, 2005.
DOI : 10.1007/11601524_14
URL : https://hal.archives-ouvertes.fr/inria-00536522

A. Nizar and S. Kumar, Efficient Evaluation of Forward XPath Axes over XML Streams, 14th International Conference on Management of Data (COMAD), pp.222-233, 2008.

D. Olteanu, SPEX: Streamed and Progressive Evaluation of XPath, IEEE Transactions on Knowledge and Data Engineering, vol.19, issue.7, pp.934-949, 2007.
DOI : 10.1109/TKDE.2007.1063

P. Parys, XPath evaluation in linear time with polynomial combined complexity, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS '09, pp.55-64, 2009.
DOI : 10.1145/1559795.1559805

F. Peng and S. S. Chawathe, XSQ, ACM Transactions on Database Systems, vol.30, issue.2, pp.577-623, 2005.
DOI : 10.1145/1071610.1071617

M. O. Rabin, Decidability of Second-Order Theories and Automata on Infinite Trees. Transactions of the, pp.1-35, 1969.

P. Ramanan, Worst-case optimal algorithm for XPath evaluation over XML streams, Journal of Computer and System Sciences, vol.75, issue.8, pp.465-485, 2009.
DOI : 10.1016/j.jcss.2009.06.001

J. Raskin and F. Servais, Visibly Pushdown Transducers, Automata, Languages and Programming, 35th International Colloquium, pp.386-397, 2008.
DOI : 10.1007/978-3-540-70583-3_32
URL : https://hal.archives-ouvertes.fr/inria-00492241

J. Sakarovitch and R. Souza, On the Decidability of Bounded Valuedness for Transducers, Mathematical Foundations of Computer Science, 2008.
DOI : 10.1007/978-3-540-85238-4_48

L. Segoufin and V. 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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.6403

H. Seidl, Deciding equivalence of finite tree automata, Annual Symposium on Theoretical Aspects of Computer Science, pp.480-492, 1989.
DOI : 10.1007/BFb0029009

H. Seidl, On the finite degree of ambiguity of finite tree automata, Acta Informatica, vol.26, issue.6, pp.527-542, 1989.

H. Seidl, Single-valuedness of tree transducers is decidable in polynomial time, Theoretical Computer Science, vol.106, issue.1, pp.135-181, 1992.
DOI : 10.1016/0304-3975(92)90281-J

H. Seidl, Equivalence of finite-valued tree transducers is decidable, Mathematical Systems Theory, vol.4, issue.4, pp.285-346, 1994.
DOI : 10.1007/BF01192143

H. Seidl, Haskell overloading is DEXPTIME-complete, Information Processing Letters, vol.52, issue.2, pp.57-60, 1994.
DOI : 10.1016/0020-0190(94)00130-8
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.119.8086

R. E. Stearns, H. B. Hunt, and I. , On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata, SIAM Journal on Computing, vol.14, issue.3, pp.598-611, 1985.
DOI : 10.1137/0214044

S. Tison, Automates Comme Outils de Décision dans les Arbres. Thèse d'habilitation, Laboratoire d, 1990.

A. Weber and H. Seidl, On the degree of ambiguity of finite automata, In Mathematical Foundations of Computer Science Lecture Notes in Computer Science, vol.233, pp.620-629, 1986.
DOI : 10.1007/BFb0016289

X. Wu and D. Theodoratos, Evaluating partial tree-pattern queries on XML streams, Proceeding of the 17th ACM conference on Information and knowledge mining, CIKM '08, pp.1409-1410, 2008.
DOI : 10.1145/1458082.1458305