Abstract

In this paper we extend the 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 normalisation) and semi-completeness (confluence plus weak normalisation) are decomposable properties of conditional constructor systems without extra variables in the conditions of the rewrite rules.

BibTeX Entry

@article{M-JSC94,
 author    = "Aart Middeldorp",
 title     = "Completeness of Combinations of Conditional Constructor
              Systems",
 journal   = "Journal of Symbolic Computation",
 volume    = 17,
 number    = 1,
 pages     = "3--21",
 year      = 1994,
 doi       = "10.1006/jsco.1994.1002"
}