Almost everywhere equivalence of logics in finite model theory
Bulletin of Symbolic Logic 2 (4):422-443 (1996)
| Abstract | We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept of almost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, if L, L ′ are two logics and μ is an asymptotic measure on finite structures, then $\scr{L}\equiv _{\text{a.e.}}\scr{L}^{\prime}(\mu)$ means that there is a class C of finite structures with μ (C)=1 and such that L and L ′ define the same queries on C. We carry out a systematic investigation of $\equiv _{\text{a.e.}}$ with respect to the uniform measure and analyze the $\equiv _{\text{a.e.}}$ -equivalence classes of several logics that have been studied extensively in finite model theory. Moreover, we explore connections with descriptive complexity theory and examine the status of certain classical results of model theory in the context of this new framework | |||||||||
| Keywords | complexity descriptive finite generalized model quantifiers theory | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,653 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesMartin Otto (1996). The Expressive Power of Fixed-Point Logic with Counting. Journal of Symbolic Logic 61 (1):147-176.
Dexter Kozen (1988). A Finite Model Theorem for the Propositional Μ-Calculus. Studia Logica 47 (3):233 - 241.
Dmitrij Skvortsov (2004). On Intermediate Predicate Logics of Some Finite Kripke Frames, I. Levelwise Uniform Trees. Studia Logica 77 (3):295 - 323.
Daniele Mundici (1981). An Algebraic Result About Soft Model Theoretical Equivalence Relations with an Application to H. Friedman's Fourth Problem. Journal of Symbolic Logic 46 (3):523-530.
Stéphane Demri & Ewa Orłowska (1999). Every Finitely Reducible Logic has the Finite Model Property with Respect to the Class of ♦-Formulae. Studia Logica 62 (2):177 - 200.
Wafik Boulos Lotfallah (2000). Strong 0-1 Laws in Finite Model Theory. Journal of Symbolic Logic 65 (4):1686-1704.
Anuj Dawar & Yuri Gurevich (2002). Fixed Point Logics. Bulletin of Symbolic Logic 8 (1):65-88.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads5 ( #160,171 of 548,977 )Recent downloads (6 months)1 ( #63,511 of 548,977 )How can I increase my downloads? |
My notes
Discussion
