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

J. Baget, M. Leclère, M. Mugnier, and E. Salvat, On rules with existential variables: Walking the decidability line, Artificial Intelligence, vol.175, issue.9-10, pp.9-101620, 2011.
DOI : 10.1016/j.artint.2011.03.002
URL : https://hal.archives-ouvertes.fr/lirmm-00587012

V. Bárány, B. Cate, and M. Otto, Queries with guarded negation, pp.1328-1339, 2012.

V. Bárány, B. Cate, and L. Segoufin, Guarded Negation, Lecture Notes in Computer Science, vol.21, issue.8, pp.356-367
DOI : 10.1002/malq.19750210118

M. Benedikt, P. Bourhis, and P. Senellart, Monadic Datalog Containment, Automata, Languages, and Programming -39th International Colloquium, ICALP 2012, pp.79-91, 2012.
DOI : 10.1007/978-3-642-31585-5_11
URL : https://hal.archives-ouvertes.fr/hal-00809306

H. Björklund, W. Martens, and T. Schwentick, Optimizing Conjunctive Queries over Trees Using Schema Information, Proc. 3rdInt. Symposium on Mathematical Foundations of Computer Science, pp.132-143, 2008.
DOI : 10.1007/978-3-540-85238-4_10

A. Calì, G. Gottlob, and M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints, Proc. 11th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR'08), pp.70-80, 2008.

D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Y. Vardi, Reasoning on regular path queries, ACM SIGMOD Record, vol.32, issue.4, pp.83-92, 2003.
DOI : 10.1145/959060.959076

D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Y. Vardi, Reasoning on regular path queries, ACM SIGMOD Record, vol.32, issue.4, pp.83-92, 2003.
DOI : 10.1145/959060.959076

D. Calvanese, G. D. Giacomo, and M. Y. Vardi, Decidable containment of recursive queries, Theoretical Computer Science, vol.336, issue.1, pp.33-56, 2005.
DOI : 10.1016/j.tcs.2004.10.031

A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer, Alternation, Journal of the ACM, vol.28, issue.1, pp.114-133, 1981.
DOI : 10.1145/322234.322243

S. Chaudhuri and M. Y. Vardi, On the complexity of equivalence between recursive and nonrecursive Datalog programs, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems , PODS '94, pp.107-116, 1994.
DOI : 10.1145/182591.182604

S. Chaudhuri and M. Y. Vardi, On the Equivalence of Recursive and Nonrecursive Datalog Programs, Journal of Computer and System Sciences, vol.54, issue.1, pp.61-78, 1997.
DOI : 10.1006/jcss.1997.1452

S. Cosmadakis, H. Gaifman, P. Kanellakis, and M. Vardi, Decidable optimization problems for database logic programs, Proceedings of the twentieth annual ACM symposium on Theory of computing , STOC '88, pp.477-490, 1988.
DOI : 10.1145/62212.62259

B. Courcelle, Recursive queries and context-free graph grammars, Theoretical Computer Science, vol.78, issue.1, pp.217-244, 1991.
DOI : 10.1016/0304-3975(51)90009-6

A. Deutsch and V. Tannen, Optimization Properties for Classes of Conjunctive Regular Path Queries, Revised Papers from the 8th International Workshop on Database Programming Languages, DBPL '01, pp.21-39, 2002.
DOI : 10.1007/3-540-46093-4_2

D. Florescu, A. Levy, and D. Suciu, Query containment for conjunctive queries with regular expressions, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems , PODS '98, pp.139-148, 1998.
DOI : 10.1145/275487.275503

S. Rudolph and M. Krötzsch, Flag & check, Proceedings of the 32nd symposium on Principles of database systems, PODS '13, pp.151-162, 2013.
DOI : 10.1145/2463664.2465227

W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences, vol.4, issue.2, pp.177-192, 1970.
DOI : 10.1016/S0022-0000(70)80006-X

O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems , PODS '87, pp.237-249, 1987.
DOI : 10.1145/28659.28685