article

Free access

Proving termination with multiset orderings

Authors:

Nachum Dershowitz,

Zohar MannaAuthors Info & Claims

Communications of the ACM, Volume 22, Issue 8

Pages 465 - 476

https://doi.org/10.1145/359138.359142

Published: 01 August 1979 Publication History

PDF eReader

Abstract

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.

References

[1]

Dijkstra, E.W. A small note on the additive composition of variant functions. Note EWD592, Burroughs Corp., Neunen, The Netherlands, 1976.

Google Scholar

[2]

Floyd, R.W. Assigning meanings to programs. Proc. Symp. in Applied Math., Vol. 19, Amer. Math. Soc., Providence, R.I., pp. 19- 32.

Google Scholar

[3]

Gentzen, G. New version of the consistency proof for elementary number theory (1938). In The Collected Papers of Gerhart Gentzen, M.E. Szabo, Ed., North-Holland, Amsterdam, 1969, pp. 252-286.

Google Scholar

[4]

Gorn, S. Explicit definitions and linguistic dominoes. Proc. Conf. on Syst. and Comptr. Sci., London, Ontario, Sept. 1965, pp. 77-115.

Google Scholar

[5]

Iturriaga, R. Contributions to mechanical mathematics. Ph.D. Th., Carnegie-Mellon U., Pittsburgh, Pa., May 1967.

Google Scholar

[6]

Katz, S.M. and Manna, Z. A closer look at termination. Acta Inform. 5, 4 (1975), 333-352.

Digital Library

Google Scholar

[7]

Knuth, D.E. and Bendix, P.B. Simple word problems in universal algebras. In Computational Problems in Universal Algebras, J. Leech, Ed., Pergamon Press, Oxford, 1969, pp. 263-297,

Google Scholar

[8]

Lankford, D.S. Canonical algebraic simplification in computational logic. Memo ATP-25, Automatic Theorem Proving Project, U. of Texas, Austin, Texas, May 1975.

Google Scholar

[9]

Lipton, R.J. and Snyder, L. On the halting of tree replacement systems. Proc. Conf. on Theoret. Comptr. Sci., Waterloo, Ontario, Aug. 1977, pp. 43-46.

Google Scholar

[10]

Manna, Z. and Ness, S. On the termination of Markov algorithms. Proc. Third Hawaii Int. Conf. on Syst. Sci., Honolulu, Hawaii, Jan. 1970, pp. 789-792.

Google Scholar

[11]

Manna, Z. and Waldinger, R.J. Is SOMETIME sometimes better than ALWAYS? Intermittent assertions in proving program correctness. Comm. ACM 21, 2 (Feb. 1978), 159-172.

Digital Library

Google Scholar

[12]

Plaisted, D. Well-founded orderings for proving the termination of rewrite rules. Memo R-78-932, Dept. of Comptr. Sci., U. of Illinois, Urbana, IlL, July 1978.

Google Scholar

[13]

Plaisted, D. A recursively defined ordering for proving termination of term rewriting systems. Memo R-78-943, Dept. of Comptr. Sci., U. of Illinois, Urbana, I11., Oct. 1978.

Google Scholar

Cited By

View all

Férée HGiessen IGool SShillito I(2024)Mechanised Uniform Interpolation for Modal Logics K, GL, and iSLAutomated Reasoning10.1007/978-3-031-63501-4_3(43-60)Online publication date: 2-Jul-2024
https://doi.org/10.1007/978-3-031-63501-4_3
Hajdu MKovács LRawson MVoronkov A(2024)Reducibility Constraints in SuperpositionAutomated Reasoning10.1007/978-3-031-63498-7_8(115-132)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63498-7_8
Iemhoff R(2024)Proof Theory for Lax LogicDick de Jongh on Intuitionistic and Provability Logics10.1007/978-3-031-47921-2_8(203-229)Online publication date: 26-Jul-2024
https://doi.org/10.1007/978-3-031-47921-2_8
Show More Cited By

Proving termination with multiset orderings
1. Theory of computation
  1. Formal languages and automata theory
    1. Formalisms

Recommendations

Proving termination and multiset orderings
Abstract Relations Between Restricted Termination And Confluence Properties Of Rewrite Systems

We investigate restricted termination and confluence properties of term rewriting systems, in particular weak termination, weak innermost termination, (strong) innermost termination, (strong) termination, and their interrelations. New criteria are ...
Proving termination properties with MU-TERM
AMAST'10: Proceedings of the 13th international conference on Algebraic methodology and software technology

MU-TERM is a tool which can be used to verify a number of termination properties of (variants of) Term Rewriting Systems (TRSs): termination of rewriting, termination of innermost rewriting, termination of order-sorted rewriting, termination of context-...

Comments

Information & Contributors

Information

Published In

Communications of the ACM Volume 22, Issue 8

Aug. 1979

40 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359138

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1979

Published in CACM Volume 22, Issue 8

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

417
Total Citations
View Citations
1,385
Total Downloads

Downloads (Last 12 months)216
Downloads (Last 6 weeks)27

Reflects downloads up to 07 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Férée HGiessen IGool SShillito I(2024)Mechanised Uniform Interpolation for Modal Logics K, GL, and iSLAutomated Reasoning10.1007/978-3-031-63501-4_3(43-60)Online publication date: 2-Jul-2024
https://doi.org/10.1007/978-3-031-63501-4_3
Hajdu MKovács LRawson MVoronkov A(2024)Reducibility Constraints in SuperpositionAutomated Reasoning10.1007/978-3-031-63498-7_8(115-132)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63498-7_8
Iemhoff R(2024)Proof Theory for Lax LogicDick de Jongh on Intuitionistic and Provability Logics10.1007/978-3-031-47921-2_8(203-229)Online publication date: 26-Jul-2024
https://doi.org/10.1007/978-3-031-47921-2_8
Férée Hvan Gool SKrebbers RTraytel DPientka BZdancewic S(2023)Formalizing and Computing Propositional QuantifiersProceedings of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs10.1145/3573105.3575668(148-158)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3573105.3575668
Freund AManca D(2023)Normal functions and maximal order typesJournal of Logic and Computation10.1093/logcom/exad00234:6(1064-1081)Online publication date: 16-Feb-2023
https://doi.org/10.1093/logcom/exad002
Kraus NNordvall Forsberg FXu C(2023)Type-theoretic approaches to ordinalsTheoretical Computer Science10.1016/j.tcs.2023.113843957(113843)Online publication date: May-2023
https://doi.org/10.1016/j.tcs.2023.113843
Sheng YNötzli AReynolds AZohar YDill DGrieskamp WPark JQadeer SBarrett CTinelli C(2023)Reasoning About Vectors: Satisfiability Modulo a Theory of SequencesJournal of Automated Reasoning10.1007/s10817-023-09682-267:3Online publication date: 15-Sep-2023
https://dl.acm.org/doi/10.1007/s10817-023-09682-2
Shillito Ivan der Giessen IGoré RIemhoff R(2023)A New Calculus for Intuitionistic Strong Löb Logic: Strong Termination and Cut-Elimination, FormalisedAutomated Reasoning with Analytic Tableaux and Related Methods10.1007/978-3-031-43513-3_5(73-93)Online publication date: 18-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43513-3_5
Iemhoff R(2022)The G4i Analogue of a G3i Sequent CalculusStudia Logica10.1007/s11225-022-10008-3110:6(1493-1506)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11225-022-10008-3
Bonacina M(2022)Set of Support, Demodulation, Paramodulation: A Historical PerspectiveJournal of Automated Reasoning10.1007/s10817-022-09628-066:4(463-497)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10817-022-09628-0
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Proving termination and multiset orderings

Abstract Relations Between Restricted Termination And Confluence Properties Of Rewrite Systems

Proving termination properties with MU-TERM

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations