On the Expressiveness of Frame Satisfiability and Fragments of Second-Order Logic
Eiter, Thomas ; Gottlob, Georg
J. Symbolic Logic, Tome 63 (1998) no. 1, p. 73-82 / Harvested from Project Euclid
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 $\Sigma^1_1$ (Ackermann) and $\Sigma^1_1$ (Bernays-Schonfinkel). We prove this conjecture. Our results imply that $\Sigma^1_1$ (Ackermann) and $\Sigma^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, $\Sigma^1_1$ (Bernays-Schonfinkel) is strictly more expressive than $\Sigma^1_1$ (Ackermann).
Publié le : 1998-03-14
Classification: 
@article{1183745458,
     author = {Eiter, Thomas and Gottlob, Georg},
     title = {On the Expressiveness of Frame Satisfiability and Fragments of Second-Order Logic},
     journal = {J. Symbolic Logic},
     volume = {63},
     number = {1},
     year = {1998},
     pages = { 73-82},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745458}
}
Eiter, Thomas; Gottlob, Georg. On the Expressiveness of Frame Satisfiability and Fragments of Second-Order Logic. J. Symbolic Logic, Tome 63 (1998) no. 1, pp.  73-82. http://gdmltest.u-ga.fr/item/1183745458/