Capturing the polynomial hierarchy by second-order revised Krom logic

Kexu Wang, Shiguang Feng, Xishun Zhao

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 ${\Sigma }_1^1$-KROM$^r…