Finite Model Theory
Springer (2005)
| Abstract | The book presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logics that are important in this context include fixed-point logics, transitive closure logics, and also certain infinitary languages; their model theory is studied in full detail. Other topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems. The book is written in such a way that the respective parts on model theory and descriptive complexity theory may be read independently. This second edition is a thoroughly revised and enlarged version of the original text | |||||||||
| Keywords | complexity computational descriptive finite generalized model quantifiers theory | |||||||||
| Categories | ||||||||||
| Buy the book | $92.67 direct from Amazon (23% off) Amazon page | |||||||||
| ISBN(s) | 3540287876 9783540287872 | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,631 |
| External links |
  Try with proxy. Try with proxy. |
| Through your library | Configure |
Similar books and articlesLauri Hella, Phokion G. Kolaitis & Kerkko Luosto (1996). Almost Everywhere Equivalence of Logics in Finite Model Theory. Bulletin of Symbolic Logic 2 (4):422-443.
Marcin Mostowski (1998). Computational Semantics for Monadic Quantifiers. Journal of Applied Non--Classical Logics 8:107--121.
Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. The Bulletin of Symbolic Logic 13:281--282.
Jakub Szymanik & Marcin Zajenkowski (2009). Comprehension of Simple Quantifiers. Empirical Evaluation of a Computational Model. Cognitive Science: A Multidisciplinary Journal 34 (3):521-532.
Joerg Flum (2003). Descriptive Complexity Theories. Theoria 18 (1):47-58.
Jakub Szymanik (2009). Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language. Dissertation, University of Amsterdam
Felipe Cucker & Klaus Meer (1999). Logics Which Capture Complexity Classes Over the Reals. Journal of Symbolic Logic 64 (1):363-390.
Leszek Aleksander Kołodziejczyk (2004). Truth Definitions in Finite Models. Journal of Symbolic Logic 69 (1):183-200.
Dexter Kozen (1988). A Finite Model Theorem for the Propositional Μ-Calculus. Studia Logica 47 (3):233 - 241.
Anuj Dawar & Yuri Gurevich (2002). Fixed Point Logics. Bulletin of Symbolic Logic 8 (1):65-88.
Jakub Szymanik & Marcin Zajenkowski (2009). Understanding Quantifiers in Language. In N. A. Taatgen & H. van Rijn (eds.), Proceedings of the 31st Annual Conference of the Cognitive Science Society.
Jakub Szymanik (2010). Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language. Linguistics and Philosophy 33 (3):215-250.
Martin Grohe (1998). Finite Variable Logics in Descriptive Complexity Theory. Bulletin of Symbolic Logic 4 (4):345-398.
Analytics
Monthly downloads |
Added to index2012-03-18Total downloads4 ( #178,434 of 548,951 )Recent downloads (6 months)2 ( #37,438 of 548,951 )How can I increase my downloads? |
My notes
Discussion
