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

      0 references
      18 May 1993
      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

      Identifiers