Generalized sufficient conditions for modular termination of rewriting (Q1328180): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:57, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generalized sufficient conditions for modular termination of rewriting |
scientific article |
Statements
Generalized sufficient conditions for modular termination of rewriting (English)
0 references
4 July 1994
0 references
Since rewrite systems can be seen as programs of a functional programming language, there is some interest in the following question: Given two rewrite systems \(R_ 1\) and \(R_ 2\), both having property \(P\), under which conditions does the union \(R_ 1 \cup R_ 2\) have property \(P\)? In the paper, this problem is studied for \(P\) meaning ``terminating''. This problem is nontrivial since an example of Toyama shows that \(R_ 1 \cup R_ 2\) need not be terminating even if \(R_ 1\) and \(R_ 2\) are terminating and disjoint (i.e. are defined over disjoint signatures). The property \(P\) is called modular, if \(R_ 1 \cup R_ 2\) has property \(P\) whenever \(R_ 1\) and \(R_ 2\) are disjoint and have property \(P\). It is known that termination is modular on some restricted classes of rewrite systems, e.g. on the classes of (a) non-duplicating, (b) non-collapsing, (c) left-linear and confluent, and (d) confluent overlay systems. The paper generalizes these results by classifying exactly those cases where \(R_ 1 \cup R_ 2\) is non-terminating: \(R\) is called ``termination preserving under non-deterministic collapses'' if termination of \(R\) implies termination of \(R \cup \{G(x,y) \to x\), \(G(x,y) \to y\}\), where \(G\) is a new function symbol. Now the main result of the paper is: ``If \(R_ 1\) and \(R_ 2\) are disjoint terminating rewrite systems and \(R_ 1 \cup R_ 2\) is non-terminating, then one of the systems is not termination preserving under non-deterministic collapses and the other one is collapsing''. Unfortunately, it is undecidable whether \(R\) is termination preserving under non-deterministic collapses. The main result is generalized in several directions. For example, the assumption that \(R_ 1\) and \(R_ 2\) are disjoint can be weakend to the assumption that \(R_ 1\) and \(R_ 2\) share only constructor symbols.
0 references
disjoint union
0 references
rewrite systems
0 references
functional programming language
0 references