Capturing the polynomial hierarchy by second-order revised Krom logic

We study the expressive power and complexity of second-order revised Krom logic (SO-KROM${}^r$). On ordered finite structures, we show that its existential fragment ${\mathrm{\Sigma }}_1^1$-KROM${}^r$ equals ${\mathrm{\Sigma }}_1^1$-KROM, and captures NL. On all finite structures, for $k\ge 1$, we show that ${\mathrm{\Sigma }}_k^1$ equals ${\mathrm{\Sigma }}_{k+1}^1$-KROM${}^r$ if $k$ is even, and ${\mathrm{\Pi }}_k^1$ equals ${\mathrm{\Pi }}_{k+1}^1$-KROM${}^r$ 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 ${\mathrm{\Pi }}_2^1$-EKROM and equals ${\mathrm{\Pi }}_1^1$. Both SO-EKROM and ${\mathrm{\Pi }}_2^1$-EKROM capture co-NP on ordered finite structures.