×

Termination of (canonical) context-sensitive rewriting. (English) Zbl 1045.68074

Tison, Sophie (ed.), Rewriting techniques and applications. 13th international conference, RTA 2002, Copenhagen, Denmark, July 22–24, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43916-1). Lect. Notes Comput. Sci. 2378, 296-310 (2002).
Summary: Context-sensitive rewriting (CSR) is a restriction of rewriting which forbids reductions on selected arguments of functions. A replacement map discriminates, for each symbol of the signature, the argument positions on which replacements are allowed. If the replacement restrictions are less restrictive than those expressed by the so-called canonical replacement map, then CSR can be used for computing (infinite) normal forms of terms. Termination of such canonical CSR is desirable when using CSR for these purposes. Existing transformations for proving termination of CSR fulfill a number of new properties when used for proving termination of canonical CSR.
For the entire collection see [Zbl 0992.00043].

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: Link