Can I read Proving Termination with Multiset Orderings on EtoBox?

Proving Termination with Multiset Orderings by Nachum Dershowitz; Zohar Manna is a scholarly article available to read on EtoBox.

What is Proving Termination with Multiset Orderings about?

A common tool for proving the termination of programs is the __well-founded set__ , a set ordered in such a way as to admit no infinite descending sequences. The basic approach is to find a __termination function__ that maps the values of the program variables into some well-founded set, such that the value of the termination function is repeatedly reduced throughout the computation. All too often, the termination functions required are difficult to find and are of a complexity out of proportion to the program under consideration. __Multisets__ ( __bags__ ) over a given well-founded set __S__ are sets that admit multiple occurrences of elements taken from __S__ . The given ordering on __S__ induces an ordering on the finite multisets over __S__ . This __multiset ordering__ is shown to be well-founded. The multiset ordering enables the use of relatively simple and intuitive termination functions in otherwise difficult termination proofs. In particular, the multiset ordering is used to prove the termination of __production systems__ , programs defined in terms of sets of rewriting rules.

Author

Nachum Dershowitz; Zohar Manna

Publisher

ACM

Published

1979

Language

EN