On the Expressibility of Stable Logic Programming

Details On the Expressibility of Stable Logic Programming On the Expressibility of Stable Logic Programming

2003-12-22

arxiv.org/abs/cs/0312053v1

TCLP 3(2003), pp. 551-567q

Computer Science

Artificial Intelligence

17 pages

Scientific paper

(We apologize for pidgin LaTeX) Schlipf \cite{sch91} proved that Stable Logic Programming (SLP) solves all $\mathit{NP}$ decision problems. We extend Schlipf's result to prove that SLP solves all search problems in the class $\mathit{NP}$. Moreover, we do this in a uniform way as defined in \cite{mt99}. Specifically, we show that there is a single $\mathrm{DATALOG}^{\neg}$ program $P_{\mathit{Trg}}$ such that given any Turing machine $M$, any polynomial $p$ with non-negative integer coefficients and any input $\sigma$ of size $n$ over a fixed alphabet $\Sigma$, there is an extensional database $\mathit{edb}_{M,p,\sigma}$ such that there is a one-to-one correspondence between the stable models of $\mathit{edb}_{M,p,\sigma} \cup P_{\mathit{Trg}}$ and the accepting computations of the machine $M$ that reach the final state in at most $p(n)$ steps. Moreover, $\mathit{edb}_{M,p,\sigma}$ can be computed in polynomial time from $p$, $\sigma$ and the description of $M$ and the decoding of such accepting computations from its corresponding stable model of $\mathit{edb}_{M,p,\sigma} \cup P_{\mathit{Trg}}$ can be computed in linear time. A similar statement holds for Default Logic with respect to $\Sigma_2^\mathrm{P}$-search problems\footnote{The proof of this result involves additional technical complications and will be a subject of another publication.}.

Affiliated with

Also associated with

No associations

Rating

On the Expressibility of Stable Logic Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Expressibility of Stable Logic Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Expressibility of Stable Logic Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-618292