A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, 41(2&3):197230, 1999.  @ NUS  Home/Search   Document Details and Download   Summary   Related Articles   Check

....The core principles of this translation have been recently incorporated in SPIN [Hol97] showing similar gains in performance [Hol99] The XMC system can be downloaded from http: www.cs.sunysb.edu lmc. More recently, we have developed techniques using logic program transformations [TS84,PP99,RKRR99] for verifying parameterized systems, i.e. infinite families of finite state systems [RKR 00] a proof tree viewer for justifying successful or failed verification runs for branching time properties [RRR00] a symbolic bisimulation checker (based on the work of [HL95] for ....

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, 1999.

....in [16, 1, 7] syntactically consists in replacing an agent in the body of a program de nition by another one. It is therefore a very general operation and it is able to mimic many other transformations, such as thinning, fattening [3] and folding. In the logic programming area, a lot of research [4, 5, 1, 6, 7, 12, 16, 22, 28, 27] has been devoted to the de nition of applicability conditions sucient to guarantee the correctness of replacement w.r.t. several di erent semantics. See [21] for a survey on transformation techniques for logic languages. The goal of this paper is to provide some natural and relatively simple ....

M. Proietti and A. Pettorossi. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, 41(2-3):197-230, 1999.

....to our deduction system in order to completely automate the deductive process. 1. 1 Related Work Related Work : Program Transformations Unfold fold logic program transformation systems have been extensively used for program synthesis, specialization and optimization [BCD90, BB93, LSW96, PPR97, PP99a] 4 However, relatively little work has been done on using such systems for constructing proofs. Hsiang and Srivas [HS87] extended Prolog s evaluation with limited forward chaining to perform inductive theorem proving. This limited forward chaining step is in fact a restricted form of ....

....of induction proofs of theorems about the original program. However, this method performs conjunctive folding using only a single non recursive clause, and does not perform goal replacement. The idea of using logic program transformations for proving goal equivalences was rst explored in [PP99a] for logic program synthesis. Our work expands the existing body of work with more powerful transformations and algorithms that are central to veri cation of parameterized systems. A more detailed comparison of the relative power of our transformations with the existing literature on unfold fold ....

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, to appear, 1999.

....systems is not possible, for many cases of practical interest, we have identi ed certain heuristics that can be applied to our proof system in order to completely automate the deduction involved. The idea of using logic program transformations for proving goal equivalences was rst explored in [PP99] for logic program synthesis. Our work expands the existing body of work in logic program transformations with more powerful transformation rules and strategies that are central to veri cation of parameterized systems. Note that our transformation rules are also applicable for proving general ....

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, 41, 1999.

No context found.

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, 41(2&3):197230, 1999.

.... analysis (such as the redundant argument filtering technique presented in [11] This property may also be proved by showing the equivalence: lm(f16;17;16:1;17:1g; D) j=8A; B;C; S; I (newp(A; B;C; S; I) newp1(S; I) which, in turn, may easily be shown by using the unfold fold proof method [16]. 5 Related Work and Conclusions We have presented some transformation rules and strategies for the specialization of constraint logic programs by taking into account their context of use. Our method extends related techniques for the partial evaluation of logic programs because the context of ....

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, 41(2--3):197--230, 1999.

....by Kott [36] and Courcelle [14] in the case of applicative program schemata. The essential idea is that, since the transformation rules preserve a given semantics, the transformation of a program P 1 into a program P 2 is also a proof of the equivalence of P 1 and P 2 w.r.t. that semantics. In [54] this idea has also been developed in the case of de nite logic programs. The method presented in that paper, called unfold fold proof method, allows us to prove the equivalence of conjunctions of atoms w.r.t. the least Herbrand model of a program. In [65] the 30 A. Pettorossi, M. Proietti ....

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, 41(2&3):197230, 1999.

No context found.

Pettorossi, A. and Proietti, M. : Synthesis and Transformation of Logic Programs Using Unfold/Fold Proofs. Journal of Logic Programming Vol.41, N.2&3 (1999) 197--230

....systems is not possible, for many cases of practical interest, wehave identi ed certain heuristics that can be applied to our proof system in order to completely automate the deduction involved. The idea of using logic program transformations for proving goal equivalences was rst explored in [PP99] for logic program synthesis. Our work expands the existing body of work in logic program transformations with more powerful transformation rules and strategies that are central to veri cation of parameterized systems. Note that our transformation rules are also applicable for proving general ....

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. ####### ## ##### ###########, 41, 1999.

....folding steps during program transformation correspond to applications of inductive hypotheses during proofs by induction, and goal replacements correspond to lemma applications. Some transformational techniques for proving equivalences of functional and logic programs are presented in [8, 16] and [20, 24], respectively. In this paper we extend these techniques by introducing a method for proving that a closed rst order formula holds in the perfect model [22] of a locally strati ed logic program P , written as M(P ) j= Perfect models are the usual intended semantics for logic programs with ....

....in [8] proves a similar result by making use of the (restricted) unfold, restricted) fold, cycle elimination, and rede nition rule. We leave for future research further investigation on the power of the various sets of program transformations. The present paper extends the techniques proposed in [20] for showing equivalences of de nite programs w.r.t. least Herbrand models. The main extensions presented here are the following: i) we consider logic programs with strati ed negation and perfect model semantics, ii) we prove rst order formulas, and (iii) we present an automated strategy for ....

[Article contains additional citation context not shown here]

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, 41(2&3):197230, 1999.

.... rewriting rules, and among those techniques we want to present the unfold fold proof method [95, 124] In what follows we present this method and we show how to prove that a given equivalence formula holds in the least Herbrand model of a given program using the unfold fold proof method (see also [119]) For simplicity, here we consider the following transformation rules only: R1) De nition Introduction, R2) Unfolding, R3) Folding, R4) Goal Replacement, and (R8) Equality Introduction and Elimination. De nition 4 (Unfold Fold proof) Let P be a program and Equiv be the formula 8X: 9Y: F ....

.... synthesis method we propose may also be useful to enhance other unfold fold based techniques for avoiding nondeterminism which do not use lemmas (like, for instance, 120] Finally, we would like to point out that our synthesis method can be used for the program specialization as indicated in [119], and the resulting program specialization method is strictly 55 more general than the usual partial evaluation methods [104] Indeed, we are able to specialize our initial program w.r.t. a set of input values which can be described by any predicate, while in [104] the set of input values can ....

[Article contains additional citation context not shown here]

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold /fold proofs. Journal of Logic Programming, 41(2&3):197230, 1999.

.... analysis (such as the redundant argument ltering technique presented in [11] This property may also be proved by showing the equivalence: lm(f16; 17; 16:1; 17:1g; D) j= 8A; B; C; S; I (newp(A; B; C; S; I) newp1(S; I) which, in turn, may easily be shown by using the unfold fold proof method [15]. 7 5 Related Work and Conclusions We have presented some transformation rules and strategies for the specialization of constraint logic programs by taking into account their context of use. Our method extends related techniques for the partial evaluation of logic programs because the context ....

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold/fold proofs. Journal of Logic Programming, 41(2&3):197230, 1999.

....program transformation correspond to applications of inductive hypotheses during proofs by induction, and goal replacements correspond to lemma applications. Some transformational techniques for proving equivalences of functional and logic programs have been already presented in [9, 17] and [21, 26], respectively. In this paper we extend these techniques by introducing a method for proving that a closed rst order formula holds in the perfect model [23] of a locally strati ed logic program P . This property is denoted by M(P ) j= Perfect models are the usual intended semantics for logic ....

....in [9] proves a similar result by making use of the (restricted) unfold, restricted) fold, cycle elimination, and rede nition rule. We leave for future research further investigation on the power of the various sets of program transformations. The present paper extends the techniques proposed in [21] for showing equivalences of de nite programs w.r.t. least Herbrand models. The main extensions presented here are the following: i) we consider logic programs with locally strati ed negation and perfect model semantics, ii) we prove rst order formulas, and (iii) we present an automated ....

[Article contains additional citation context not shown here]

A. Pettorossi and M. Proietti. Synthesis and transformation of logic programs using unfold /fold proofs. Journal of Logic Programming, 41(2&3):197230, 1999.

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.