1 citations · 2 across the 5 of their papers we have counts for
Showing cs.LOShow all
3 papers · 1 filter
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). On ordered finite structures, we show that its existential fragment -KROM$^r…
cs.LO2015★ 1 cited
Canonical Logic Programs are Succinctly Incomparable with Propositional Formulas
Yuping Shen, Xishun Zhao
\emph{Canonical (logic) programs} (CP) refer to normal logic programs augmented with connective . In this paper we address the question of whether CP are \emph{succinctly…
cs.LO2010
NP-Logic Systems and Model-Equivalence Reductions
Yuping Shen, Xishun Zhao
In this paper we investigate the existence of model-equivalence reduction between NP-logic systems which are logic systems with model existence problem in NP. It is shown that amon…