H. Andréka, J. Van-benthem, and I. Németi, Modal Languages and Bounded Fragments of Predicate Logic, Journal of Philosophical Logic, vol.60, issue.5, pp.217-274, 1998.
DOI : 10.1023/A:1004275029985

F. Baader, D. Calvanese, D. L. Mcguinness, D. Nardi, and P. F. Patel-schneider, The Description Logic Handbook: Theory, Implementation, and Applications, 2003.
DOI : 10.1017/CBO9780511711787

J. Bailey, G. Dong, and A. W. To, Logical queries over views, ACM Transactions on Computational Logic, vol.11, issue.2, p.8, 2010.
DOI : 10.1145/1656242.1656243

V. Bárány and M. Boja´nczykboja´nczyk, Finite satisfiability for guarded fixpoint logic, Information Processing Letters, vol.112, issue.10, pp.371-375, 2012.
DOI : 10.1016/j.ipl.2012.02.005

V. Bárány, B. Cate, and L. Segoufin, Guarded negation, Intl. Coll. on Automata, Languages and Programming (ICALP), pp.356-367, 2011.

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

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

J. Van-benthem, Modal Logic and Classical Logic, Bibliopolis, 1983.

D. Berwanger and E. Grädel, Games and Model Checking for Guarded Logics, Intl. Conf. on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), pp.70-84, 2001.
DOI : 10.1007/3-540-45653-8_5

P. Blackburn, M. De-rijke, and Y. Venema, Modal Logic. Cambridge Tracts in Theoretical Computer Science, 2002.
URL : https://hal.archives-ouvertes.fr/inria-00100502

M. Boja´nczykboja´nczyk, Two-way alternating automata and finite models, In Intl. Coll. on Automata, Languages and Programming, pp.833-844, 2002.

E. Börger, E. Grädel, and Y. Gurevich, The Classical Decision Problem, 1997.
DOI : 10.1007/978-3-642-59207-2

S. R. Buss and H. Louise, On truth-table reducibility to SAT, Information and Computation, vol.91, issue.1, pp.86-102, 1991.
DOI : 10.1016/0890-5401(91)90075-D

J. Castro and C. Seara, Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, RAIRO - Theoretical Informatics and Applications, vol.30, issue.2, pp.101-121, 1996.
DOI : 10.1051/ita/1996300201011

B. Cate, The expressivity of XPath with transitive closure, Symp. on Principles of Database Systems (PODS), pp.328-337, 2006.

B. Cate and M. Marx, Navigational XPath, ACM SIGMOD Record, vol.36, issue.2, pp.19-26, 2007.
DOI : 10.1145/1328854.1328858

B. Cate and L. Segoufin, Unary negation, Intl. Symp. on Theoretical Aspects of Computer Science (STACS), pp.344-355, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00573634

C. C. Chang and H. J. Keisler, Model Theory. Studies in Logic and the Foundations of Mathematics, 1990.

E. M. Clarke, O. Grumberg, and D. A. , Peled. Model checking, 1999.

S. Cosmadakis, H. Gaifman, P. Kanellakis, and M. Y. 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

M. Fisher and R. 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

G. Gottlob, NP trees and Carnap's modal logic, Journal of the ACM, vol.42, issue.2, pp.421-457, 1995.
DOI : 10.1145/201019.201031

G. Gottlob and C. Koch, Monadic datalog and the expressive power of languages for Web information extraction, Journal of the ACM, vol.51, issue.1, pp.74-113, 2004.
DOI : 10.1145/962446.962450

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. Gottlob, C. Koch, and K. Schulz, Conjunctive queries over trees, Symp. Principles of Database Systems (PODS), pp.189-200, 2004.
DOI : 10.1145/1055558.1055585
URL : http://arxiv.org/abs/cs/0602004

E. Grädel and I. Walukiewicz, Guarded fixed point logic, Proceedings. 14th Symposium on Logic in Computer Science (Cat. No. PR00158), pp.45-54, 1999.
DOI : 10.1109/LICS.1999.782585

W. Hodges, Model Theory, 1993.
DOI : 10.1017/CBO9780511551574

E. Hoogland and M. Marx, Interpolation and definability in guarded fragments, Studia Logica, vol.70, issue.3, pp.373-409, 2002.
DOI : 10.1023/A:1015154431342

D. Janin and I. Walukiewicz, On the expressive completeness of the propositional µ-calculus w.r.t. monadic second-order logic, Intl. Conf. on Concurrency Theory (CONCUR), 1996.

D. Kozen, Results on the Propositional ??-Calculus, DAIMI Report Series, vol.11, issue.146, pp.333-354, 1983.
DOI : 10.7146/dpb.v11i146.7420

L. Libkin, Elements of Finite Model Theory, 2004.
DOI : 10.1007/978-3-662-07003-1

C. Lutz, The Complexity of Conjunctive Query Answering in Expressive Description Logics, Intl. Joint Conf. on Automated Reasoning (IJCAR), pp.179-193, 2008.
DOI : 10.1007/978-3-540-71070-7_16

M. Marx and M. De-rijke, Semantic characterizations of navigational XPath, ACM SIGMOD Record, vol.34, issue.2, pp.41-46, 2005.
DOI : 10.1145/1083784.1083792

D. Niwinski, On fixed-point clones, In Intl. Coll. on Automata, Languages and Programming, pp.464-473, 1986.
DOI : 10.1007/3-540-16761-7_96

M. Otto, Modal and guarded characterisation theorems over finite transition systems, Annals of Pure and Applied Logic, vol.130, issue.1-3, pp.173-205, 2004.
DOI : 10.1016/j.apal.2004.04.003
URL : http://doi.org/10.1016/j.apal.2004.04.003

M. Otto, Highly acyclic groups, hypergraph covers, and the guarded fragment, J. ACM, vol.59, issue.1, p.5, 2012.

T. Place and L. Segoufin, A decidable characterization of locally testable tree languages, Intl. Coll. on Automata, Languages and Programming (ICALP), pp.285-296, 2009.

E. Rosen, Modal logic over finite structures, Journal of Logic, Language and Information, vol.6, issue.4, pp.427-439, 1997.
DOI : 10.1023/A:1008275906015

P. Schnoebelen, Oracle Circuits for Branching-Time Model Checking, In Intl. Coll. on Automata, Languages and Programming, pp.187-187, 2003.
DOI : 10.1007/3-540-45061-0_62

O. Shmueli, Equivalence of Datalog queries is undecidable, The Journal of Logic Programming, vol.15, issue.3, pp.231-241, 1993.
DOI : 10.1016/0743-1066(93)90040-N

R. S. Streett, Propositional Dynamic Logic of looping and converse, Proceedings of the thirteenth annual ACM symposium on Theory of computing , STOC '81, pp.121-141, 1982.
DOI : 10.1145/800076.802492

M. Y. Vardi, On the complexity of bounded-variable queries, Symp. on Principles of Database Systems (PODS), pp.266-276, 1995.

M. Y. Vardi, Why is modal logic so robustly decidable? In Descriptive Complexity and Finite Models, pp.149-184, 1996.

M. Y. Vardi, Reasoning about the past with two-way automata, Intl. Coll. on Automata, Languages and Programming (ICALP), pp.628-641, 1998.
DOI : 10.1007/BFb0055090

K. W. Wagner, More complicated questions about maxima and minima, and some closures of NP, Theoretical Computer Science, vol.51, issue.1-2, pp.53-80, 1987.
DOI : 10.1016/0304-3975(87)90049-1