BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Xishun Zhao

Xishun Zhao contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Logic in Computer ScienceDiscrete Mathematicsmath.COArtificial IntelligenceComputational Complexitymath.LO

Trust snapshot

Quick read

Trust 21 - Emerging
7works
0followers
6topics
3close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2022arXiv

A Logic that Captures $β$P on Ordered Structures

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 logic $\exists^{\log^ω}\text{IFP}$ captures the limited nondeterminism class $β\text{P}$. In order to study its expressive power, we also design a new version of Ehrenfeucht-Fraïssé game for this logic and show that our capturing result will not hold on the general case, i.e. on all the finite structures.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Unsatisfiable hitting clause-sets with three more clauses than variables

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 variables) there are only finitely many patterns, given a certain basic reduction (generalising unit-clause propagation). We focus our attention on hitting clause-sets (every two clauses have at least one clash), where the conjecture says that there are only finitely many isomorphism types. The Finiteness Conjecture is here known to hold for deficiency at most 2, and we now prove it for deficiency 3. An important tool is the notion of "(ir)reducible clause-sets": we show how to reduce the general question to the irreducible case, and then solve this case (for deficiency 3). This notion comes from number theory (Korec 1984, Berger et al 1990), and we rediscovered it in our studies.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Canonical Logic Programs are Succinctly Incomparable with Propositional Formulas

\emph{Canonical (logic) programs} (CP) refer to normal logic programs augmented with connective $not\ not$. In this paper we address the question of whether CP are \emph{succinctly incomparable} with \emph{propositional formulas} (PF). Our main result shows that the PARITY problem, which can be polynomially represented in PF but \emph{only} has exponential representations in CP. In other words, PARITY \emph{separates} PF from CP. Simply speaking, this means that exponential size blowup is generally inevitable when translating a set of formulas in PF into an equivalent program in CP (without introducing new variables). Furthermore, since it has been shown by Lifschitz and Razborov that there is also a problem that separates CP from PF (assuming $\mathsf{P}\nsubseteq \mathsf{NC^1/poly}$), it follows that CP and PF are indeed succinctly incomparable. From the view of the theory of computation, the above result may also be considered as the separation of two \emph{models of computation}, i.e., we identify a language in $\mathsf{NC^1/poly}$ which is not in the set of languages computable by polynomial size CP programs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parameters for minimal unsatisfiability: Smarandache primitive numbers and full clauses

We establish a new bridge between propositional logic and elementary number theory. The main objects are &#34;minimally unsatisfiable clause-sets&#34;, short &#34;MUs&#34;, unsatisfiable conjunctive normal forms rendered satisfiable by elimination of any clause. In other words, irredundant coverings of the boolean hypercube by subcubes. The main parameter for MUs is the &#34;deficiency&#34; k, the difference between the number of clauses and the number of variables (the difference between the number of elements in the covering and the dimension of the hypercube), and the fundamental fact is that k >= 1 holds. A &#34;full clause&#34; in an MU contains all variables (corresponding to a singleton in the covering). We show the lower bound S_2(k) <= FCM(k), where FCM(k) is the maximal number of full clauses in MUs of deficiency k, while S_2(k) is the smallest n such that 2^k divides n!. The proof rests on two methods: On the logic-combinatorial side, applying subsumption resolution and its inverse, a fundamental method since Boole in 1854 introduced the &#34;expansion method&#34;. On the arithmetical side, analysing certain recursions, combining an application-specific recursion with a recursion from the field of meta-Fibonacci sequences (indeed S_2 equals twice the Conolly sequence). A further tool is the consideration of unsatisfiable &#34;hitting clause-sets&#34; (UHITs), special cases of MUs, which correspond to the partitions of the boolean hypercube by subcubes; they are also known as orthogonal or disjoint DNF tautologies. We actually show the sharper lower bound S_2(k) <= FCH(k), where FCH(k) is the maximal number of full clauses in UHITs of deficiency k. We conjecture that for all k holds S_2(k) = FCH(k), which would establish a surprising connection between the extremal combinatorics of (un)satisfiability and elementary number theory. We apply the lower bound to analyse the structure of MUs and UHITs.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Davis-Putnam reductions for minimally unsatisfiable clause-sets

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-reduction F -> DP_v(F) in case variable v occurs in one polarity only once. Recall, in general DP_v(F) replaces all clauses containing variable v by their resolvents on v (another name is &#34;variable elimination&#34;). We consider sDP(F), the set of all results of applying singular DP-reduction to F in MU as long as possible, obtaining non-singular F&#39; in MU with the same deficiency, i.e., delta(F&#39;) = delta(F). (In general, delta(F) is the difference c(F) - n(F) of the number of clauses and the number of variables.) Our main results are: 1. For all F&#39;, F&#34; in sDP(F) we have n(F&#39;) = n(F&#34;). 2. If F is saturated (F in SMU), then we have |sDP(F)| = 1. 3. If F is &#34;eventually saturated&#34;, that is, sDP(F) <= SMU, then for F&#39;, F&#34; in sDP(F) we have F&#39; isomorphic F&#34; (establishing &#34;confluence modulo isomorphism&#34;). The results are obtained by a detailed analysis of singular DP-reduction for F in MU. As an application we obtain that singular DP-reduction for F in MU(2) (i.e., delta(F) = 2) is confluent modulo isomorphism (using the fundamental characterisation of MU(2) by Kleine Buening). The background for these considerations is the general project of the classification of MU in terms of the deficiency.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On variables with few occurrences in conjunctive normal forms

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 variable-degree, the minimum of the number of occurrences of variables. Our main result is an upper bound mvd(F) <= nM(surp(F)) <= surp(F) + 1 + log_2(surp(F)) for lean clause-sets F in dependency on the surplus surp(F). - Lean clause-sets, defined as having no non-trivial autarkies, generalise minimally unsatisfiable clause-sets. - For the surplus we have surp(F) <= delta(F) = c(F) - n(F), using the deficiency delta(F) of clause-sets, the difference between the number of clauses and the number of variables. - nM(k) is the k-th &#34;non-Mersenne&#34; number, skipping in the sequence of natural numbers all numbers of the form 2^n - 1. We conjecture that this bound is nearly precise for minimally unsatisfiable clause-sets. As an application of the upper bound we obtain that (arbitrary!) clause-sets F with mvd(F) > nM(surp(F)) must have a non-trivial autarky (so clauses can be removed satisfiability-equivalently by an assignment satisfying some clauses and not touching the other clauses). It is open whether such an autarky can be found in polynomial time. As a future application we discuss the classification of minimally unsatisfiable clause-sets depending on the deficiency.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Proof System for Plan Verification under 0-Approximation Semantics

In this paper a proof system is developed for plan verification problems $\{X\}c\{Y\}$ and $\{X\}c\{KW p\}$ under 0-approximation semantics for ${\mathcal A}_K$. Here, for a plan $c$, two sets $X,Y$ of fluent literals, and a literal $p$, $\{X\}c\{Y\}$ (resp. $\{X\}c\{KW p\}$) means that all literals of $Y$ become true (resp. $p$ becomes known) after executing $c$ in any initial state in which all literals in $X$ are true.Then, soundness and completeness are proved. The proof system allows verifying plans and generating plans as well.

0 citations0 reviewsNo code linkedOpen access