Lower bounds for the lengths of refutations

From MaRDI portal





Some lower bounds for lengths of refutations of a goal with respect to (w.r.t.) a logic program are proved; they imply corresponding lower bounds for pure Prolog. A data-type \(D\) is a set of ground terms; representation of \(D\) is the set \({\mathcal T}\) of terms such that \(D=U\{\text{ground}(t):t \in{\mathcal T}\}\), where ground\((t)\) denotes the set of all ground instances of \(t\). \(D\) is elementary if \(D=\text{ground}(t)\) for some term \(t\) and discrete, if it does not include infinite elementary data-type. Pair \((P,g)\) \((P\) -- a logic program, \(g\) -- unary relation symbol) is called a recognizer for \(D\) if \(t\in D\) for any ground term \(t\) iff \(g(t)\) has a refutation w.r.t. \(P\). \(m({\mathcal G},P)\) denotes the minimum length of all the refutations for the goal \({\mathcal G}\) w.r.t. \(P\). The meaning of a logic program \(P\) is the set of all grounds goals \({\mathcal G}\) such that \({\mathcal G}\) has a refutation w.r.t. \(P\). Let \(\mu(t)=\min |\{\text{subterms}(t^ \sigma)\} |\), where \(\sigma\) is a substitution; \(d_ 0(P)=\max\{\text{depth}(H)\}\), \(\nu_ 0(P)=\max\{ \nu(H) \}\), where \(H\) is the head of a clause in \(P\) and \(\nu(t)\) is the number of distinct subterms of \(t\) which are not variables and depth is defined by: \(\text{depth}(t)=0\), if \(t\) is a variable; \(\text{depth}(t)=1\), if \(t\) is a constant, \(\text{depth}\bigl( f(t_ 1,\ldots,t_ n)\bigr)=\max\{\text{depth}(t_ i)\}+1\) for a function symbol \(f\), \(\text{depth}\bigl( g(t_ 1,\ldots,t_ n)\bigr)=\max\{\text{depth}(t_ i)\}\) for a relation symbol \(g\) and \(\text{depth}(t_ 1,\ldots,t_ n)=\max\{\text{depth}(t_ 1)\}\). It is proved, that if \(D\) is an infinite discrete data-type and \((P,g)\) is a recognizer for \(D\), then for any infinite sequence \(d_ 1,d_ 2,\ldots\) of elements of \(D\) there exist infinitely many \(n\) such that \(m\bigl( g(d_ n),P\bigr) <\log_ p(n)-1\), where \(p\) is the number of clauses in \(P\). If \(P\) is range restricted (every variable in the head of any clause also appears in the body of the clause) and meaning \((P)\neq \emptyset\), then neither \(d_ 0(P)\) nor \(\nu_ 0(P)\) is 0 and \(m(G,P)\geq \text{depth}(G)/d_ 0(P)\), \(m(G,P)\geq \mu(G)/\nu_ 0(P)\) holds for any atom \(G\).











This page was built for publication: Lower bounds for the lengths of refutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4272508)