Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-30T19:54:31.087Z Has data issue: false hasContentIssue false

Bibliography

Published online by Cambridge University Press:  01 June 2011

Edited by
Javier Esparza ,
Christian Michaux  and
Charles Steinhorn
Javier Esparza
Affiliation:
Technische Universität München
Christian Michaux
Affiliation:
Université de Mons, Belgium
Charles Steinhorn
Affiliation:
Vassar College, New York
Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'
Type
Chapter
Information
Finite and Algorithmic Model Theory , pp. 339 - 341
Publisher: Cambridge University Press
Print publication year: 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Alon, N. 1995. Tools from Higher Algebra. Pages 1749–1783 of: Graham, R., Grötschel, M., and Lovasz, L. (eds), Handbook of Combinatorics, vol. II. North-Holland.Google Scholar
[2] Andréka, H., van Benthem, J., and Németi, I. 1998. Modal Languages and Bounded Fragments of Predicate Logic. Journal of Philosophical Logic, 27, 217–274.CrossRefGoogle Scholar
[3] Atserias, A., Dawar, A., and Grohe, M. 2005. Preservation under extensions on well-behaved finite structures. Pages 1437–1449 of: Proceedings of 32nd International Colloquium on Automata, Languages and Programming ICALP'05. LNCS, vol. 3580.CrossRefGoogle Scholar
[4] Atserias, A., Dawar, A., and Kolaitis, P. 2006. On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM, 53, 208–237.CrossRefGoogle Scholar
[5] Barany, V., Gottlob, G., and Otto, M. 2010. Querying the guarded fragment. Pages 2–11 of: Proceedings of 25th Annual IEEE Symposium on Logic in Computer Science LICS'10.Google Scholar
[6] Beeri, C., Fagin, R., Maier, D., and Yannakakis, M. 1983. On the desirability of acyclic database schemes. Journal of the ACM, 30, 497–513.CrossRefGoogle Scholar
[7] Berge, C. 1973. Graphs and Hypergraphs. North-Holland.Google Scholar
[8] Berwanger, D., and Grädel, E. 2001. Games and Model Checking for Guarded Logics. Pages 70–84 of: Proceedings of the 8th International Conference on Logic for Programming and Automated Reasoning LPAR'01. LNCS, vol. 2250.Google Scholar
[9] Blackburn, P., de Rijke, M., and Venema, Y. 2001. Modal Logic. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press.CrossRefGoogle Scholar
[10] Blackburn, P., van Benthem, J., and Wolter, F. (eds). 2007. Handbook of Modal Logic. Elsevier.Google Scholar
[11] Chang, C. C., and Keisler, H. J. 1990. Model Theory. North-Holland.Google Scholar
[12] Courcelle, B. 1990. Graph rewriting: An algebraic and logic approach. Pages 194–242 of: van Leeuwen, J. (ed), Handbok of Theoretical Computer Science, volume B. Elsevier.Google Scholar
[13] Dalmau, V., Kolaitis, P., and Vardi, M. 2002. Constraint satisfaction, bounded treewidth, and finite-varaible logics. Pages 310–326 of: Proceedings of 8th International Conference on Constraint Programming. LNCS, vol. 2470.Google Scholar
[14] Dawar, A., and Otto, M. 2009. Modal characterisation theorems over special classes of frames. Annals of Pure and Applied Logic, 161, 1–42. Extended journal version of LICS'05 paper.CrossRefGoogle Scholar
[15] Ebbinghaus, H.-D., and Flum, J. 1999. Finite Model Theory. 2nd edn. Springer.Google Scholar
[16] Frick, M., and Grohe, M. 2001. Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM, 48, 1184–1206.CrossRefGoogle Scholar
[17] Goranko, V., and Otto, M. 2007. Model Theory of Modal Logic. Pages 249–329 of: Blackburn, P., van Benthem, J., and Wolter, F. (eds), Handbook of Modal Logic. Elsevier.CrossRefGoogle Scholar
[18] Gottlob, G., Leone, N., and Scarcello, F. 2001. The complexity of acyclic conjunctive queries. Journal of the ACM, 43, 431–498.CrossRefGoogle Scholar
[19] Gottlob, G., Grädel, E., and Veith, H. 2002a. Datalog LITE: A deductive query language with linear time model checking. ACM Transactions on Computational Logic, 3, 1–35.CrossRefGoogle Scholar
[20] Gottlob, G., Leone, N., and Scarcello, F. 2002b. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64, 579–627.CrossRefGoogle Scholar
[21] Grädel, E. 1999. On the restraining power of guards. Journal of Symbolic Logic, 64, 1719–1742.CrossRefGoogle Scholar
[22] Grädel, E. 2007. Finite model theory and descriptive complexity. Pages 125–230 of: Finite Model Theory and Its Applications. Springer.CrossRefGoogle Scholar
[23] Grädel, E., and Otto, M. 1999. On Logics with Two Variables. Theoretical Computer Science, 224, 73–113.CrossRefGoogle Scholar
[24] Grädel, E., and Walukiewicz, I. 1999. Guarded fixed point logic. Pages 45–54 of: Proceedings of 14th Annual IEEE Symposium on Logic in Computer Science LICS'99.Google Scholar
[25] Grädel, E., Hirsch, C., and Otto, M. 2002. Back and forth between guarded and modal logics. ACM Transactions on Computational Logics, 3, 418–463.CrossRefGoogle Scholar
[26] Grohe, M. 2008. Logic, graphs, and algorithms. Pages 357–422 of: Flum, J., Grädel, E., and Wilke, T. (eds), Logic and Automata, History and Perspectives. Amsterdam University Press.Google Scholar
[27] Herwig, B. 1995. Extending partial isomorphisms on finite structures. Combinatorica, 15, 365–371.CrossRefGoogle Scholar
[28] Herwig, B. 1998. Extending partial isomorphisms for the small index property of many omega-categorical structures. Israel Journal of Mathematics, 107, 93–124.CrossRefGoogle Scholar
[29] Herwig, B., and Lascar, D. 2000. Extending partial isomorphisms and the profinite topology on free groups. Transactions of the AMS, 352, 1985–2021.CrossRefGoogle Scholar
[30] Hodges, W. 1993. Model Theory. Cambridge University Press.CrossRefGoogle Scholar
[31] Hodkinson, I., and Otto, M. 2003. Finite conformal hypergraph covers and Gaifman cliques in finite structures. Bulletin of Symbolic Logic, 9, 387–405.CrossRefGoogle Scholar
[32] Hoogland, E., Marx, M., and Otto, M. 1999. Beth definability for the guarded fragment. In: Gebrandy, J., Marx, M., de Rijke, M., and Venema, Y. (eds), JFAK – Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday. Amsterdam University Press. CD-ROM.Google Scholar
[33] Immerman, N. 1998. Decsriptive Complexity. Graduate Texts in Computer Science. Springer.Google Scholar
[34] Janin, D., and Walukiewicz, I. 1996. On the Expressive Completeness of the Propositional mu-Calculus with Respect to Monadic Second Order Logic. Pages 263–277 of: Proceedings of 7th International Conference on Concurrency Theory CONCUR'96. LNCS, vol. 1119.CrossRefGoogle Scholar
[35] Kolaitis, P. 2007. On the expressive power of logics on finite models. Pages 27–123 of: Finite Model Theory and Its Applications. Springer.CrossRefGoogle Scholar
[36] Kolaitis, P., and Vardi, M. 2000a. Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences, 61, 302–332.CrossRefGoogle Scholar
[37] Kolaitis, P., and Vardi, M. 2000b. A game-theoretic approach to constraint satisfaction. Pages 175–181 of: Proceedings of Of 17th Conference on Artificial Intelligence AAAI'00.Google Scholar
[38] Kolaitis, P., and Vardi, M. 2007. A logical approach to constraint satisfaction. Pages 339–370 of: Finite Model Theory and Its Applications. Springer.CrossRefGoogle Scholar
[39] Kreutzer, S. 2008. Algorithmic Meta-Theorems. In: Esparza, J., Michaux, C., and Steinhorn, C. (eds), Finite and Algorithmic Model Theory. CUP. (this volume).Google Scholar
[40] Lorenz, K. 1968. Dialogspiele als semantische Grundlage von Logikkalkülen. Archiv für Mathematische Logik und Grundlagenforschung, 11, 32–55 and 73–100.CrossRefGoogle Scholar
[41] Lorenzen, P. 1961. Ein dialogisches Konstruktivitätskriterium. Pages 193–200 of: Infinitistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warsaw 1959. Oxford University Press.Google Scholar
[42] Otto, M. 2004. Modal and guarded characterisation theorems over finite transition systems. Annals of Pure and Applied Logic, 130, 173–205.CrossRefGoogle Scholar
[43] Otto, M. 2010a. Highly acyclic groups, hypergraph covers and the guarded fragment. Pages 12–21 of: Proceedings of 25th Annual IEEE Symposium on Logic in Computer Science LICS'10.Google Scholar
[44] Otto, M. 2010b. Highly acyclic groups, hypergraph covers and the guarded fragment. Draft of extended version of LICS 2010 paper.
[45] Rabin, M. 1969. Decidability of second order theories and automata on infinite trees. Transactions of the AMS, 141, 1–35.Google Scholar
[46] Rosen, E. 1997. Modal logic over finite structures. Journal of Logic, Language and Information, 6, 427–439.CrossRefGoogle Scholar
[47] Rossman, B. 2008. Homomorphism preservation theorems. Journal of the ACM, 55.CrossRefGoogle Scholar
[48] Vardi, M. 1995. On the complexity of bounded-variable queries. Pages 266–276 of: Proceedings of 14th Annual ACM Symposium on Principles of Database Systems PODS'95.Google Scholar
[49] Vardi, M. 1997. Why is modal logic so robustly decidable? Pages 149–184 of: Immerman, N., and Kolaitis, P. (eds), Descriptive Complexity and Finite Models. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 31. AMS.CrossRefGoogle Scholar
[50] Vardi, M. 2006. Games as an algorithmic construct. Tutorial, Isaac Newton Institute workshop on Games and Verification (Logic and Algorithms programme).Google Scholar
[51] Weinstein, S. 2007. Unifying themes in finite model theory. Pages 1–25 of: Finite Model Theory and Its Applications. Springer.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×