S. Abiteboul and V. Vianu, Regular Path Queries with Constraints, Journal of Computer and System Sciences, vol.58, issue.3, pp.428-452, 1999.
DOI : 10.1006/jcss.1999.1627
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.7172

L. Afanasiev, P. Blackburn, I. Dimitriou, B. Gaiffe, E. Goris et al., PDL for ordered trees, Journal of Applied Non-Classical Logics, vol.32, issue.2, pp.115-135, 2005.
DOI : 10.3166/jancl.15.115-135
URL : https://hal.archives-ouvertes.fr/inria-00001206

S. Amer-yahia, S. Cho, L. V. Lakshmanan, and D. Srivastava, Minimization of tree pattern queries, ACM SIGMOD Record, vol.30, issue.2, pp.497-508, 2001.
DOI : 10.1145/376284.375730

A. Arnold and D. Niwinski, Fixed point characterization of weak monadic logic definable sets of trees, Tree Automata and Languages, pp.159-188, 1992.

P. Barceló and L. Libkin, Temporal Logics over Unranked Trees, 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), pp.31-40, 2005.
DOI : 10.1109/LICS.2005.51

M. Benedikt, W. Fan, and F. Geerts, XPath satisfiability in the presence of DTDs, PODS '05: Proceedings of the twenty-fourth ACM Symposium on Principles of Database Systems, pp.25-36, 2005.

M. Benedikt, W. Fan, and G. M. Kuper, Structural properties of XPath fragments, Theoretical Computer Science, vol.336, issue.1, pp.3-31, 2005.
DOI : 10.1016/j.tcs.2004.10.030

M. Benedikt and L. Segoufin, Regular Tree Languages Definable in FO, STACS '05: Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, pp.327-339, 2005.
DOI : 10.1007/978-3-540-31856-9_27

J. Clark and S. Derose, XML path language (XPath) version 1.0, W3C recommendation, 1999.

E. M. Clarke and E. A. Emerson, Design and synthesis of synchronization skeletons using branching-time temporal logic, Logic of Programs, pp.52-71, 1981.

A. Deutsch and V. Tannen, Containment of regular path expressions under integrity constraints, KRDB '01: Proceedings of the 8th International Workshop on Knowledge Representation meets Databases CEUR Workshop Proceedings, pp.1-11, 2001.

J. Doner, Tree acceptors and some of their applications, Journal of Computer and System Sciences, vol.4, issue.5, pp.406-451, 1970.
DOI : 10.1016/S0022-0000(70)80041-1

D. Draper, P. Fankhauser, M. Fernández, A. Malhotra, K. Rose et al., XQuery 1.0 and XPath 2.0 formal semantics, W3C working draft, 2005.

W. Fan, C. Chan, and M. Garofalakis, Secure XML querying with security views, Proceedings of the 2004 ACM SIGMOD international conference on Management of data , SIGMOD '04, pp.587-598, 2004.
DOI : 10.1145/1007568.1007634
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.2679

M. J. Fischer and R. E. Ladner, Propositional dynamic logic of regular programs, Journal of Computer and System Sciences, vol.18, issue.2, pp.194-211, 1979.
DOI : 10.1016/0022-0000(79)90046-1

M. Franceschet, XPathMark: An XPath Benchmark for the XMark Generated Data, XSYM '05: Proceedings of The Third International Symposium on Database and XML Technologies, pp.129-143, 2005.
DOI : 10.1007/11547273_10

G. Gottlob and C. Koch, Monadic datalog and the expressive power of languages for web information extraction, PODS '02: Proceedings of the twenty-first ACM Symposium on Principles of Database Systems, pp.17-28, 2002.

G. Gottlob and C. Koch, Monadic queries over tree-structured data, Proceedings 17th Annual IEEE Symposium on Logic in Computer Science, pp.189-202, 2002.
DOI : 10.1109/LICS.2002.1029828
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.989

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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.4205

A. Grzegorczyk, Some classes of recursive functions, Rozprawy Matematyczne, vol.4, pp.1-45, 1953.

D. Kozen, Results on the propositional ??-calculus, Theoretical Computer Science, vol.27, issue.3, pp.333-354, 1983.
DOI : 10.1016/0304-3975(82)90125-6

D. Kozen, A finite model theorem for the propositional ?-calculus, Studia Logica, vol.64, issue.2, pp.233-241, 1988.
DOI : 10.1007/BF00370554

O. Kupferman and M. Vardi, The Weakness of Self-Complementation, Proc. 16th Symp. on Theoretical Aspects of Computer Science, pp.455-466, 1999.
DOI : 10.1007/3-540-49116-3_43

M. Y. Levin and B. C. Pierce, Type-Based Optimization for Regular Patterns, DBPL '05: Proceedings of the 10th International Symposium on Database Programming Languages, 2005.
DOI : 10.1007/11601524_12

W. Martens and F. Neven, Frontiers of tractability for typechecking simple XML transformations, PODS '04: Proceedings of the twenty-third ACM Symposium on Principles of Database Systems, pp.23-34, 2004.

M. Marx, Conditional XPath, the first order complete XPath dialect, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '04, pp.13-22, 2004.
DOI : 10.1145/1055558.1055562

M. Marx, XPath with Conditional Axis Relations, Proceedings of the 9th International Conference on Extending Database Technology, pp.477-494, 2004.
DOI : 10.1007/978-3-540-24741-8_28
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.7870

R. Mateescu, Local Model-Checking of Modal Mu-Calculus on Acyclic Labeled Transition Systems, TACAS '02: Proceedings of the 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp.281-295, 2002.
DOI : 10.1007/3-540-46002-0_20
URL : https://hal.archives-ouvertes.fr/inria-00072158

G. Miklau and D. Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM, vol.51, issue.1, pp.2-45, 2004.
DOI : 10.1145/962446.962448

F. Neven, Automata theory for XML researchers, ACM SIGMOD Record, vol.31, issue.3, pp.39-46, 2002.
DOI : 10.1145/601858.601869
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.907

F. Neven and T. Schwentick, XPath containment in the presence of disjunction, DTDs, and variables, ICDT '03: Proceedings of the 9th International Conference on Database Theory, pp.315-329, 2003.

T. Schwentick, XPath query containment, ACM SIGMOD Record, vol.33, issue.1, pp.101-109, 2004.
DOI : 10.1145/974121.974140

G. Sur, J. Hammer, and J. Siméon, Updatex -an XQuery-based language for processing updates in XML, PLAN-X 2004: Proceedings of the International Workshop on Programming Language Technologies for XML NS-03-4 of BRICS Notes Series, pp.40-53, 2004.

Y. Tanabe, K. Takahashi, M. Yamamoto, A. Tozawa, and M. Hagiya, A Decision Procedure for the Alternation-Free Two-Way Modal ??-Calculus, TABLEAUX '05: Proceedings of the 14th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, pp.277-291, 2005.
DOI : 10.1007/11554554_21

J. W. Thatcher and J. B. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic, Mathematical Systems Theory, vol.12, issue.1, pp.57-81, 1968.
DOI : 10.1007/BF01691346

A. Tozawa, Towards static type checking for XSLT, Proceedings of the 2001 ACM Symposium on Document engineering , DocEng '01, pp.18-27, 2001.
DOI : 10.1145/502187.502191

M. Y. Vardi, Reasoning about the past with two-way automata, ICALP '98: Proceedings of the 25th International Colloquium on Automata, Languages and Programming, pp.628-641, 1998.
DOI : 10.1007/BFb0055090

P. Wadler, Two semantics for XPath Internal Technical Note of the W3C XSL Working Group, 2000.

P. T. Wood, On the Equivalence of XML Patterns, CL '00: Proceedings of the First International Conference on Computational Logic, pp.1152-1166, 2000.
DOI : 10.1007/3-540-44957-4_77

P. T. Wood, Containment for XPath Fragments under DTD Constraints, ICDT '03: Proceedings of the 9th International Conference on Database Theory, pp.300-314, 2003.
DOI : 10.1007/3-540-36285-1_20
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.3975