Horn clause

This section details the different aspects of the representation we have adopted to describe the problem solutions and the new control knowledge generated by the learning mechanism. Throughout the section we will continue to use the flowshop scheduling problem as an illustration. The section starts by discussing the motives for selecting the horn clause form of first-order predicate calculus, and then proceeds to show how the representation supports both the synthesis of problem solutions and their analysis. The section concludes with a description of how the sufficient... 

It is beyond the scope of this chapter to explain the syntax and semantics of first-order predicate logic, and the reader is referred to Lloyd s text (1987) for a general introduction. However, it is useful to provide some details on the horn clause form. 

A logical clause is a disjunction of terms, and a horn clause is one where, at most, one term is positive. In propositional logic, where only literals are allowed horn clauses have the following form ... 

Theoretically it has been shown (Thayse, 1988) that the DDP formalism is closely related to a simpler form of horn clause logic, i.e., the propositional calculus. This would suggest that we could use the horn clause form to express some of the types of knowledge we are required to manipulate in combinatorial optimization problems. The explicit inclusion of state information into the representation, necessitates the shift from the simpler propositional form, to the first-order form, since we wish to parsimoniously represent properties that can be true, or take different values, in different states. By limiting the form to horn clauses, we are striving to retain the maximum simplicity of representation, whilst admitting the necessary expressive power. 

First-order predicate calculus admits proof techniques that can be shown to be sound and complete (Lloyd, 1987). The soundness of the proof technique is important because it ensures that our methodology will not deduce results that are invalid. We are less concerned with completeness, because in most cases, although the proof technique will be complete, the theory of dominance or equivalence we have available will be incomplete for most problems. Restricting the first-order logic to be of horn clause form, enables the employment of SLD resolution, a simpler... 

First-order horn clause logic is the representation that has been adopted by workers in the field of explanation-based learning (Minton et al., 1990). Hence, using this representation allows us take advantage of the results and algorithms developed in that field to carry out the machine learning task. 

State to another, can be modeled by the deductive form of the horn clauses. This is a common strategy in artiliciai intelligence, and is formalized by situational calculus (Green, 1969). 

Let us now illustrate how the horn clause for of predicate logic can be used for the unfolding of the branching structure and the synthesis of new solutions. 

The domain theory consists of the horn clauses that represent... 

The method that Shavlik developed to carry out the structure generalization is complex, and requires the introduction of an extension to the horn clause deduction scheme to allow the repetitive application of a... 

Horn clause Clause having one left-hand side literal at... 

Logic programming Representation of a program in the form of Horn clauses, and interpretation of these clauses in a declarative and in a procedural form. 

Prolog s rules, facts, and queries are Horn clauses. Horn clauses, also called definite clauses, are a subset of the clausal form of logic. The consequent of the clause is restricted to one term at maximum ... 

Horn clauses do not have the expressive power of the full clausal form of logic and, therefore do not have the power of first-order predicate calculus. The main disadvantage is that it is impossible to represent negative information like Siblings are not married with Horn clauses. 

Horn-clause logic is known to be Turing-complete, that is, it provides a universal computing formalism. Horn clauses are closely related to conventional programming languages since they can be given a simple procedural interpretation. 

There are two ways in which a Horn clause like... 

---