Recursive logic algorithms

In the following, we thus only consider recursive logic algorithms where some well-founded relation can be defined between the recursive literals and the head. We thus have to enforce that a synthesis mechanism doesn t design non-terminating recursion (for ground queries). 

Within a restricted setting, the MSG Method infers, from a finite set of general examples, a non-recursive logic algorithm that is defined in terms of the =/2 primitive only, and that is correct wrt a natural extension of the given examples. The underlying algorithm is non-deterministic. 

However, it may happen that the instance of Solve or SolveNonMin is defined as a full-fledged, possibly recursive, logic algorithm. Different methods need to be applied then. We discuss one such method in Section 14.2.4. 

Example 13-4 During the synthesis of LAipermutation-int-L), the MSG Method is invoked as in Example 10-12. The first result is subject to Heuristic 13-2, because there are too many cliques, which lets expect that LA(pcPermutation) wouldn t behave as intended on a goal such aspcPermutation a,[b,c4,ef]R). The same holds for the second result. The intended relation for LA(pcPermutation) is indeed the one underlying the stuff/3 predicate, and thus requires a recursive logic algorithm. We show in Section 14.2.4 how this can be obtained. 

The Synthesis Method assumes that there is a single sub-case of the recursive case (w=l), and that procCompi(HX,TY,Y), which is hereafter denoted procComp HX,TY,Y), is defined by a full-fledged recursive logic algorithm. The synthesis of LA procComp) may thus be achieved by the following sequence of tasks ... 

Example 5-4 The following logic algorithm for insert(EEfi) has been designed with L as induction parameter. Parameter E is an auxiliary parameter. Note that the non-minimal form gives rise to two cases, one of them without a recursive atom. 

Several aspects of logic algorithm design can be discussed now. We first propose a useful terminology for logic algorithm classification, and then show in what sense minimal cases and non-recursive non-minimal cases, though syntactically similar, are totally different concepts. 

As the logic algorithms of this book exhibit, not all non-minimal cases are recursive. Indeed, prefix-traversal logic algorithms have non-recursive non-minimal cases. But some structural cases of logic algorithms in Chapter 4, or [Deville 90], seem hard to classify. There are several potential reasons to this. 

A first reason is that non-recursive non-minimal cases of prefix-scan logic algorithms can often be merged with their minimal cases. The resulting algorithm looks like it has no minimal case. It exhibits cases whose structural forms are not mutually exclusive, and is thus easy to detect as being a rewriting of the canonical version. 

It is important to understand that such logic algorithms with non-recursive, non-minimal cases are the result of re-writing canonical logic algorithms, rather than unpleasant aberrations. 

Let s close in now on the MSG Method. Intuitively, its objective is to infer a logic algorithm of a predicate r n, given a finite set of examples of rhi The method should be applicable if the intended relation (from which the examples are extracted) can be expressed by a logic algorithm that is defined solely in terms of the =/2 primitive (hence is non-recursive, among others). This is feasible iff, in the intended relation, some parameters are somehow syntactically constructed from some other parameters. 

So why not immediately use the Synthesis Method The reason is that both methods tackle different classes of problems. The MSG Method and the Synthesis Method are a joint answer to the same overall problem how to infer, from a finite set of general examples of an unknown relation that is however known to feature a given dataflow pattern between its parameters, a logic algorithm that is correct wrt a natural extension of the given examples. The MSG Method is the base case of the answer, because it doesn t look for recursion, and the Synthesis Method is the structure case of the answer, because it does look for recursion. 

Third, we only aim at the synthesis of single-loop logic algorithms. In other words, we assume that the only loop is the one that is achieved in the schema by the recursion on the induction parameter, and that none of the instances of the predicate-variables is defined recursively (possibly as a divide-and-conquer logic algorithm). 

This amounts to splitting the non-minimal case into two non-mandatory cases, called the non-recursive non-minimal case and the recursive non-minimal case, respectively. For convenience, we drop the qualifier non-minimal from these two names. Recursion may be useless in the sense that the recursively computed TY are not needed for the computation of Y. Useless recursion wouldn t affect the correctness of a logic algorithm, though. Its elimination is thus rather a matter of algorithm optimization. The following objectives of the strategy ... 

This logic algorithm is totally correct wrt the intended relation. The main obstacle is the detection that recursion is useless in the second disjunct. ... 

In terms of alternative techniques to the MSG Method, there is of course the whole literature on empirical learning, and inductive logic programming (ILP), as surveyed in Chapter 3. But it should be noted that the MSG Method only aims at the synthesis of a sub-class of concept descriptions, namely non-recursive algorithms that are implemented in terms of the =/2 primitive only, and whose intended relation, though unknown as a whole, is however known to feature a given dataflow pattern between... 

---