11 citations · 39 across the 12 of their papers we have counts for
5 papers · 1 filter
The Complexity and Expressive Power of Second-Order Extended Logic
Shiguang Feng, Xishun Zhao
We study the expressive powers of SO-HORN, SO-HORN and SO-HORN on all finite structures. We show that SO-HORN, SO-HORN, FO(LFP) coincide with each o…
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…
A Logic that Captures P on Ordered Structures
Kexu Wang, Xishun Zhao
We extend the inflationary fixed-point logic, IFP, with a new kind of second-order quantifiers which have (poly-)logarithmic bounds. We prove that on ordered structures the new log…
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…
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…