Xishun Zhao

activity

20102022

most citedOn variables with few occurrences in conjunctive normal forms

11 citations · 39 across the 12 of their papers we have counts for

collaborators

Showing 2022Show all

2 papers · 1 filter

cs.LO2022★ 2 cited

The Complexity and Expressive Power of Second-Order Extended Logic

Shiguang Feng, Xishun Zhao

We study the expressive powers of SO-HORN $^{*}$ , SO-HORN $^{r}$ and SO-HORN $^{* r}$ on all finite structures. We show that SO-HORN $^{r}$ , SO-HORN $^{* r}$ , FO(LFP) coincide with each o…

cs.LO2022

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 $Σ_{1}^{1}$ -KROM$^r…