ON THE EXPRESSIVENESS OF FRAME SATISFIABILITY AND FRAGMENTS OF 2ND-ORDER LOGIC

It was conjectured by Halpern and Kapron (Annals of Pure and Applied L ogic, vol. 69, 1994) that frame satisfiability of propositional modal formulas is incomparable in expressive power to both Sigma(1)(1)(Acker mann) and Sigma(1)(1)(Bernays-Schonfinkel). We prove this conjecture. Our results imply that (Ackermann) and Sigma(1)(1)(Bernays-Schonfinkel ) are incomparable in expressive power, already on finite graphs. More over, we show that on ordered finite graphs, i.e., finite graphs with a successor, Sigma(1)(1)(Bernays-Schonfinkel) is strictly more express ive than Sigma(1)(1)(Ackermann).