On the expressiveness of frame satisfiability and fragments of second-order logic
Journal of Symbolic Logic 63 (1):73-82 (1998)
| Abstract | It was conjectured by Halpern and Kapron (Annals of Pure and Applied Logic, vol. 69, 1994) that frame satisfiability of propositional modal formulas is incomparable in expressive power to both Σ 1 1 (Ackermann) and Σ 1 1 (Bernays-Schonfinkel). We prove this conjecture. Our results imply that Σ 1 1 (Ackermann) and Σ 1 1 (Bernays-Schonfinkel) are incomparable in expressive power, already on finite graphs. Moreover, we show that on ordered finite graphs, i.e., finite graphs with a successor, Σ 1 1 (Bernays-Schonfinkel) is strictly more expressive than Σ 1 1 (Ackermann) | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,664 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesGeorg Gottlob (1997). Relativized Logspace and Generalized Quantifiers Over Finite Ordered Structures. Journal of Symbolic Logic 62 (2):545-574.
Stéphane Demri & Hans De Nivelle (2005). Deciding Regular Grammar Logics with Converse Through First-Order Logic. Journal of Logic, Language and Information 14 (3).
Ian Pratt-Hartmann (2008). On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics. The Bulletin of Symbolic Logic 14 (1):1 - 28.
Miklos Ajtai & Ronald Fagin (1990). Reachability is Harder for Directed Than for Undirected Finite Graphs. Journal of Symbolic Logic 55 (1):113-150.
R. Hirsch, I. Hodkinson & A. Kurucz (2002). On Modal Logics Between K × K × K and $S5 \Times S5 \Times S5$. Journal of Symbolic Logic 67 (1):221 - 234.
William C. Purdy (2002). Complexity and Nicety of Fluted Logic. Studia Logica 71 (2):177 - 198.
Eva Hoogland & Maarten Marx (2002). Interpolation and Definability in Guarded Fragments. Studia Logica 70 (3):373 - 409.
Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
Frank Wolter & Michael Zakharyaschev (2001). Decidable Fragments of First-Order Modal Logics. Journal of Symbolic Logic 66 (3):1415-1438.
Martin Otto (2001). Two Variable First-Order Logic Over Ordered Domains. Journal of Symbolic Logic 66 (2):685-702.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads2 ( #232,316 of 549,037 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
