A time bound on the materialization of some recursively defined views

A virtual relation (or view) can be defined with a recursive Horn clause that is a function of one or more base relations. In general, the number of times such a Horn clause must be applied in order to retrieve all the tuples in the virtual relation depends on the contents of the base relations of the definition. However, there exist Horn clauses for which there is an upper bound on the number of applications necessary to form the virtual relation, independent of the contents of the base relations. Considering a restricted class of recursive Horn clauses, we give necessary and sufficient conditions for members of the class to have this bound.     

Learning Conjunctions of Horn Clauses

An algorithm is presented for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses. (A Horn clause is a disjunction of literals, all but at most one of which is a negated variable.) The algorithm uses equivalence queries and membership queries to produce a formula that is logically equivalent to the unknown formula to be learned. The amount of time used by the algorithm is polynomial in the number of variables and the number of clauses in the unknown formula.     

The Alexander Method — A technique for the processing of recursive axioms in deductive databases

We propose a technique for handling recursive axioms in deductive databases. More precisely, we solve the following problem: Given a relational query including virtual relations defined from axioms (Horn clauses, with variables in the conclusion predefined in the hypotheses), which can be recursive, how to translate this query into arelational program, i. e. a set of relational operations concerning only real relations (not virtual). Our solution has the following properties:

? the program to evaluate the query always terminates,

? the relational program is produced by a pure compilation of a source query and of the axioms, and is independent of the data values (there is no run-time),

? the relational operations are optimized: theyfocus towards the computation of the query, without needless computations.

As far as we know, the Alexander Method is the first solution exhibiting all these properties. This work is partly funded by Esprit Project 112 (KIMS).     

Completing open logic programs by constructive induction

We consider part of the problem of schema-biased inductive synthesis of recursive logic programs from incomplete specifications, such as clausal evidence (for instance, but not necessarily, ground positive and negative examples). After synthesizing the base clause and introducing recursive call(s) to the recursive clause, it remains to combine the overall result from the partial results obtained through recursion, so as to complete the recursive clause. Evidence for this combination relation can be abduced from the initially given evidence for the top-level relation. A program for this combination relation can be anything, from a single clause performing a unification (such as for lastElem) to multiple guarded clauses performing unifications (such as for filtering programs) to recursive programs (such as for naive reverse). Existing methods cannot induce guarded clause programs for this combination relation from the abduced evidence. Some existing methods cannot even detect that the combination program itself may have to be recursive and thus they then do not recursively invoke themselves the overall recursive program synthesizer. We introduce our Program Completion Method as a suitable extension and generalization of the existing methods. ©1999 John Wiley & Sons, Inc.     

Logical inference of clauses based on Petri net models

This paper extends the logical inference of Horn clauses in Petri net models to cover a large class of non-Horn clauses. Based on four-valued logic and the conflict transition concept, we show how the Petri net model for this class of non-Horn clauses can be constructed. The clause inference is solved by the T-invariant method or the fixpoint of markings. Both forward and backward inference can be used in our model. It is further shown that these techniques are efficient for the common classes of monotonic reasoning. © 1998 John Wiley & Sons, Inc.     

Compiling a default reasoning system into Prolog

Artificial intelligence researchers have been designing representation systems for default and abductive reasoning. Logic Programming researchers have been working on techniques to improve the efficiency of Horn clause deduction systems This paper describes how one such default and abductive reasoning system (namelyTheorist) can be translated into Horn clauses (with negation as failure), so that we can use the clarity of abductive reasoning systems and the efficiency of Horn clause deduction systems. We thus show how advances in expressive power that artificial intelligence workers are working on can directly utilise advances in efficiency that logic programming researchers are working on. Actual code from a running system is given.     

Model-100: Specification language for interacting processes

Basic ideas and constructs of the Model-100 language designed for describing behavior of interacting processes are discussed. Process interaction rules are specified by clauses of the form “if … then …” (Horn clauses). Structure of the interactions is presented by a graph described by a rational term. Execution of one step of the program reduces to simultaneous application of all rules to all nodes to which the rule can be applied (i.e., to all rational subterms with which the Horn clause can be unified).     

Hardness results for approximate pure Horn CNF formulae minimization

We study the hardness of approximation of clause minimum and literal minimum representations of pure Horn functions in n Boolean variables. We show that unless P=NP, it is not possible to approximate in polynomial time the minimum number of clauses and the minimum number of literals of pure Horn CNF representations to within a factor of \(2^{\log^{1-o(1)} n}\) . This is the case even when the inputs are restricted to pure Horn 3-CNFs with O(n ^1+ε ) clauses, for some small positive constant ε. Furthermore, we show that even allowing sub-exponential time computation, it is still not possible to obtain constant factor approximations for such problems unless the Exponential Time Hypothesis turns out to be false.     

Learning compact Markov logic networks with decision trees

Statistical-relational learning combines logical syntax with probabilistic methods. Markov Logic Networks (MLNs) are a prominent model class that generalizes both first-order logic and undirected graphical models (Markov networks). The qualitative component of an MLN is a set of clauses and the quantitative component is a set of clause weights. Generative MLNs model the joint distribution of relationships and attributes. A state-of-the-art structure learning method is the moralization approach: learn a set of directed Horn clauses, then convert them to conjunctions to obtain MLN clauses. The directed clauses are learned using Bayes net methods. The moralization approach takes advantage of the high-quality inference algorithms for MLNs and their ability to handle cyclic dependencies. A?weakness of moralization is that it leads to an unnecessarily large number of clauses. In this paper we show that using decision trees to represent conditional probabilities in the Bayes net is an effective remedy that leads to much more compact MLN structures. In experiments on benchmark datasets, the decision trees reduce the number of clauses in the moralized MLN by a factor of 5?C25, depending on the dataset. The accuracy of predictions is competitive with the models obtained by standard moralization, and in many cases superior.     

A generalization of the differential approach to recursive query evaluation

The differential (or seminaive) approach to query evaluation in function free, recursively defined, Horn clauses was recently proposed as an improvement to the naive bottom-up evaluation strategy. In this paper, we extend the approach to efficiently accomodate n recursively defined predicates in the body of a Horn clause.     

On computability by logic programs

The problem of computational completeness of Horn clause logic programs is revisited. The standard results on representability of all computable predicates by Horn clause logic programs are not related to the real universe on which logic programs operate. SLD-resolution, which is the main mechanism to execute logic programs, may give answer substitutions with variables. As the main result we prove that computability by Horn clause logic programs is equivalent to standard computability over the Herbrand universe with variables. The semantics we use isS-semantics introduced by Falaschi et al. [3]. As an application of the main result we prove the existence of a metainterpreter for a sublanguage of real Prolog, written in the language of Horn clauses with the S-semantics. We also show that the traditional semantics of Prolog do not reflect its computational behavior from the viewpoint of recursion theory.This article is a revised version of [13]. The work was essentially done during author's visit to ECRC.     

扩展AL-log挖掘日志本体的ILP方法

为发现Web使用记录中所蕴涵的用户访问模式,在深入分析日志本体中事件间的抽象关系后,提出适用于原子事件和复合事件间整分关系推理的ALC传播规则扩展已有的推理模式,并在此基础上提出一种挖掘日志本体的ILP方法.该方法结合描述逻辑和Horn规则在知识表示和推理过程中互补的特点,采用AL-log混合系统构建知识库,利用约束SLD-反驳消解和扩展ALC传播规则从日志本体中学习用户访问模式,达到站点商业智能和个性化的目的.最后给出验证该方法的实例,实验结果表明了该方法的可行性和有效性.     

A Fuzzy Proof Theory

Based on the first order peicate logic,in this paper,we present a new approach to generalizing the syntax of ordinary Horn clause rules to establish a fuzzy proof theory,First of all,each Horn clause rule is associated with a numerical implication strength f.Therefore we obtain f-Horn clause rules.Secondly,Herbrand interpretations can be generalized to fuzzy subsets of the Herbrand base in the sense of Zadch.As a result the proof theory for Horn clause rules can be developed in much the same way for f-Horm clause rules.     

Algorithmic Debugging and Hypothetical Reasoning

This paper presents a generalization of Shapiro style algorithmic debugging for generalized Horn clause intuitionistic logic. This logic offers hypothetical reasoning and negation is defined not by failure but by inconsistency. We extend Shapiro's notion of intended interpretation, symptoms and errors and give formal results paralleling those known for definite clauses. We also show how a corresponding diagnosis module for RISC- a logic programming system for generalized Horn clause intuitionistic logic-can be defined by meta interpretation. In contrast to Shapiro's PROLOG modules ours work independently of the specific computation rule that in RISC may be specified by the user.     

Disjoint essential sets of implicates of a CQ Horn function

In this paper we study a class of CQ Horn functions introduced in Boros et al. (Ann Math Artif Intell 57(3–4):249–291, 2010). We prove that given a CQ Horn function f, the maximal number of pairwise disjoint essential sets of implicates of f equals the minimum number of clauses in a CNF representing f. In other words, we prove that the maximum number of pairwise disjoint essential sets of implicates of f constitutes a tight lower bound on the size (the number of clauses) of any CNF representation of f.     

Algorithms for constructing minimal deduction graphs

Two algorithms for constructing minimal deduction graphs (MDG) for inferring rules and facts in an extended version of the Horn clause logic are described. A deduction graph (DG) is minimal if the number of arcs in the graph is minimized. Horn clauses (HC) are extended to Horn formulas (HF), such that the head or the body of an HF can be a conjunction of positive literals or a disjunction of the bodies of some rule instances, respectively. Each algorithm constructs an MDG from its source to its sink, whose arcs infer the HF `if source then sink'. The construction of an MDG is based on a sound and complete set of inference rules of reflexivity, transitivity, and conjunction for HFs which proceeds by expanding a tree rooted at its sink until its source has a successful backtracking to the root. Then the MDG is extracted from the tree. The nodes being expanded in such a tree are classified into seven types, which are assigned by different priorities for their growing into subtrees or for their pruning to reduce the tree space     

On-line algorithms for polynomially solvable satisfiability problems

Given a propositional Horn formula, we show how to maintain on-line information about its satisfiability during the insertion of new clauses. A data structure is presented which answers each satisfiability question in O(1) time and inserts a new clause of length q in O(q) amortized time. This significantly outperforms previously known solutions of the same problem. This result is extended also to a particular class of non-Horn formulae already considered in the literature, for which the space bound is improved. Other operations are considered, such as testing whether a given hypothesis is consistent with a satisfying interpretation of the given formula and determining a truth assignment which satisfies a given formula. The on-line time and space complexity of these operations is also analyzed.