Rewrite orderings and termination of rewrite systems (Q4035223)
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 176122
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Rewrite orderings and termination of rewrite systems |
scientific article; zbMATH DE number 176122 |
Statements
18 May 1993
0 references
0.9521139
0 references
0.9288794
0 references
0.91146916
0 references
0.90917856
0 references
0.9014517
0 references
0.8959509
0 references
0.8909372
0 references
0.8908571
0 references
Rewrite orderings and termination of rewrite systems (English)
0 references
[For the entire collection see Zbl 0753.00030.] Recent results on proving uniform termination of term rewrite systems and rewrite systems modulo identities, like associativity and commutativity. Uniform termination is the termination of the rewrite process for any rewriting strategy. Proving uniform termination (later called just termination) of rewrite strategy. Proving uniform termination (later called just termination) of rewrite systems is known to be difficult, probably because it is undecidable [\textit{G. Huet} and \textit{D. S. Lankford}, On the uniform halting problem for term rewriting systems. Technical Report 283, Laboria, France (1978)]. Dauchet has proven that even if one restricts to one left-linear rewrite rule systems [\textit{M. Dauchet}, Simulation of Turing mathines by a left-linear rewrite rule. In \textit{N. Dershowitz}, editor, Proceedings 3rd Conference on Rewriting Techniques and Applications, Chapel Hill, (North Carolina, USA), Lect. Notes Comput. Sci. 355, VII (1989; Zbl 0741.68008)] it is still undecidable.
0 references