M. Bruynooghe, and L. Pereira. Deduction revision by intelligent backtracking Implementations of Prolog (J. Campbell, ed.), Ellis Horwood, 1984, pp. 194-215.  @ NUS  Home/Search   Document Not in Database   Summary   Related Articles   Check

.... than retreating to the chronologically most recent decision was exploited independently in [Gaschnig 79] where the term backjumping was introduced, and in [Stallman Sussman 77] The idea has since been used in truthmaintenance systems, Doyle 79] and in intelligent backtracking in PROLOG [Bruynooghe Pereira 84] Gaschnig s algorithm uses a marking technique where each variable maintains a pointer to the highest ancestor found incompatible with any of its values. In case of a dead end, the algorithm can safely jump directly to the ancestor pointed to by the dead end variable. Although this scheme ....

Bruynooghe, M., and Pereira, L. M., \Deduction revision by intelligent backtracking," in Implementation of PROLOG, J. A. Campbell, Ed. Ellis Harwood, pp. 194-215, 1984. 25

....in the rvariable structure, more in formation is given in section 3.3. 1 [Bruynooghe, 1982] Mellish, 1982] Kahn and Carlsson, 1984] Sterling and Shapiro, 1986] All internal functions and builtins handle arguments that have this structure, such that intelligent backtracking [Warren, 1986] [Bruynooghe and Peteira, 1984] [Cox, 1984] can be implemented. The idea is that all functions that can backtrack take a failure continuation as an argument. If they cannot find any proof for the form handed them, they invoke the continuation. If they can identify a particular culprit, however, a slot on the rvariable contains ....

M. Bruynooghe and L. M. Peteira, "Deduction Revision by Intelligent Backtracking," In J. A. Campbell, editor, Implementations of Prolog. Ellis Hotwood Limited, 1984.

....records dependency information which is exploited on backtracking. This way branches of the search tree which can lead to the same failure are avoided and the search is more efficient. The idea of backjumping is equivalent to the idea of intelligent backtracking in logic programming as studied in [Bru78, PP79, PP80b, Bru80, Bru81, BP84, KL87, CCF88, MTK89, Bru92]. Intelligent backtracking is the only tree search technique that can be used to prune the search space of a CLP(R) derivation. Since in constraint logic programming variables can take values over different domains (e.g. Herbrand, real numbers) separate failure analysis procedures are needed for ....

....arithmetic constraint solvers and the first complete intelligent backtracking framework for a CLP( language. 1.4 Structure of the thesis Chapter 2 discusses a novel framework under which all the well known intelligent backtracking schemes are presented. The awkward techniques and algorithms of [BP84], CCF88] and [KL88] are explained using a common terminology, data structures and algorithmic frameworks. This allows for their first complete direct comparison to be drawn. Their differences in terms of space overheads, time overheads, advantages and disadvantages are discussed in detail. As a ....

[Article contains additional citation context not shown here]

M. Bruynooghe and L.-M. Pereira. Deduction revision by intelligent backtracking. In J. Campbell, editor, Implementations of Prolog, page 194. Ellis Horwood, 1984.

....level of e ciency, because the search space generated by the nondeterministic evaluation of a program is explored without taking into account any information derived from the program. Much work has been done in the direction of improving the control strategy of logic languages (see, for instance, [26, 110]) 20 We consider here a transformation technique, called compiling control [25] which follows a di erent approach. Instead of enhancing the naive Prolog evaluator using a clever (and often more complex) control strategy, we transform the given program so that the derived program behaves using ....

M. Bruynooghe and L. M. Pereira. Deduction revision by intelligent backtracking. In J. A. Campbell, editor, Implementations of Prolog, pages 253266. Ellis Horwood, 1984.

....are often called past variables and the unassigned variables are called future variables. Most dependency directed backtracking techniques can be divided into one of two types that I will call aggressive and conservative. Conservative techniques, such as those described in [Gaschnig, 1979] and [Bruynooghe and Pereira, 1984], only store dependency information for previously tried values of the past variables. Aggressive techniques, such as that described in [Stallman and Sussman, 1977] keep dependency information about future variables derived from earlier portions of the search involving those variables. Most ....

M. Bruynooghe and L. M. Pereira. Deduction revision by intelligent backtracking. In J. A. Cambell, editor, Implementations of Prolog, pages 196-- 215. Ellis Horwood, 1984.

.... 1988 ] Zabih, 1990 ] Furthermore, there is variety of mechanisms for backjumping , i.e. jumping back to earlier choice points because a dependency analysis shows that intervening choices where not involved in the cause of failure [ Stallman and Sussman, 1977 ] Gaschnig, 1979 ] Bruynooghe and Pereira, 1984 ] Research on algorithms for solving CSPs continues to be active. Translating CSPs into Boolean Clauses. It is possible to use a TMS as the foundation of a procedure for solving arbitrary CSPs. Truth maintenance techniques operate on Boolean constraints rather than CSPs as defined above. To ....

M. Bruynooghe and L. M. Pereira. Deduction revision by intelligent backtracking. In J. A. Cambell, editor, Implementations of Prolog, pages 196--215. Ellis Horwood, 1984.

....that we considered using was intelligent backtracking (also known as dependency directed backtracking) There is a large body of literature in this area and the techniques are relatively well understood. However after a survey of the literature on the technique (Kumar Lin, 1988) Cox, 1984) (Bruynooghe Pereira, 1984) we concluded that this approach would not be suitable for DEB. This is elaborated below. 6.1.1 What is intelligent backtracking When a logic program interpreter (read Prolog interpreter) is searching for a proof for a goal, it may produce a potential proof tree that is incorrect in the sense ....

....backtracking methods differ in the details of their implementation or in their capabilities of handling the cut and other Prolog predicates the basic approach in domain independent intelligent backtracking remains the same. Prune away subtrees such that deadend search spaces are not revisited. In (Bruynooghe Pereira, 1984) minimally inconsistent subtrees are spoken of while in (Cox 1984) maximally consistent subtrees are spoken of. Codognet, Codognet File 1988) claims to handle the cut and system predicates which cannot be handled by (Kumar Lin 1988) 6.1.2 Why intelligent backtracking will not work for DEB ....

Bruynooghe, M., & Peirera, L. M. (1984) Deduction revision by intelligent backtracking. In J. A. Campbell (Ed.) Implementations of Prolog New York: Ellis Horwood.

....in a compact timetable. Due to the topology of our search space, this results in a behavior we call thrashing when constraints are violated because the enumeration strategy is not clever enough to find the responsible variables. An approach using intelligent backtracking could help here [BP84] enumerate the courses of each year starting from a different time of the week. The domain from 1 through 180 is divided in 10 blocks representing mornings and afternoons of school days. These blocks can be individually ordered for each course (in the implementation we use the same ordering for ....

M. Bruynooghe and L.M. Pereira. Deduction revision by intelligent backtracking. In J.A. Campbell, editor, Implementations of PROLOG. Ellis Horwood Limited, 1984.

.... than retreating to the chronologically most recent decision was exploited independently in [Gaschnig 79] where the term backjumping was introduced, and in [Stallman Sussman 77] The idea has since been used in truth maintenance systems, Doyle 79] and in intelligent backtracking in PROLOG [Bruynooghe Pereira 84] Gaschnig s algorithm uses a marking technique where each variable maintains a pointer to the highest ancestor found incompatible with any of its values. In case of a dead end, the algorithm can safely jump directly to the ancestor pointed to by the dead end variable. Although this scheme ....

Bruynooghe, M., and Pereira, L. M., "Deduction revision by intelligent backtracking," in Implementation of PROLOG, J. A. Campbell, Ed. Ellis Harwood, pp. 194--215, 1984.

....idea is to learn from dead ends; whenever a dead end is reached we record a constraint explicated by the dead end. This type of learning has been presented in dependency directed backtracking strategies in the TMS community (Stallman Sussman 1977) and within intelligent backtracking for Prolog(Bruynooghe Pereira 1984). Recently, it was treated more systematically by Dechter (1990) within the constraint network framework. Different variants of learning were examined there, while taking into account the tradeoff between the overhead of learning and performance 3 This work was partially supported by NSF grant ....

Bruynooghe, M., and Pereira, L. M. 1984. Deduction revision by intelligent backtracking. In Campbell, J. A., ed., Implementation of Prolog. Ellis Horwood.

....satisfied. Due to a deductive nature of the problem, in principle, straightforward backtracking techniques can be used to solve it. To improve the efficiency and eliminate redundancies exploited by a simple minded backtracking, a number of intelligent backtracking techniques was proposed, e.g. Bruynooghe and Pereira, 1984 ] Alternatively, Bibel [ 1988 ] proposes a general bottom up, lazy evaluation method which transforms a constraint satisfaction problem into the problem of evaluating a database expression. In our approach, we do not address the backtracking redundancies, but rather reduce the search by first ....

Bruynooghe, M., Pereira, L.M. Deduction revision by intelligent backtracking. In J.A. Campbell, Ed., Implementations of PROLOG, pp. 194-215, Ellis Horwood, Chichester, UK.

....[3] Prolog systems based on the WAM are implemented during the last decade. In this paper, we will assume that the reader is familiar with the WAM. The details of the WAM can be found in Warren s original paper [17] and Kaci s tutorial book on the WAM [1] Many intelligent backtracking schemes [4, 5, 6, 7, 9, 11, 12, 13, 14, 16, 19] are presented to avoid unnecessary backtracking steps. Early works in intelligent backtracking [4, 9, 14] are implemented as Prolog interpreters. Implementations of later works [6, 7, 11, 12] are WAM based systems. Our intelligent backtracking schema whose some parts are presented in this paper ....

....with the WAM. The details of the WAM can be found in Warren s original paper [17] and Kaci s tutorial book on the WAM [1] Many intelligent backtracking schemes [4, 5, 6, 7, 9, 11, 12, 13, 14, 16, 19] are presented to avoid unnecessary backtracking steps. Early works in intelligent backtracking [4, 9, 14] are implemented as Prolog interpreters. Implementations of later works [6, 7, 11, 12] are WAM based systems. Our intelligent backtracking schema whose some parts are presented in this paper is implemented as an extension of the WAM, like the systems in [6, 11] Our mechanism is similar to the ....

[Article contains additional citation context not shown here]

Bruynooghe M. and Pereira L. M., Deduction Revision by Intelligent Backtracking, in Implementations of Prolog, ed. Cambell J. A., Ellis Horwood, 1984.

....list. It continues from node to node until all variables are assigned a value. If a feasible solution cannot be obtained during the searching process, different searching strategies have different methods to search for alternative solutions. 2. 4 Backtracking Algorithm Backtracking algorithm [19, 20, 21, 12, 22] is an exhaustive search that explores the whole search space. It has no attempt to reduce the search space by pruning off the search space. When no feasible value can be assigned to the current node (a dead end situation occurs) it goes back to the previous node, picks another value and ....

M. Bruynooghe and L. M. Pereira, "Deduction revision by intelligent backtracking," in Implementation of Prolog, pp. 194--215, Chichester, U. K.: Ellis Horwood, 1984.

....number 2559 1 Introduction Intelligent Backtracking has already been proven a valuable tool in solving combinatorial problems in Logic Programming. Many intelligent backtracking schemes have been proposed in the logic programming literature. Traditionally, full failure analysis methods as in [BP84, CCF86, Cox84] are considered very costly although they provide more accurate backtrack points than other methods. There is always a tradeoff between intelligent backtracking overheads and search space pruning to be considered. Therefore, some intelligent backtracking schemes sacrifice failure analysis accuracy ....

....analysis techniques described in the next section is illustrated in example 7.3. 7 Constraint Failure Analysis An essential component of an intelligent backtracking interpreter is the failure analysis subsystem. In standard logic programming, unification failure analysis has been studied in [Bru78, Bru80, BP84, CCF86, Nik88, VVK89, PP79, PP80b, PP80a]. Cox84, PM82, MP82] have studied unification failure analysis in the context of theorem proving. Failure analysis is obviously affected by the underlying domain of computation as well as the constraint solving algorithm. Ideally, the failure analysis subsystem should exploit the work already ....

Maurice Bruynooghe and Luis Moniz Periera. Deduction revision by intelligent backtracking. In J. Campbell, editor, Implementations of Prolog, page 194. Ellis Horwood, 1984.

....point may not be the most recent choice point. In other words, alternatives of choice points between the most recent one and the chosen one are discarded without retrying them. If they were retried, the system would have reencountered with the same failure. Many intelligent backtracking schemes [Bru84, Cha85, Cod88, Cod91, Cox81, Lin87, Lin88, Per82] are presented to avoid unnecessary backtracking steps. Early works in intelligent backtracking [Bru84, Cox81, Per82] are implemented as prolog interpreters. Implementations of later works [Lin87, Lin88, Cod88, Cod91] are WAM based systems. Direct comparisons of early works with later works may ....

....without retrying them. If they were retried, the system would have reencountered with the same failure. Many intelligent backtracking schemes [Bru84, Cha85, Cod88, Cod91, Cox81, Lin87, Lin88, Per82] are presented to avoid unnecessary backtracking steps. Early works in intelligent backtracking [Bru84, Cox81, Per82] are implemented as prolog interpreters. Implementations of later works [Lin87, Lin88, Cod88, Cod91] are WAM based systems. Direct comparisons of early works with later works may not give fruitful results because the machinery used in early works are much slower than the WAM based implementations ....

Bruynooghe M. and Pereiara L. M., Deduction Revision by Intelligent Backtracking, in Implementations of Prolog, ed. Cambell J. A., Ellis Horwood, 1984.

....us the desired level of efficiency, because the search space generated by the nondeterministic evaluation of a program is explored without using any information about the program. Much work has been done in the direction of improving the control strategy of logic languages (see, for instance, Bruynooghe and Pereira, 1984; Naish, 1985 ] We consider here a transformation technique, called compiling control [ Bruynooghe et al. 1989 ] which follows a different approach. Instead of enhancing the naive Prolog evaluator using a clever (and often more complex) control strategy, we transform the given program so ....

M. Bruynooghe and L. M. Pereira. Deduction revision by intelligent backtracking. In J. A. Campbell, editor, Implementations of Prolog, pages 253--266. Ellis Horwood, 1984.

....Ordered Prolog and other Prolog extensions Many efforts have been made during the last decade to try to overcome the problem of inefficient execution of Prolog. Among these efforts were extensions of standard Prolog that allow the definition of control rules for controlling the program execution (Bruynooghe Periera, 1984; Clark McCabe, 1979; Cox, 1984; Lloyd, 1984; Pereira, 1984; Pietryzykowski Matwin, 1982; Porto, 1984; Wise, 1984) Many of these Prolog extension use some form of what is called intelligent backtracking. Naish (1985b) gives an overview and classification of the control constructs used by ....

Bruynooghe, M., & Periera, L. M. (1984). Deduction Revision by Intelligent Backtracking. In J. A. Campbell (Ed.), Implementations of Prolog.

....Logarithm and section 5 gives some programming examples and experimental results on a Transputer network. 2 Formal definition of Logarithm resolution model Loagrithm resolution model is based on a distributed backtracking algorithm derived from the intelligent backtracking algorithm presented in [2]. After a presentation of the principles of our algorithm, we give a formal definition of our resolution model and a proof of its completeness. 2.1 Intelligent backtracking principle Intelligent backtracking is based on the choice of a backtrack point that can cure an unification failure. ....

....also compare Logarithm and compiled Sicstus Prolog (V2.1) execution times on sequential programs. Sicstus Prolog execution times have been measured on a Sparc station and multiplied by three to be comparable to T800 execution times. 5. 1 Data base query We address to a small data base taken from [2] that defines three predicates (student 2, prof 2 and course 3) two equivalent queries: the first one (fig: 3) exploits dependent AND parallelism and distributed backtracking; the second one (fig: 4) exploits OR parallelism. To increase the grain of OR parallelism, the request has been ....

M. Bruynooghe and L.-M. Pereira, "Deduction revision by intelligent backtracking", in Implementation of Prolog, J. Campbell, Ed., pp. 194--215, Ellis Horwood, 1984.

....pointing out more similarities than differences. Using their perspective, the RMS deployed in Echidna can be seen to be a single context ATMS. Given the recognized effectiveness of IB compared to chronological backtracking, it is natural to apply this methodology to LP. The early research of Bruynooghe and Pereira (1984) established the basic method using a justification type RMS. The more recent work of Drakos (1988) showed how to limit the size of the nogood database constructed by the RMS. Echidna uses a variation of this technique. Codognet et al. 1988) and You and Wong (1989) have made further practical ....

....as well) In the background, the RMS records in the Dependency Lattice the derivations made by the SLD Engine and their consequences propagated by the Constraint Engine. The RMS is a hybrid single context JTMS type augmented with datum labels as in ATMS approach. Similar to the earlier work of Bruynooghe and Pereira (1984), Drakos (1988) and You and Wong (1989) Echidna uses its RMS to record derivational changes to the proof tree. In Echidna however, assumptions correspond to both user queries and the nondeterministic choices of clauses made by the SLD Engine to satisfy goals. Events supported by these assumptions ....

[Article contains additional citation context not shown here]

M. Bruynooghe & L.M. Pereira (1984) Deduction Revision by Intelligent Backtracking, in J.A. Campbell (ed.) Implementations of Prolog,Ellis Horwood Publishers.

....the original system. To achieve this we propose to make use of binding dependency information to guide the unfolding of an AKL computation. One way this is accomplished is by improving the accuracy of the methods explored in [2] The basic problem of intelligent backtracking (IB) in Prolog (see [4, 6]) is to locate the bindings responsible for the occurrence of a failure, and backtrack directly to their originator, designated as the culprit, so that unnecessary work (i.e. irrelevant to the con ict) is eschewed. To do so, schemes to implement IB in Prolog (for example see [4, 12, 5, 7] always ....

....in Prolog (see [4, 6] is to locate the bindings responsible for the occurrence of a failure, and backtrack directly to their originator, designated as the culprit, so that unnecessary work (i.e. irrelevant to the con ict) is eschewed. To do so, schemes to implement IB in Prolog (for example see [4, 12, 5, 7]) always refer to the Prolog runtime data structures used to implement nondeterminism, namely choice points; i.e. a binding is said to depend on a given goal if it is associated with that goal s choice point. AKL provides no such concept, nondeterminism being handled di erently, by the use of ....

M. Bruynooghe and L. M. Pereira. Deduction revision by intelligent backtracking. In J.A. Campbell, editor, Implementations of Prolog. Ellis-Horwood, 1984.

....way or another, the whole computation tree has to be explicitly represented. One important aspect of our work is that the information we use for the backward execution is very limited and the goal of this work is not to attempt anything like intelligent backtracking as has been proposed for Prolog [1, 3, 4] or concurrent languages [2] Intelligent backtracking would require using data dependency information in some way. This requires to record more information, usually during the unification process, in order to determine dependencies between failing goals and choice points, based on ....

.... a version of the houses problem, crypt is adapted from [28] money is the send more=money cryptarithmetic puzzle, example g is the example discussed in section 5, bagof salt mustard is the salt and mustard puzzle, color 13 good and color 13 bad are the traditional map coloring puzzle from [1] with both a favorable and a bad goal ordering, ham and bagof ham consist in finding a Hamiltonian path through a graph, and blocks is a simple planning problem in the blocks world. The overall best method seems to be the btf family, the fastest ones being btf and btf t, as they obtain an average ....

M. Bruynooghe and L. M. Pereira. Deduction revision by intelligent backtracking. In J.A. Campbell, editor, implementations of Prolog. Ellis-Horwood, 1984.

.... is a version of the houses problem, crypt is adapted from [17] money is the send more=money cryptarithmetic puzzle, example g is the example previously discussed, bagof salt mustard is the saltand mustard puzzle, color 13 good and color 13 bad are the traditional map coloring puzzle from [1] with both a favorable and a bad goal ordering, ham and bagof ham consist in finding a Hamiltonian path through a graph, and blocks is a simple planning problem in the blocks world. The overall best method seems to be the btf family, the fastest ones being btf and btf t, as they obtain an average ....

M. Bruynooghe and L. M. Pereira. Deduction revision by intelligent backtracking. In J.A. Campbell, editor, implementations of Prolog. Ellis-Horwood, 1984.

....of the failed one. It does so only for those segments that have become related to the failing one in interaction points. The strategy uses a form of intelligent backtracking in the selection of the segment where alternatives will be sought such that segments that would repeat failure are ignored ([BP84], PN84] Cun88] First, a centralized implementation of this strategy was experimented relying upon a global data structure to keep the information on the segments in the current derivation. This may be an interesting approach for shared memory multiprocessors, but not for distributed memory ....

....main difficulty regards the complexity of the computations that may be defined by each program and top goal. One important topic of research is the improvement of the search strategy by the definition and use of more selective distributed backtracking algorithms, following the approach proposed in [BP84]. We have experimented with distributed backtracking for simple programs, and we feel that in order to make feasible the programming of large realistic applications, further research must be pursued towards refining the language model, particularly the inclusion of modules. Efforts at the ....

M. Bruynooghe and L.M. Pereira. Deduction revision by intelligent backtracking. In J. A. Campbell, editor, Implementations of Prolog, pages 194-- 215. Ellis Horwood, 1984.

No context found.

M. Bruynooghe, and L. Pereira. Deduction revision by intelligent backtracking Implementations of Prolog (J. Campbell, ed.), Ellis Horwood, 1984, pp. 194-215.

No context found.

Bruynooghe, M., and L. Pereira. Deduction revision by intelligent backtracking. In J. Campbell, ed. Implementations of Prolog, Ellis Horwood, 1984.

First 50 documents

Online articles have much greater impact   More about CiteSeer.IST at NUS   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.