![]() |
![]() |
We study the expressive power and complexity of second-order revised Krom logic (SO-KROMr). On ordered finite structures, we show that its existential fragment Σ11-KROMr equals Σ11-KROM, and captures NL. On all finite structures, for k≥1, we show that Σ1k equals Σ1k+1-KROMr if k is even, and Π1k equals Π1k+1-KROMr if k is odd. The result gives an alternative logic to capture the polynomial hierarchy. We also introduce an extended version of second-order Krom logic (SO-EKROM). On ordered finite structures, we prove that SO-EKROM collapses to Π12-EKROM and equals Π11. Both SO-EKROM and Π12-EKROM capture co-NP on ordered finite structures.