11 citations · 39 across the 12 of their papers we have counts for
12 papers
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…
Quantum-enhanced Logic-based Blockchain I: Quantum Honest-success Byzantine Agreement and Qulogicoin
Xin Sun, Quanlong Wang, Piotr Kulicki +1
We proposed a framework of quantum-enhanced logic-based blockchain, which improves the efficiency and power of quantum-secured blockchain. The efficiency is improved by using a new…
Unsatisfiable hitting clause-sets with three more clauses than variables
Oliver Kullmann, Xishun Zhao
The topic of this paper is the Finiteness Conjecture for minimally unsatisfiable clause-sets (MUs), stating that for each fixed deficiency (number of clauses minus number of variab…
Parameters for minimal unsatisfiability: Smarandache primitive numbers and full clauses
Oliver Kullmann, Xishun Zhao
We establish a new bridge between propositional logic and elementary number theory. The main objects are "minimally unsatisfiable clause-sets", short "MUs", unsatisfiable conjuncti…
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…
Bounds for variables with few occurrences in conjunctive normal forms
Oliver Kullmann, Xishun Zhao
We investigate connections between SAT (the propositional satisfiability problem) and combinatorics, around the minimum degree (number of occurrences) of variables in various forms…
On Davis-Putnam reductions for minimally unsatisfiable clause-sets
Oliver Kullmann, Xishun Zhao
For investigations into the structure of MU, i.e., minimally unsatisfiable clause-sets or conjunctive normal forms, singular DP-reduction is a fundamental tool, applying DP-reducti…
Proof System for Plan Verification under 0-Approximation Semantics
Xishun Zhao, Yuping Shen
In this paper a proof system is developed for plan verification problems and under 0-approximation semantics for . Here, for a plan $…
On variables with few occurrences in conjunctive normal forms
Oliver Kullmann, Xishun Zhao
We consider the question of the existence of variables with few occurrences in boolean conjunctive normal forms (clause-sets). Let mvd(F) for a clause-set F denote the minimal vari…
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…