/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 12 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) QDPOrderProof [EQUIVALENT, 604 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) QDPOrderProof [EQUIVALENT, 0 ms] (11) QDP (12) PisEmptyProof [EQUIVALENT, 0 ms] (13) YES (14) QDP (15) QDPOrderProof [EQUIVALENT, 0 ms] (16) QDP (17) PisEmptyProof [EQUIVALENT, 0 ms] (18) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> SORTSU(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> TE(msubst(te(a), sortSu(t))) SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> SORTSU(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> SORTSU(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> SORTSU(circ(sortSu(t), sortSu(u))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> SORTSU(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> SORTSU(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> SORTSU(circ(sortSu(s), sortSu(t))) TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> SORTSU(circ(sortSu(s), sortSu(t))) The TRS R consists of the following rules: sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> TE(msubst(te(a), sortSu(t))) TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> SORTSU(circ(sortSu(t), sortSu(u))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> SORTSU(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> SORTSU(circ(sortSu(s), sortSu(t))) The TRS R consists of the following rules: sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> SORTSU(circ(sortSu(t), sortSu(u))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> SORTSU(circ(sortSu(s), sortSu(t))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation with max and min functions [POLO,MAXPOLO]: POL(SORTSU(x_1)) = x_1 POL(TE(x_1)) = x_1 POL(circ(x_1, x_2)) = 1 + x_1 + x_2 POL(cons(x_1, x_2)) = max(x_1, x_2) POL(id) = 0 POL(lift) = 0 POL(msubst(x_1, x_2)) = 1 + x_1 + x_2 POL(sop(x_1)) = 0 POL(sortSu(x_1)) = x_1 POL(subst(x_1, x_2)) = x_1 POL(te(x_1)) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: te(msubst(te(a), sortSu(id))) -> te(a) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> TE(msubst(te(a), sortSu(t))) TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> SORTSU(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) The TRS R consists of the following rules: sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) The TRS R consists of the following rules: sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. TE(x1) = x1 msubst(x1, x2) = x1 te(x1) = te(x1) subst(x1, x2) = x1 sortSu(x1) = sortSu id = id Knuth-Bendix order [KBO] with precedence:trivial and weight map: dummyConstant=1 te_1=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: te(msubst(te(a), sortSu(id))) -> te(a) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) ---------------------------------------- (11) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> SORTSU(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) The TRS R consists of the following rules: sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> SORTSU(circ(sortSu(s), sortSu(t))) SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> SORTSU(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. SORTSU(x1) = x1 circ(x1, x2) = circ(x1, x2) sortSu(x1) = x1 cons(x1, x2) = cons(x2) id = id Knuth-Bendix order [KBO] with precedence:circ_2 > cons_1 and weight map: circ_2=1 cons_1=1 id=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) ---------------------------------------- (16) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) -> sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) -> sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) -> sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))) sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) -> sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u))))) sortSu(circ(sortSu(s), sortSu(id))) -> sortSu(s) sortSu(circ(sortSu(id), sortSu(s))) -> sortSu(s) sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) -> sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u))) te(subst(te(a), sortSu(id))) -> te(a) te(msubst(te(a), sortSu(id))) -> te(a) te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) -> te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (18) YES