scientific article; zbMATH DE number 3930339

From MaRDI portal
Publication:3703288





[For the entire collection see Zbl 0568.00022.] The paper presents a survey of methods for proving termination of term rewriting systems. First, undecidability of termination of rewriting systems is proved. Then, various criteria for checking sufficient conditions for termination are presented. The exposition begins with the use of well-founded orderings and simplification orderings for termination proofs, and continues through an exposition of quasi- orderings and multiset orderings to path orderings based on an underlying operator precedence (a partial ordering of the operators). Eventually, results concerning restricted classes of rewriting systems are presented: termination of combinations of rewriting systems and termination criteria for special classes of rewriting systems. Variants of the orderings suitable form the implementational point of view are also discussed. A lot of examples is provided throughout the paper, illustrating the orderings introduced and comparing their usage in termination proofs of various rewriting systems.




Cited in
(69)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3703288)