Abstract

In this paper we extend the recent divide and conquer technique of Middeldorp and Toyama for establishing (semi-)completeness of constructor systems to conditional constructor systems. We show that both completeness (i.e. the combination of confluence and strong normalization) and semi-completeness (confluence plus weak normalization) are decomposable properties of conditional constructor systems without extra variables in the conditions of the rewrite rules.

BibTeX Entry

@inproceedings{M-CTRS92,
 author    = "Aart Middeldorp",
 title     = "Completeness of Combinations of Conditional Constructor
              System",
 booktitle = "Proceedings of the 3rd International Workshop on Conditional
              Term Rewriting Systems",
 series    = "Lecture Notes in Computer Science",
 volume    = 656,
 pages     = "82--96",
 year      = 1993,
 doi       = "10.1007/3-540-56393-8\_6"
}