No label defined (Q3703288)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3930339
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3930339 |
Statements
1985
0 references
decidability
0 references
precedence orderings
0 references
survey
0 references
term rewriting systems
0 references
undecidability
0 references
simplification orderings
0 references
quasi-orderings
0 references
multiset orderings
0 references
path orderings
0 references
0.9108126759529114
0 references
0.8875071406364441
0 references
0.8850342035293579
0 references
0.862834632396698
0 references
0.8564119935035706
0 references
[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.
0 references