Last edited by Gonos
Saturday, May 16, 2020 | History

5 edition of Well-founded orderings for proving termination of systems of rewrite rules found in the catalog.

Well-founded orderings for proving termination of systems of rewrite rules

David A. Plaisted

Well-founded orderings for proving termination of systems of rewrite rules

by David A. Plaisted

  • 247 Want to read
  • 34 Currently reading

Published by Dept. of Computer Science, University of Illinois at Urbana-Champaign in Urbana .
Written in English

    Subjects:
  • Computer programs -- Verification,
  • Recursive programming

  • Edition Notes

    Bibliography: p. 34.

    Statementby David A. Plaisted.
    SeriesUIUCDCS-R-78 ; 932
    Classifications
    LC ClassificationsQA76 .I4 no. 932, QA76.6 .I4 no. 932
    The Physical Object
    Pagination34 p. ;
    Number of Pages34
    ID Numbers
    Open LibraryOL4067518M
    LC Control Number79620560

    This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions. All rig. The reduction relation is here defined firstly by the direction of the rules and secondly by some metric that yields efficient algorithms. These systems are general enough to discuss the basic notions of arbitrary replacement systems, such as termination, confluence, and the Church-Rosser property in its original meaning.

    Dexter Kozen and Maria-Cristina Patron. Certification of compiler optimizations using Kleene algebra with tests. In John Lloyd, Veronica Dahl, Ulrich Furbach, Manfred Kerber, Kung-Kiu Lau, Catuscia Palamidessi, Luis Moniz Pereira, Yehoshua Sagiv, and Peter J. Stuckey, editors, Proc. 1st Int. Conf. Computational Logic (CL), volume of Lecture Notes in Artificial Intelligence, pages Highman's Lemma is a property about well quasi-orderings on strings. In this paper a formal proof of this result is presented, using a termination argument based on well-founded multiset extensions. A Formal Proof of Dickson's Lemma in ACL2, F.J. Martín-Mateos, J.A. Alonso, M.J. Hidalgo and J.L. Ruiz-Reina.

    This book constitutes the refereed proceedings of the 12th International Conference on Artificial Intelligence and Symbolic Computation, AISC , held in Seville, Spain, in December The 15 full papers presented together with 2 invited papers were carefully reviewed and selected from 22 . The contributions focus on topics like Gröbner bases, real algebraic geometry, Lie algebras, factorisation of polynomials, integer programming, permutation groups, differential equations, coding theory, automatic theorem proving, and polyhedral geometry. This book is a must-read for everybody interested in computer algebra.


Share this book
You might also like
Managers and workers in engineering industries

Managers and workers in engineering industries

French contemporary art

French contemporary art

The importunate begger for things necessary, or necessity, without deniall

The importunate begger for things necessary, or necessity, without deniall

third Miss Symons

third Miss Symons

Some apparatus for specialised use on sites of new foundations.

Some apparatus for specialised use on sites of new foundations.

British Aerospace Public Limited Company and VSEL plc

British Aerospace Public Limited Company and VSEL plc

Industrial application of enzymes based on carbohydrate-based material

Industrial application of enzymes based on carbohydrate-based material

Personal identity and fractured selves

Personal identity and fractured selves

An attempt to illustrate and confirm the ecclesiastical constitution of the consociated churches, in the colony of Connecticut.

An attempt to illustrate and confirm the ecclesiastical constitution of the consociated churches, in the colony of Connecticut.

Air carrier aviation demand forecasts for the central Puget Sound region, 1970-2000

Air carrier aviation demand forecasts for the central Puget Sound region, 1970-2000

The Girl Scout Pioneers Or Winning the First B. C.

The Girl Scout Pioneers Or Winning the First B. C.

Employment in Britain.

Employment in Britain.

Advanced Topics in Artificial Intelligence

Advanced Topics in Artificial Intelligence

sea in education.

sea in education.

Rum Jungle.

Rum Jungle.

John Hunter, the forgotten tenant of Craigcrook

John Hunter, the forgotten tenant of Craigcrook

The galaxy is rated G

The galaxy is rated G

Well-founded orderings for proving termination of systems of rewrite rules by David A. Plaisted Download PDF EPUB FB2

Plaisted, D. “Well-founded orderings for proving termination of systems of rewrite rules”, Report R, Department of Computer Science, University of Illinois, Urbana, IL, July Google Scholar. Abstract. In this paper an important problem in the domain of term rewriting, the termination of (conditional) rewrite systems, is dealt with.

We show that in many applications, well-founded orderings on terms which only make use of syntactic information of a rewrite systemR, do not suffice for proving termination sometimes semantic information is needed to orient a rewrite by: The orderings and the notion of strictness can also be generalised.

The techniques to achieve this are similar to those used in [Gan8O, dV87]. Moreover, the result that termination proofs can be given with a well-founded monotone algebra in [Zan93] carries over to HRSs with simple conditions on the well-founded ordering.

With this technique. Termination of Constructor Systems. applications, well-founded orderings on terms which only make use of syntactic information of a rewrite systemR, do not suffice for proving termination ofR. Several well-founded syntactic orderings have been proposed in the literature for proving the termination of rewrite systems.

Recursive path orderings (RPO) and their extensions are the most. REWRITE SYSTEMS A term-rewriting (rewrite) system R over a set of terms T is a finite set of rewrite rules, each of the form l[-~] ~ r[, where l and r are terms in T containing variables ft. Such a rule may be applied to a term t in T if a sub- term s of t matches the left-hand side with some substitution # of terms for the variables appearing Cited by: This survey describes methods for proving that systems of rewrite rules are terminating programs.

We illustrate the use in termination proofs of various kinds of orderings on terms, including polyn. This banner text can have markup. web; books; video; audio; software; images; Toggle navigation. In this paper we describe a new class of orderings—associative path orderings—for proving termination of associative-commutative term rewriting orderings are based on the concept of simplification orderings and extend the well-known recursive path orderings to E - congruence classes, where E is an equational theory consisting of associativity and commutativity by: Motivation.

Intuitively, a reduction order R relates two formal expressions s and t if t is properly "simpler" than s in some sense. For example, simplification of terms may be a part of a computer algebra program, and may be using the rule set { x+0 → x, 0+x → x, x*0 → 0, 0*x → 0, x*1 → x, 1*x → x}.In order to prove impossibility of endless loops when simplifying a term, the.

Simple termination of rewrite systems ’ Aart Middeldorp ‘,*s2, Hans Zantema b terms is indeed a well-founded order. Proving irreflexivity and transitivity often turns out to be feasible, using some induction and case analysis.

Rewrite rules (2, r) will henceforth be written as 1 + r. 3 Acknowledgments This document is still under development. It has been used, generaly in part, as a support for D.E.A.

and Master lectures in Nancy and several other national or international schools. In mathematics, the Dershowitz–Manna ordering is a well-founded ordering on multisets named after Nachum Dershowitz and Zohar is often used in context of termination of programs or term rewriting systems.

Suppose that. Mathematical Theory and Modeling ISSN (Paper) ISSN (Online) Vol.3, No, Simplified 1Proof of Kruskal’s Tree Theorem 2* 2. International peer-reviewed academic journals call for papers,   Blanqui, F. () A type-based termination criterion for dependently-typed higher-order rewrite systems.

In Proceedings of the 15th International Conference on Rewriting Techniques and Applications, Lecture Notes in Computer Science, vol. work protocols, operating systems, and distributed databases), as termination proofs are used to show that some desirable behavior is not postponed forever, i.e., to establish liveness properties.

Proving termination amounts to showing that a relation is well-founded [1]. Since every well-founded. • An ordering is well-founded if there exists no infinite strictly decreasing sequence termination property.

However, Huet and Lankford [5] showed that the termination problem for rewriting systems is undecidable; therefore no uniform method based, for instance, on orderings can exist. But proving termination of particular rewriting system is.

The relationship between several simplification orderings is investigated: the path of subterms ordering, the recursive path ordering and the recursive decomposition ordering.

The recursive decompo Author: RusinowitchMichael. Kruskal's tree theorem plays a fundamental role in computer science because it is one of the main tools for showing that certain orderings on trees are well-founded.

These orderings play a crucial role in proving the termination of rewrite rules and the correctness of the. Nachum Dershowitz, Dec.“Jumping and Escaping: Modular Termination and the Abstract Path Ordering”, Theoretical Computer Science, Special issue: New Directions in Rewriting (Honoring the 60th Birthday of Yoshihito Toyama), vol.pp.

Abstract Simple termination (or its algebraic counterpart, the simplification orderings) is the (often indirect) basis of most existing automatic techniques for proving termination of rule-based programs (e.g., Knuth-Bendix, polynomial, or recursive path orderings, but also DP-simple termination, etc.).

An interesting framework for such.work protocols, operating systems, distributed databases, pipelined machines, etc.): they are used to prove liveness properties i.e., to show that some desirable behavior is not postponed forever. Proving ter-mination amounts to showing that a relation is well-founded [2].

Any well-founded relation can be extended to a total order, giving rise to.