TERMINATION FOR DIRECT SUMS OF LEFT-LINEAR COMPLETE TERM REWRITING-SYSTEMS

A term rewriting system is called complete if it is confluent and term inating. We prove that completeness of TRSs is a ''modular'' property (meaning that it stays preserved under direct sums), provided the cons tituent TRSs are left-linear. Here, the direct sum R(0) + R(1) is the union of TRSs R(0), R(1) with disjoint signature. The proof hinges cru cially upon the (non)deterministic collapsing behavior of terms from t he sum TRS.