/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO 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 disproven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 1 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) TransformationProof [EQUIVALENT, 0 ms] (6) QDP (7) TransformationProof [EQUIVALENT, 0 ms] (8) QDP (9) TransformationProof [EQUIVALENT, 0 ms] (10) QDP (11) NonTerminationLoopProof [COMPLETE, 9840 ms] (12) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(x1) -> x1 o(x1) -> x1 l(x1) -> x1 S(x1) -> x1 +(x1, x2) -> x2 +(x1, x2) -> x1 P(x1, x2, x3) -> x3 P(x1, x2, x3) -> x2 P(x1, x2, x3) -> x1 M(x1, x2, x3) -> x3 M(x1, x2, x3) -> x2 M(x1, x2, x3) -> x1 J1(x1, x2) -> x2 J1(x1, x2) -> x1 J2(x1, x2, x3) -> x3 J2(x1, x2, x3) -> x2 J2(x1, x2, x3) -> x1 Q11(x1, x2) -> x2 Q11(x1, x2) -> x1 Q21(x1, x2, x3) -> x3 Q21(x1, x2, x3) -> x2 Q21(x1, x2, x3) -> x1 Q22(x1, x2, x3) -> x3 Q22(x1, x2, x3) -> x2 Q22(x1, x2, x3) -> x1 R1(x1, x2, x3) -> x3 R1(x1, x2, x3) -> x2 R1(x1, x2, x3) -> x1 R2(x1, x2, x3, x4) -> x4 R2(x1, x2, x3, x4) -> x3 R2(x1, x2, x3, x4) -> x2 R2(x1, x2, x3, x4) -> x1 P(0, 0, 0) -> S(0) +(x, S(y)) -> S(+(x, y)) a(l(x)) -> l(a(a(x))) l(o(x)) -> o(l(l(x))) o(x) -> l(x) l(x) -> a(x) a(S(x)) -> S(l(x)) a(+(x, y)) -> +(l(x), y) a(+(x, y)) -> +(x, l(y)) a(P(x1, x2, x3)) -> P(x1, x2, l(x3)) a(P(x1, x2, x3)) -> P(x1, l(x2), x3) a(P(x1, x2, x3)) -> P(l(x1), x2, x3) +(x, o(y)) -> o(+(x, y)) P(x1, x2, o(x3)) -> o(P(x1, x2, x3)) P(x1, o(x2), x3) -> o(P(x1, x2, x3)) P(o(x1), x2, x3) -> o(P(x1, x2, x3)) M(x1, x2, l(y)) -> +(M(x1, x2, y), P(x1, x2, y)) J2(x1, l(x2), y) -> P(x1, J2(x1, x2, y), 0) J1(l(x1), y) -> P(J1(x1, y), 0, 0) a(S(x)) -> o(x) P(0, 0, S(y)) -> o(M(0, 0, y)) P(0, 0, P(x1, x2, y)) -> o(M(x1, x2, y)) P(x1, S(x2), y) -> o(J2(x1, x2, y)) P(S(x1), 0, y) -> o(J1(x1, y)) P(x1, S(x2), S(y)) -> o(J2(x1, x2, P(x1, S(x2), y))) P(S(x1), 0, S(y)) -> o(J1(x1, P(S(x1), 0, y))) a(P(x1, x2, 0)) -> Q22(x1, a(x2), x2) a(P(x1, x2, 0)) -> Q21(x1, a(x2), x1) a(P(x1, 0, 0)) -> Q11(a(x1), x1) Q22(x1, o(x2), y) -> o(P(x1, x2, y)) Q21(x1, o(x2), y) -> o(P(x1, x2, y)) Q11(o(x1), y) -> o(P(x1, 0, y)) a(P(x1, x2, S(y))) -> R2(x1, a(x2), x2, y) a(P(x1, 0, S(y))) -> R1(a(x1), x1, y) R2(x1, o(x2), y, z) -> o(P(x1, x2, P(x1, y, z))) R1(o(x1), y, z) -> o(P(x1, 0, P(y, 0, z))) 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: P^1(0, 0, 0) -> S^1(0) +^1(x, S(y)) -> S^1(+(x, y)) +^1(x, S(y)) -> +^1(x, y) A(l(x)) -> L(a(a(x))) A(l(x)) -> A(a(x)) A(l(x)) -> A(x) L(o(x)) -> O(l(l(x))) L(o(x)) -> L(l(x)) L(o(x)) -> L(x) O(x) -> L(x) L(x) -> A(x) A(S(x)) -> S^1(l(x)) A(S(x)) -> L(x) A(+(x, y)) -> +^1(l(x), y) A(+(x, y)) -> L(x) A(+(x, y)) -> +^1(x, l(y)) A(+(x, y)) -> L(y) A(P(x1, x2, x3)) -> P^1(x1, x2, l(x3)) A(P(x1, x2, x3)) -> L(x3) A(P(x1, x2, x3)) -> P^1(x1, l(x2), x3) A(P(x1, x2, x3)) -> L(x2) A(P(x1, x2, x3)) -> P^1(l(x1), x2, x3) A(P(x1, x2, x3)) -> L(x1) +^1(x, o(y)) -> O(+(x, y)) +^1(x, o(y)) -> +^1(x, y) P^1(x1, x2, o(x3)) -> O(P(x1, x2, x3)) P^1(x1, x2, o(x3)) -> P^1(x1, x2, x3) P^1(x1, o(x2), x3) -> O(P(x1, x2, x3)) P^1(x1, o(x2), x3) -> P^1(x1, x2, x3) P^1(o(x1), x2, x3) -> O(P(x1, x2, x3)) P^1(o(x1), x2, x3) -> P^1(x1, x2, x3) M^1(x1, x2, l(y)) -> +^1(M(x1, x2, y), P(x1, x2, y)) M^1(x1, x2, l(y)) -> M^1(x1, x2, y) M^1(x1, x2, l(y)) -> P^1(x1, x2, y) J2^1(x1, l(x2), y) -> P^1(x1, J2(x1, x2, y), 0) J2^1(x1, l(x2), y) -> J2^1(x1, x2, y) J1^1(l(x1), y) -> P^1(J1(x1, y), 0, 0) J1^1(l(x1), y) -> J1^1(x1, y) A(S(x)) -> O(x) P^1(0, 0, S(y)) -> O(M(0, 0, y)) P^1(0, 0, S(y)) -> M^1(0, 0, y) P^1(0, 0, P(x1, x2, y)) -> O(M(x1, x2, y)) P^1(0, 0, P(x1, x2, y)) -> M^1(x1, x2, y) P^1(x1, S(x2), y) -> O(J2(x1, x2, y)) P^1(x1, S(x2), y) -> J2^1(x1, x2, y) P^1(S(x1), 0, y) -> O(J1(x1, y)) P^1(S(x1), 0, y) -> J1^1(x1, y) P^1(x1, S(x2), S(y)) -> O(J2(x1, x2, P(x1, S(x2), y))) P^1(x1, S(x2), S(y)) -> J2^1(x1, x2, P(x1, S(x2), y)) P^1(x1, S(x2), S(y)) -> P^1(x1, S(x2), y) P^1(S(x1), 0, S(y)) -> O(J1(x1, P(S(x1), 0, y))) P^1(S(x1), 0, S(y)) -> J1^1(x1, P(S(x1), 0, y)) P^1(S(x1), 0, S(y)) -> P^1(S(x1), 0, y) A(P(x1, x2, 0)) -> Q22^1(x1, a(x2), x2) A(P(x1, x2, 0)) -> A(x2) A(P(x1, x2, 0)) -> Q21^1(x1, a(x2), x1) A(P(x1, 0, 0)) -> Q11^1(a(x1), x1) A(P(x1, 0, 0)) -> A(x1) Q22^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q22^1(x1, o(x2), y) -> P^1(x1, x2, y) Q21^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q21^1(x1, o(x2), y) -> P^1(x1, x2, y) Q11^1(o(x1), y) -> O(P(x1, 0, y)) Q11^1(o(x1), y) -> P^1(x1, 0, y) A(P(x1, x2, S(y))) -> R2^1(x1, a(x2), x2, y) A(P(x1, x2, S(y))) -> A(x2) A(P(x1, 0, S(y))) -> R1^1(a(x1), x1, y) A(P(x1, 0, S(y))) -> A(x1) R2^1(x1, o(x2), y, z) -> O(P(x1, x2, P(x1, y, z))) R2^1(x1, o(x2), y, z) -> P^1(x1, x2, P(x1, y, z)) R2^1(x1, o(x2), y, z) -> P^1(x1, y, z) R1^1(o(x1), y, z) -> O(P(x1, 0, P(y, 0, z))) R1^1(o(x1), y, z) -> P^1(x1, 0, P(y, 0, z)) R1^1(o(x1), y, z) -> P^1(y, 0, z) The TRS R consists of the following rules: a(x1) -> x1 o(x1) -> x1 l(x1) -> x1 S(x1) -> x1 +(x1, x2) -> x2 +(x1, x2) -> x1 P(x1, x2, x3) -> x3 P(x1, x2, x3) -> x2 P(x1, x2, x3) -> x1 M(x1, x2, x3) -> x3 M(x1, x2, x3) -> x2 M(x1, x2, x3) -> x1 J1(x1, x2) -> x2 J1(x1, x2) -> x1 J2(x1, x2, x3) -> x3 J2(x1, x2, x3) -> x2 J2(x1, x2, x3) -> x1 Q11(x1, x2) -> x2 Q11(x1, x2) -> x1 Q21(x1, x2, x3) -> x3 Q21(x1, x2, x3) -> x2 Q21(x1, x2, x3) -> x1 Q22(x1, x2, x3) -> x3 Q22(x1, x2, x3) -> x2 Q22(x1, x2, x3) -> x1 R1(x1, x2, x3) -> x3 R1(x1, x2, x3) -> x2 R1(x1, x2, x3) -> x1 R2(x1, x2, x3, x4) -> x4 R2(x1, x2, x3, x4) -> x3 R2(x1, x2, x3, x4) -> x2 R2(x1, x2, x3, x4) -> x1 P(0, 0, 0) -> S(0) +(x, S(y)) -> S(+(x, y)) a(l(x)) -> l(a(a(x))) l(o(x)) -> o(l(l(x))) o(x) -> l(x) l(x) -> a(x) a(S(x)) -> S(l(x)) a(+(x, y)) -> +(l(x), y) a(+(x, y)) -> +(x, l(y)) a(P(x1, x2, x3)) -> P(x1, x2, l(x3)) a(P(x1, x2, x3)) -> P(x1, l(x2), x3) a(P(x1, x2, x3)) -> P(l(x1), x2, x3) +(x, o(y)) -> o(+(x, y)) P(x1, x2, o(x3)) -> o(P(x1, x2, x3)) P(x1, o(x2), x3) -> o(P(x1, x2, x3)) P(o(x1), x2, x3) -> o(P(x1, x2, x3)) M(x1, x2, l(y)) -> +(M(x1, x2, y), P(x1, x2, y)) J2(x1, l(x2), y) -> P(x1, J2(x1, x2, y), 0) J1(l(x1), y) -> P(J1(x1, y), 0, 0) a(S(x)) -> o(x) P(0, 0, S(y)) -> o(M(0, 0, y)) P(0, 0, P(x1, x2, y)) -> o(M(x1, x2, y)) P(x1, S(x2), y) -> o(J2(x1, x2, y)) P(S(x1), 0, y) -> o(J1(x1, y)) P(x1, S(x2), S(y)) -> o(J2(x1, x2, P(x1, S(x2), y))) P(S(x1), 0, S(y)) -> o(J1(x1, P(S(x1), 0, y))) a(P(x1, x2, 0)) -> Q22(x1, a(x2), x2) a(P(x1, x2, 0)) -> Q21(x1, a(x2), x1) a(P(x1, 0, 0)) -> Q11(a(x1), x1) Q22(x1, o(x2), y) -> o(P(x1, x2, y)) Q21(x1, o(x2), y) -> o(P(x1, x2, y)) Q11(o(x1), y) -> o(P(x1, 0, y)) a(P(x1, x2, S(y))) -> R2(x1, a(x2), x2, y) a(P(x1, 0, S(y))) -> R1(a(x1), x1, y) R2(x1, o(x2), y, z) -> o(P(x1, x2, P(x1, y, z))) R1(o(x1), y, z) -> o(P(x1, 0, P(y, 0, z))) 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 3 less nodes. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: P^1(x1, x2, o(x3)) -> O(P(x1, x2, x3)) O(x) -> L(x) L(o(x)) -> O(l(l(x))) L(o(x)) -> L(l(x)) L(o(x)) -> L(x) L(x) -> A(x) A(l(x)) -> L(a(a(x))) A(l(x)) -> A(a(x)) A(l(x)) -> A(x) A(S(x)) -> L(x) A(+(x, y)) -> +^1(l(x), y) +^1(x, S(y)) -> +^1(x, y) +^1(x, o(y)) -> O(+(x, y)) +^1(x, o(y)) -> +^1(x, y) A(+(x, y)) -> L(x) A(+(x, y)) -> +^1(x, l(y)) A(+(x, y)) -> L(y) A(P(x1, x2, x3)) -> P^1(x1, x2, l(x3)) P^1(x1, x2, o(x3)) -> P^1(x1, x2, x3) P^1(x1, o(x2), x3) -> O(P(x1, x2, x3)) P^1(x1, o(x2), x3) -> P^1(x1, x2, x3) P^1(o(x1), x2, x3) -> O(P(x1, x2, x3)) P^1(o(x1), x2, x3) -> P^1(x1, x2, x3) P^1(0, 0, S(y)) -> O(M(0, 0, y)) P^1(0, 0, S(y)) -> M^1(0, 0, y) M^1(x1, x2, l(y)) -> +^1(M(x1, x2, y), P(x1, x2, y)) M^1(x1, x2, l(y)) -> M^1(x1, x2, y) M^1(x1, x2, l(y)) -> P^1(x1, x2, y) P^1(0, 0, P(x1, x2, y)) -> O(M(x1, x2, y)) P^1(0, 0, P(x1, x2, y)) -> M^1(x1, x2, y) P^1(x1, S(x2), y) -> O(J2(x1, x2, y)) P^1(x1, S(x2), y) -> J2^1(x1, x2, y) J2^1(x1, l(x2), y) -> P^1(x1, J2(x1, x2, y), 0) P^1(S(x1), 0, y) -> O(J1(x1, y)) P^1(S(x1), 0, y) -> J1^1(x1, y) J1^1(l(x1), y) -> P^1(J1(x1, y), 0, 0) J1^1(l(x1), y) -> J1^1(x1, y) J2^1(x1, l(x2), y) -> J2^1(x1, x2, y) P^1(x1, S(x2), S(y)) -> O(J2(x1, x2, P(x1, S(x2), y))) P^1(x1, S(x2), S(y)) -> J2^1(x1, x2, P(x1, S(x2), y)) P^1(x1, S(x2), S(y)) -> P^1(x1, S(x2), y) P^1(S(x1), 0, S(y)) -> O(J1(x1, P(S(x1), 0, y))) P^1(S(x1), 0, S(y)) -> J1^1(x1, P(S(x1), 0, y)) P^1(S(x1), 0, S(y)) -> P^1(S(x1), 0, y) A(P(x1, x2, x3)) -> L(x3) A(P(x1, x2, x3)) -> P^1(x1, l(x2), x3) A(P(x1, x2, x3)) -> L(x2) A(P(x1, x2, x3)) -> P^1(l(x1), x2, x3) A(P(x1, x2, x3)) -> L(x1) A(S(x)) -> O(x) A(P(x1, x2, 0)) -> Q22^1(x1, a(x2), x2) Q22^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q22^1(x1, o(x2), y) -> P^1(x1, x2, y) A(P(x1, x2, 0)) -> A(x2) A(P(x1, x2, 0)) -> Q21^1(x1, a(x2), x1) Q21^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q21^1(x1, o(x2), y) -> P^1(x1, x2, y) A(P(x1, 0, 0)) -> Q11^1(a(x1), x1) Q11^1(o(x1), y) -> O(P(x1, 0, y)) Q11^1(o(x1), y) -> P^1(x1, 0, y) A(P(x1, 0, 0)) -> A(x1) A(P(x1, x2, S(y))) -> R2^1(x1, a(x2), x2, y) R2^1(x1, o(x2), y, z) -> O(P(x1, x2, P(x1, y, z))) R2^1(x1, o(x2), y, z) -> P^1(x1, x2, P(x1, y, z)) R2^1(x1, o(x2), y, z) -> P^1(x1, y, z) A(P(x1, x2, S(y))) -> A(x2) A(P(x1, 0, S(y))) -> R1^1(a(x1), x1, y) R1^1(o(x1), y, z) -> O(P(x1, 0, P(y, 0, z))) R1^1(o(x1), y, z) -> P^1(x1, 0, P(y, 0, z)) R1^1(o(x1), y, z) -> P^1(y, 0, z) A(P(x1, 0, S(y))) -> A(x1) The TRS R consists of the following rules: a(x1) -> x1 o(x1) -> x1 l(x1) -> x1 S(x1) -> x1 +(x1, x2) -> x2 +(x1, x2) -> x1 P(x1, x2, x3) -> x3 P(x1, x2, x3) -> x2 P(x1, x2, x3) -> x1 M(x1, x2, x3) -> x3 M(x1, x2, x3) -> x2 M(x1, x2, x3) -> x1 J1(x1, x2) -> x2 J1(x1, x2) -> x1 J2(x1, x2, x3) -> x3 J2(x1, x2, x3) -> x2 J2(x1, x2, x3) -> x1 Q11(x1, x2) -> x2 Q11(x1, x2) -> x1 Q21(x1, x2, x3) -> x3 Q21(x1, x2, x3) -> x2 Q21(x1, x2, x3) -> x1 Q22(x1, x2, x3) -> x3 Q22(x1, x2, x3) -> x2 Q22(x1, x2, x3) -> x1 R1(x1, x2, x3) -> x3 R1(x1, x2, x3) -> x2 R1(x1, x2, x3) -> x1 R2(x1, x2, x3, x4) -> x4 R2(x1, x2, x3, x4) -> x3 R2(x1, x2, x3, x4) -> x2 R2(x1, x2, x3, x4) -> x1 P(0, 0, 0) -> S(0) +(x, S(y)) -> S(+(x, y)) a(l(x)) -> l(a(a(x))) l(o(x)) -> o(l(l(x))) o(x) -> l(x) l(x) -> a(x) a(S(x)) -> S(l(x)) a(+(x, y)) -> +(l(x), y) a(+(x, y)) -> +(x, l(y)) a(P(x1, x2, x3)) -> P(x1, x2, l(x3)) a(P(x1, x2, x3)) -> P(x1, l(x2), x3) a(P(x1, x2, x3)) -> P(l(x1), x2, x3) +(x, o(y)) -> o(+(x, y)) P(x1, x2, o(x3)) -> o(P(x1, x2, x3)) P(x1, o(x2), x3) -> o(P(x1, x2, x3)) P(o(x1), x2, x3) -> o(P(x1, x2, x3)) M(x1, x2, l(y)) -> +(M(x1, x2, y), P(x1, x2, y)) J2(x1, l(x2), y) -> P(x1, J2(x1, x2, y), 0) J1(l(x1), y) -> P(J1(x1, y), 0, 0) a(S(x)) -> o(x) P(0, 0, S(y)) -> o(M(0, 0, y)) P(0, 0, P(x1, x2, y)) -> o(M(x1, x2, y)) P(x1, S(x2), y) -> o(J2(x1, x2, y)) P(S(x1), 0, y) -> o(J1(x1, y)) P(x1, S(x2), S(y)) -> o(J2(x1, x2, P(x1, S(x2), y))) P(S(x1), 0, S(y)) -> o(J1(x1, P(S(x1), 0, y))) a(P(x1, x2, 0)) -> Q22(x1, a(x2), x2) a(P(x1, x2, 0)) -> Q21(x1, a(x2), x1) a(P(x1, 0, 0)) -> Q11(a(x1), x1) Q22(x1, o(x2), y) -> o(P(x1, x2, y)) Q21(x1, o(x2), y) -> o(P(x1, x2, y)) Q11(o(x1), y) -> o(P(x1, 0, y)) a(P(x1, x2, S(y))) -> R2(x1, a(x2), x2, y) a(P(x1, 0, S(y))) -> R1(a(x1), x1, y) R2(x1, o(x2), y, z) -> o(P(x1, x2, P(x1, y, z))) R1(o(x1), y, z) -> o(P(x1, 0, P(y, 0, z))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule A(l(x)) -> A(a(x)) at position [0] we obtained the following new rules [LPAR04]: (A(l(x0)) -> A(x0),A(l(x)) -> A(x)) (A(l(l(x0))) -> A(l(a(a(x0)))),A(l(l(x0))) -> A(l(a(a(x0))))) (A(l(S(x0))) -> A(S(l(x0))),A(l(S(x0))) -> A(S(l(x0)))) (A(l(+(x0, x1))) -> A(+(l(x0), x1)),A(l(+(x0, x1))) -> A(+(l(x0), x1))) (A(l(+(x0, x1))) -> A(+(x0, l(x1))),A(l(+(x0, x1))) -> A(+(x0, l(x1)))) (A(l(P(x0, x1, x2))) -> A(P(x0, x1, l(x2))),A(l(P(x0, x1, x2))) -> A(P(x0, x1, l(x2)))) (A(l(P(x0, x1, x2))) -> A(P(x0, l(x1), x2)),A(l(P(x0, x1, x2))) -> A(P(x0, l(x1), x2))) (A(l(P(x0, x1, x2))) -> A(P(l(x0), x1, x2)),A(l(P(x0, x1, x2))) -> A(P(l(x0), x1, x2))) (A(l(S(x0))) -> A(o(x0)),A(l(S(x0))) -> A(o(x0))) (A(l(P(x0, x1, 0))) -> A(Q22(x0, a(x1), x1)),A(l(P(x0, x1, 0))) -> A(Q22(x0, a(x1), x1))) (A(l(P(x0, x1, 0))) -> A(Q21(x0, a(x1), x0)),A(l(P(x0, x1, 0))) -> A(Q21(x0, a(x1), x0))) (A(l(P(x0, 0, 0))) -> A(Q11(a(x0), x0)),A(l(P(x0, 0, 0))) -> A(Q11(a(x0), x0))) (A(l(P(x0, x1, S(x2)))) -> A(R2(x0, a(x1), x1, x2)),A(l(P(x0, x1, S(x2)))) -> A(R2(x0, a(x1), x1, x2))) (A(l(P(x0, 0, S(x1)))) -> A(R1(a(x0), x0, x1)),A(l(P(x0, 0, S(x1)))) -> A(R1(a(x0), x0, x1))) ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: P^1(x1, x2, o(x3)) -> O(P(x1, x2, x3)) O(x) -> L(x) L(o(x)) -> O(l(l(x))) L(o(x)) -> L(l(x)) L(o(x)) -> L(x) L(x) -> A(x) A(l(x)) -> L(a(a(x))) A(l(x)) -> A(x) A(S(x)) -> L(x) A(+(x, y)) -> +^1(l(x), y) +^1(x, S(y)) -> +^1(x, y) +^1(x, o(y)) -> O(+(x, y)) +^1(x, o(y)) -> +^1(x, y) A(+(x, y)) -> L(x) A(+(x, y)) -> +^1(x, l(y)) A(+(x, y)) -> L(y) A(P(x1, x2, x3)) -> P^1(x1, x2, l(x3)) P^1(x1, x2, o(x3)) -> P^1(x1, x2, x3) P^1(x1, o(x2), x3) -> O(P(x1, x2, x3)) P^1(x1, o(x2), x3) -> P^1(x1, x2, x3) P^1(o(x1), x2, x3) -> O(P(x1, x2, x3)) P^1(o(x1), x2, x3) -> P^1(x1, x2, x3) P^1(0, 0, S(y)) -> O(M(0, 0, y)) P^1(0, 0, S(y)) -> M^1(0, 0, y) M^1(x1, x2, l(y)) -> +^1(M(x1, x2, y), P(x1, x2, y)) M^1(x1, x2, l(y)) -> M^1(x1, x2, y) M^1(x1, x2, l(y)) -> P^1(x1, x2, y) P^1(0, 0, P(x1, x2, y)) -> O(M(x1, x2, y)) P^1(0, 0, P(x1, x2, y)) -> M^1(x1, x2, y) P^1(x1, S(x2), y) -> O(J2(x1, x2, y)) P^1(x1, S(x2), y) -> J2^1(x1, x2, y) J2^1(x1, l(x2), y) -> P^1(x1, J2(x1, x2, y), 0) P^1(S(x1), 0, y) -> O(J1(x1, y)) P^1(S(x1), 0, y) -> J1^1(x1, y) J1^1(l(x1), y) -> P^1(J1(x1, y), 0, 0) J1^1(l(x1), y) -> J1^1(x1, y) J2^1(x1, l(x2), y) -> J2^1(x1, x2, y) P^1(x1, S(x2), S(y)) -> O(J2(x1, x2, P(x1, S(x2), y))) P^1(x1, S(x2), S(y)) -> J2^1(x1, x2, P(x1, S(x2), y)) P^1(x1, S(x2), S(y)) -> P^1(x1, S(x2), y) P^1(S(x1), 0, S(y)) -> O(J1(x1, P(S(x1), 0, y))) P^1(S(x1), 0, S(y)) -> J1^1(x1, P(S(x1), 0, y)) P^1(S(x1), 0, S(y)) -> P^1(S(x1), 0, y) A(P(x1, x2, x3)) -> L(x3) A(P(x1, x2, x3)) -> P^1(x1, l(x2), x3) A(P(x1, x2, x3)) -> L(x2) A(P(x1, x2, x3)) -> P^1(l(x1), x2, x3) A(P(x1, x2, x3)) -> L(x1) A(S(x)) -> O(x) A(P(x1, x2, 0)) -> Q22^1(x1, a(x2), x2) Q22^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q22^1(x1, o(x2), y) -> P^1(x1, x2, y) A(P(x1, x2, 0)) -> A(x2) A(P(x1, x2, 0)) -> Q21^1(x1, a(x2), x1) Q21^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q21^1(x1, o(x2), y) -> P^1(x1, x2, y) A(P(x1, 0, 0)) -> Q11^1(a(x1), x1) Q11^1(o(x1), y) -> O(P(x1, 0, y)) Q11^1(o(x1), y) -> P^1(x1, 0, y) A(P(x1, 0, 0)) -> A(x1) A(P(x1, x2, S(y))) -> R2^1(x1, a(x2), x2, y) R2^1(x1, o(x2), y, z) -> O(P(x1, x2, P(x1, y, z))) R2^1(x1, o(x2), y, z) -> P^1(x1, x2, P(x1, y, z)) R2^1(x1, o(x2), y, z) -> P^1(x1, y, z) A(P(x1, x2, S(y))) -> A(x2) A(P(x1, 0, S(y))) -> R1^1(a(x1), x1, y) R1^1(o(x1), y, z) -> O(P(x1, 0, P(y, 0, z))) R1^1(o(x1), y, z) -> P^1(x1, 0, P(y, 0, z)) R1^1(o(x1), y, z) -> P^1(y, 0, z) A(P(x1, 0, S(y))) -> A(x1) A(l(l(x0))) -> A(l(a(a(x0)))) A(l(S(x0))) -> A(S(l(x0))) A(l(+(x0, x1))) -> A(+(l(x0), x1)) A(l(+(x0, x1))) -> A(+(x0, l(x1))) A(l(P(x0, x1, x2))) -> A(P(x0, x1, l(x2))) A(l(P(x0, x1, x2))) -> A(P(x0, l(x1), x2)) A(l(P(x0, x1, x2))) -> A(P(l(x0), x1, x2)) A(l(S(x0))) -> A(o(x0)) A(l(P(x0, x1, 0))) -> A(Q22(x0, a(x1), x1)) A(l(P(x0, x1, 0))) -> A(Q21(x0, a(x1), x0)) A(l(P(x0, 0, 0))) -> A(Q11(a(x0), x0)) A(l(P(x0, x1, S(x2)))) -> A(R2(x0, a(x1), x1, x2)) A(l(P(x0, 0, S(x1)))) -> A(R1(a(x0), x0, x1)) The TRS R consists of the following rules: a(x1) -> x1 o(x1) -> x1 l(x1) -> x1 S(x1) -> x1 +(x1, x2) -> x2 +(x1, x2) -> x1 P(x1, x2, x3) -> x3 P(x1, x2, x3) -> x2 P(x1, x2, x3) -> x1 M(x1, x2, x3) -> x3 M(x1, x2, x3) -> x2 M(x1, x2, x3) -> x1 J1(x1, x2) -> x2 J1(x1, x2) -> x1 J2(x1, x2, x3) -> x3 J2(x1, x2, x3) -> x2 J2(x1, x2, x3) -> x1 Q11(x1, x2) -> x2 Q11(x1, x2) -> x1 Q21(x1, x2, x3) -> x3 Q21(x1, x2, x3) -> x2 Q21(x1, x2, x3) -> x1 Q22(x1, x2, x3) -> x3 Q22(x1, x2, x3) -> x2 Q22(x1, x2, x3) -> x1 R1(x1, x2, x3) -> x3 R1(x1, x2, x3) -> x2 R1(x1, x2, x3) -> x1 R2(x1, x2, x3, x4) -> x4 R2(x1, x2, x3, x4) -> x3 R2(x1, x2, x3, x4) -> x2 R2(x1, x2, x3, x4) -> x1 P(0, 0, 0) -> S(0) +(x, S(y)) -> S(+(x, y)) a(l(x)) -> l(a(a(x))) l(o(x)) -> o(l(l(x))) o(x) -> l(x) l(x) -> a(x) a(S(x)) -> S(l(x)) a(+(x, y)) -> +(l(x), y) a(+(x, y)) -> +(x, l(y)) a(P(x1, x2, x3)) -> P(x1, x2, l(x3)) a(P(x1, x2, x3)) -> P(x1, l(x2), x3) a(P(x1, x2, x3)) -> P(l(x1), x2, x3) +(x, o(y)) -> o(+(x, y)) P(x1, x2, o(x3)) -> o(P(x1, x2, x3)) P(x1, o(x2), x3) -> o(P(x1, x2, x3)) P(o(x1), x2, x3) -> o(P(x1, x2, x3)) M(x1, x2, l(y)) -> +(M(x1, x2, y), P(x1, x2, y)) J2(x1, l(x2), y) -> P(x1, J2(x1, x2, y), 0) J1(l(x1), y) -> P(J1(x1, y), 0, 0) a(S(x)) -> o(x) P(0, 0, S(y)) -> o(M(0, 0, y)) P(0, 0, P(x1, x2, y)) -> o(M(x1, x2, y)) P(x1, S(x2), y) -> o(J2(x1, x2, y)) P(S(x1), 0, y) -> o(J1(x1, y)) P(x1, S(x2), S(y)) -> o(J2(x1, x2, P(x1, S(x2), y))) P(S(x1), 0, S(y)) -> o(J1(x1, P(S(x1), 0, y))) a(P(x1, x2, 0)) -> Q22(x1, a(x2), x2) a(P(x1, x2, 0)) -> Q21(x1, a(x2), x1) a(P(x1, 0, 0)) -> Q11(a(x1), x1) Q22(x1, o(x2), y) -> o(P(x1, x2, y)) Q21(x1, o(x2), y) -> o(P(x1, x2, y)) Q11(o(x1), y) -> o(P(x1, 0, y)) a(P(x1, x2, S(y))) -> R2(x1, a(x2), x2, y) a(P(x1, 0, S(y))) -> R1(a(x1), x1, y) R2(x1, o(x2), y, z) -> o(P(x1, x2, P(x1, y, z))) R1(o(x1), y, z) -> o(P(x1, 0, P(y, 0, z))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule A(+(x, y)) -> +^1(x, l(y)) at position [1] we obtained the following new rules [LPAR04]: (A(+(y0, x0)) -> +^1(y0, x0),A(+(y0, x0)) -> +^1(y0, x0)) (A(+(y0, o(x0))) -> +^1(y0, o(l(l(x0)))),A(+(y0, o(x0))) -> +^1(y0, o(l(l(x0))))) (A(+(y0, x0)) -> +^1(y0, a(x0)),A(+(y0, x0)) -> +^1(y0, a(x0))) ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: P^1(x1, x2, o(x3)) -> O(P(x1, x2, x3)) O(x) -> L(x) L(o(x)) -> O(l(l(x))) L(o(x)) -> L(l(x)) L(o(x)) -> L(x) L(x) -> A(x) A(l(x)) -> L(a(a(x))) A(l(x)) -> A(x) A(S(x)) -> L(x) A(+(x, y)) -> +^1(l(x), y) +^1(x, S(y)) -> +^1(x, y) +^1(x, o(y)) -> O(+(x, y)) +^1(x, o(y)) -> +^1(x, y) A(+(x, y)) -> L(x) A(+(x, y)) -> L(y) A(P(x1, x2, x3)) -> P^1(x1, x2, l(x3)) P^1(x1, x2, o(x3)) -> P^1(x1, x2, x3) P^1(x1, o(x2), x3) -> O(P(x1, x2, x3)) P^1(x1, o(x2), x3) -> P^1(x1, x2, x3) P^1(o(x1), x2, x3) -> O(P(x1, x2, x3)) P^1(o(x1), x2, x3) -> P^1(x1, x2, x3) P^1(0, 0, S(y)) -> O(M(0, 0, y)) P^1(0, 0, S(y)) -> M^1(0, 0, y) M^1(x1, x2, l(y)) -> +^1(M(x1, x2, y), P(x1, x2, y)) M^1(x1, x2, l(y)) -> M^1(x1, x2, y) M^1(x1, x2, l(y)) -> P^1(x1, x2, y) P^1(0, 0, P(x1, x2, y)) -> O(M(x1, x2, y)) P^1(0, 0, P(x1, x2, y)) -> M^1(x1, x2, y) P^1(x1, S(x2), y) -> O(J2(x1, x2, y)) P^1(x1, S(x2), y) -> J2^1(x1, x2, y) J2^1(x1, l(x2), y) -> P^1(x1, J2(x1, x2, y), 0) P^1(S(x1), 0, y) -> O(J1(x1, y)) P^1(S(x1), 0, y) -> J1^1(x1, y) J1^1(l(x1), y) -> P^1(J1(x1, y), 0, 0) J1^1(l(x1), y) -> J1^1(x1, y) J2^1(x1, l(x2), y) -> J2^1(x1, x2, y) P^1(x1, S(x2), S(y)) -> O(J2(x1, x2, P(x1, S(x2), y))) P^1(x1, S(x2), S(y)) -> J2^1(x1, x2, P(x1, S(x2), y)) P^1(x1, S(x2), S(y)) -> P^1(x1, S(x2), y) P^1(S(x1), 0, S(y)) -> O(J1(x1, P(S(x1), 0, y))) P^1(S(x1), 0, S(y)) -> J1^1(x1, P(S(x1), 0, y)) P^1(S(x1), 0, S(y)) -> P^1(S(x1), 0, y) A(P(x1, x2, x3)) -> L(x3) A(P(x1, x2, x3)) -> P^1(x1, l(x2), x3) A(P(x1, x2, x3)) -> L(x2) A(P(x1, x2, x3)) -> P^1(l(x1), x2, x3) A(P(x1, x2, x3)) -> L(x1) A(S(x)) -> O(x) A(P(x1, x2, 0)) -> Q22^1(x1, a(x2), x2) Q22^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q22^1(x1, o(x2), y) -> P^1(x1, x2, y) A(P(x1, x2, 0)) -> A(x2) A(P(x1, x2, 0)) -> Q21^1(x1, a(x2), x1) Q21^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q21^1(x1, o(x2), y) -> P^1(x1, x2, y) A(P(x1, 0, 0)) -> Q11^1(a(x1), x1) Q11^1(o(x1), y) -> O(P(x1, 0, y)) Q11^1(o(x1), y) -> P^1(x1, 0, y) A(P(x1, 0, 0)) -> A(x1) A(P(x1, x2, S(y))) -> R2^1(x1, a(x2), x2, y) R2^1(x1, o(x2), y, z) -> O(P(x1, x2, P(x1, y, z))) R2^1(x1, o(x2), y, z) -> P^1(x1, x2, P(x1, y, z)) R2^1(x1, o(x2), y, z) -> P^1(x1, y, z) A(P(x1, x2, S(y))) -> A(x2) A(P(x1, 0, S(y))) -> R1^1(a(x1), x1, y) R1^1(o(x1), y, z) -> O(P(x1, 0, P(y, 0, z))) R1^1(o(x1), y, z) -> P^1(x1, 0, P(y, 0, z)) R1^1(o(x1), y, z) -> P^1(y, 0, z) A(P(x1, 0, S(y))) -> A(x1) A(l(l(x0))) -> A(l(a(a(x0)))) A(l(S(x0))) -> A(S(l(x0))) A(l(+(x0, x1))) -> A(+(l(x0), x1)) A(l(+(x0, x1))) -> A(+(x0, l(x1))) A(l(P(x0, x1, x2))) -> A(P(x0, x1, l(x2))) A(l(P(x0, x1, x2))) -> A(P(x0, l(x1), x2)) A(l(P(x0, x1, x2))) -> A(P(l(x0), x1, x2)) A(l(S(x0))) -> A(o(x0)) A(l(P(x0, x1, 0))) -> A(Q22(x0, a(x1), x1)) A(l(P(x0, x1, 0))) -> A(Q21(x0, a(x1), x0)) A(l(P(x0, 0, 0))) -> A(Q11(a(x0), x0)) A(l(P(x0, x1, S(x2)))) -> A(R2(x0, a(x1), x1, x2)) A(l(P(x0, 0, S(x1)))) -> A(R1(a(x0), x0, x1)) A(+(y0, x0)) -> +^1(y0, x0) A(+(y0, o(x0))) -> +^1(y0, o(l(l(x0)))) A(+(y0, x0)) -> +^1(y0, a(x0)) The TRS R consists of the following rules: a(x1) -> x1 o(x1) -> x1 l(x1) -> x1 S(x1) -> x1 +(x1, x2) -> x2 +(x1, x2) -> x1 P(x1, x2, x3) -> x3 P(x1, x2, x3) -> x2 P(x1, x2, x3) -> x1 M(x1, x2, x3) -> x3 M(x1, x2, x3) -> x2 M(x1, x2, x3) -> x1 J1(x1, x2) -> x2 J1(x1, x2) -> x1 J2(x1, x2, x3) -> x3 J2(x1, x2, x3) -> x2 J2(x1, x2, x3) -> x1 Q11(x1, x2) -> x2 Q11(x1, x2) -> x1 Q21(x1, x2, x3) -> x3 Q21(x1, x2, x3) -> x2 Q21(x1, x2, x3) -> x1 Q22(x1, x2, x3) -> x3 Q22(x1, x2, x3) -> x2 Q22(x1, x2, x3) -> x1 R1(x1, x2, x3) -> x3 R1(x1, x2, x3) -> x2 R1(x1, x2, x3) -> x1 R2(x1, x2, x3, x4) -> x4 R2(x1, x2, x3, x4) -> x3 R2(x1, x2, x3, x4) -> x2 R2(x1, x2, x3, x4) -> x1 P(0, 0, 0) -> S(0) +(x, S(y)) -> S(+(x, y)) a(l(x)) -> l(a(a(x))) l(o(x)) -> o(l(l(x))) o(x) -> l(x) l(x) -> a(x) a(S(x)) -> S(l(x)) a(+(x, y)) -> +(l(x), y) a(+(x, y)) -> +(x, l(y)) a(P(x1, x2, x3)) -> P(x1, x2, l(x3)) a(P(x1, x2, x3)) -> P(x1, l(x2), x3) a(P(x1, x2, x3)) -> P(l(x1), x2, x3) +(x, o(y)) -> o(+(x, y)) P(x1, x2, o(x3)) -> o(P(x1, x2, x3)) P(x1, o(x2), x3) -> o(P(x1, x2, x3)) P(o(x1), x2, x3) -> o(P(x1, x2, x3)) M(x1, x2, l(y)) -> +(M(x1, x2, y), P(x1, x2, y)) J2(x1, l(x2), y) -> P(x1, J2(x1, x2, y), 0) J1(l(x1), y) -> P(J1(x1, y), 0, 0) a(S(x)) -> o(x) P(0, 0, S(y)) -> o(M(0, 0, y)) P(0, 0, P(x1, x2, y)) -> o(M(x1, x2, y)) P(x1, S(x2), y) -> o(J2(x1, x2, y)) P(S(x1), 0, y) -> o(J1(x1, y)) P(x1, S(x2), S(y)) -> o(J2(x1, x2, P(x1, S(x2), y))) P(S(x1), 0, S(y)) -> o(J1(x1, P(S(x1), 0, y))) a(P(x1, x2, 0)) -> Q22(x1, a(x2), x2) a(P(x1, x2, 0)) -> Q21(x1, a(x2), x1) a(P(x1, 0, 0)) -> Q11(a(x1), x1) Q22(x1, o(x2), y) -> o(P(x1, x2, y)) Q21(x1, o(x2), y) -> o(P(x1, x2, y)) Q11(o(x1), y) -> o(P(x1, 0, y)) a(P(x1, x2, S(y))) -> R2(x1, a(x2), x2, y) a(P(x1, 0, S(y))) -> R1(a(x1), x1, y) R2(x1, o(x2), y, z) -> o(P(x1, x2, P(x1, y, z))) R1(o(x1), y, z) -> o(P(x1, 0, P(y, 0, z))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule J1^1(l(x1), y) -> P^1(J1(x1, y), 0, 0) at position [0] we obtained the following new rules [LPAR04]: (J1^1(l(x0), x1) -> P^1(x1, 0, 0),J1^1(l(x0), x1) -> P^1(x1, 0, 0)) (J1^1(l(x0), x1) -> P^1(x0, 0, 0),J1^1(l(x0), x1) -> P^1(x0, 0, 0)) (J1^1(l(l(x0)), x1) -> P^1(P(J1(x0, x1), 0, 0), 0, 0),J1^1(l(l(x0)), x1) -> P^1(P(J1(x0, x1), 0, 0), 0, 0)) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: P^1(x1, x2, o(x3)) -> O(P(x1, x2, x3)) O(x) -> L(x) L(o(x)) -> O(l(l(x))) L(o(x)) -> L(l(x)) L(o(x)) -> L(x) L(x) -> A(x) A(l(x)) -> L(a(a(x))) A(l(x)) -> A(x) A(S(x)) -> L(x) A(+(x, y)) -> +^1(l(x), y) +^1(x, S(y)) -> +^1(x, y) +^1(x, o(y)) -> O(+(x, y)) +^1(x, o(y)) -> +^1(x, y) A(+(x, y)) -> L(x) A(+(x, y)) -> L(y) A(P(x1, x2, x3)) -> P^1(x1, x2, l(x3)) P^1(x1, x2, o(x3)) -> P^1(x1, x2, x3) P^1(x1, o(x2), x3) -> O(P(x1, x2, x3)) P^1(x1, o(x2), x3) -> P^1(x1, x2, x3) P^1(o(x1), x2, x3) -> O(P(x1, x2, x3)) P^1(o(x1), x2, x3) -> P^1(x1, x2, x3) P^1(0, 0, S(y)) -> O(M(0, 0, y)) P^1(0, 0, S(y)) -> M^1(0, 0, y) M^1(x1, x2, l(y)) -> +^1(M(x1, x2, y), P(x1, x2, y)) M^1(x1, x2, l(y)) -> M^1(x1, x2, y) M^1(x1, x2, l(y)) -> P^1(x1, x2, y) P^1(0, 0, P(x1, x2, y)) -> O(M(x1, x2, y)) P^1(0, 0, P(x1, x2, y)) -> M^1(x1, x2, y) P^1(x1, S(x2), y) -> O(J2(x1, x2, y)) P^1(x1, S(x2), y) -> J2^1(x1, x2, y) J2^1(x1, l(x2), y) -> P^1(x1, J2(x1, x2, y), 0) P^1(S(x1), 0, y) -> O(J1(x1, y)) P^1(S(x1), 0, y) -> J1^1(x1, y) J1^1(l(x1), y) -> J1^1(x1, y) J2^1(x1, l(x2), y) -> J2^1(x1, x2, y) P^1(x1, S(x2), S(y)) -> O(J2(x1, x2, P(x1, S(x2), y))) P^1(x1, S(x2), S(y)) -> J2^1(x1, x2, P(x1, S(x2), y)) P^1(x1, S(x2), S(y)) -> P^1(x1, S(x2), y) P^1(S(x1), 0, S(y)) -> O(J1(x1, P(S(x1), 0, y))) P^1(S(x1), 0, S(y)) -> J1^1(x1, P(S(x1), 0, y)) P^1(S(x1), 0, S(y)) -> P^1(S(x1), 0, y) A(P(x1, x2, x3)) -> L(x3) A(P(x1, x2, x3)) -> P^1(x1, l(x2), x3) A(P(x1, x2, x3)) -> L(x2) A(P(x1, x2, x3)) -> P^1(l(x1), x2, x3) A(P(x1, x2, x3)) -> L(x1) A(S(x)) -> O(x) A(P(x1, x2, 0)) -> Q22^1(x1, a(x2), x2) Q22^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q22^1(x1, o(x2), y) -> P^1(x1, x2, y) A(P(x1, x2, 0)) -> A(x2) A(P(x1, x2, 0)) -> Q21^1(x1, a(x2), x1) Q21^1(x1, o(x2), y) -> O(P(x1, x2, y)) Q21^1(x1, o(x2), y) -> P^1(x1, x2, y) A(P(x1, 0, 0)) -> Q11^1(a(x1), x1) Q11^1(o(x1), y) -> O(P(x1, 0, y)) Q11^1(o(x1), y) -> P^1(x1, 0, y) A(P(x1, 0, 0)) -> A(x1) A(P(x1, x2, S(y))) -> R2^1(x1, a(x2), x2, y) R2^1(x1, o(x2), y, z) -> O(P(x1, x2, P(x1, y, z))) R2^1(x1, o(x2), y, z) -> P^1(x1, x2, P(x1, y, z)) R2^1(x1, o(x2), y, z) -> P^1(x1, y, z) A(P(x1, x2, S(y))) -> A(x2) A(P(x1, 0, S(y))) -> R1^1(a(x1), x1, y) R1^1(o(x1), y, z) -> O(P(x1, 0, P(y, 0, z))) R1^1(o(x1), y, z) -> P^1(x1, 0, P(y, 0, z)) R1^1(o(x1), y, z) -> P^1(y, 0, z) A(P(x1, 0, S(y))) -> A(x1) A(l(l(x0))) -> A(l(a(a(x0)))) A(l(S(x0))) -> A(S(l(x0))) A(l(+(x0, x1))) -> A(+(l(x0), x1)) A(l(+(x0, x1))) -> A(+(x0, l(x1))) A(l(P(x0, x1, x2))) -> A(P(x0, x1, l(x2))) A(l(P(x0, x1, x2))) -> A(P(x0, l(x1), x2)) A(l(P(x0, x1, x2))) -> A(P(l(x0), x1, x2)) A(l(S(x0))) -> A(o(x0)) A(l(P(x0, x1, 0))) -> A(Q22(x0, a(x1), x1)) A(l(P(x0, x1, 0))) -> A(Q21(x0, a(x1), x0)) A(l(P(x0, 0, 0))) -> A(Q11(a(x0), x0)) A(l(P(x0, x1, S(x2)))) -> A(R2(x0, a(x1), x1, x2)) A(l(P(x0, 0, S(x1)))) -> A(R1(a(x0), x0, x1)) A(+(y0, x0)) -> +^1(y0, x0) A(+(y0, o(x0))) -> +^1(y0, o(l(l(x0)))) A(+(y0, x0)) -> +^1(y0, a(x0)) J1^1(l(x0), x1) -> P^1(x1, 0, 0) J1^1(l(x0), x1) -> P^1(x0, 0, 0) J1^1(l(l(x0)), x1) -> P^1(P(J1(x0, x1), 0, 0), 0, 0) The TRS R consists of the following rules: a(x1) -> x1 o(x1) -> x1 l(x1) -> x1 S(x1) -> x1 +(x1, x2) -> x2 +(x1, x2) -> x1 P(x1, x2, x3) -> x3 P(x1, x2, x3) -> x2 P(x1, x2, x3) -> x1 M(x1, x2, x3) -> x3 M(x1, x2, x3) -> x2 M(x1, x2, x3) -> x1 J1(x1, x2) -> x2 J1(x1, x2) -> x1 J2(x1, x2, x3) -> x3 J2(x1, x2, x3) -> x2 J2(x1, x2, x3) -> x1 Q11(x1, x2) -> x2 Q11(x1, x2) -> x1 Q21(x1, x2, x3) -> x3 Q21(x1, x2, x3) -> x2 Q21(x1, x2, x3) -> x1 Q22(x1, x2, x3) -> x3 Q22(x1, x2, x3) -> x2 Q22(x1, x2, x3) -> x1 R1(x1, x2, x3) -> x3 R1(x1, x2, x3) -> x2 R1(x1, x2, x3) -> x1 R2(x1, x2, x3, x4) -> x4 R2(x1, x2, x3, x4) -> x3 R2(x1, x2, x3, x4) -> x2 R2(x1, x2, x3, x4) -> x1 P(0, 0, 0) -> S(0) +(x, S(y)) -> S(+(x, y)) a(l(x)) -> l(a(a(x))) l(o(x)) -> o(l(l(x))) o(x) -> l(x) l(x) -> a(x) a(S(x)) -> S(l(x)) a(+(x, y)) -> +(l(x), y) a(+(x, y)) -> +(x, l(y)) a(P(x1, x2, x3)) -> P(x1, x2, l(x3)) a(P(x1, x2, x3)) -> P(x1, l(x2), x3) a(P(x1, x2, x3)) -> P(l(x1), x2, x3) +(x, o(y)) -> o(+(x, y)) P(x1, x2, o(x3)) -> o(P(x1, x2, x3)) P(x1, o(x2), x3) -> o(P(x1, x2, x3)) P(o(x1), x2, x3) -> o(P(x1, x2, x3)) M(x1, x2, l(y)) -> +(M(x1, x2, y), P(x1, x2, y)) J2(x1, l(x2), y) -> P(x1, J2(x1, x2, y), 0) J1(l(x1), y) -> P(J1(x1, y), 0, 0) a(S(x)) -> o(x) P(0, 0, S(y)) -> o(M(0, 0, y)) P(0, 0, P(x1, x2, y)) -> o(M(x1, x2, y)) P(x1, S(x2), y) -> o(J2(x1, x2, y)) P(S(x1), 0, y) -> o(J1(x1, y)) P(x1, S(x2), S(y)) -> o(J2(x1, x2, P(x1, S(x2), y))) P(S(x1), 0, S(y)) -> o(J1(x1, P(S(x1), 0, y))) a(P(x1, x2, 0)) -> Q22(x1, a(x2), x2) a(P(x1, x2, 0)) -> Q21(x1, a(x2), x1) a(P(x1, 0, 0)) -> Q11(a(x1), x1) Q22(x1, o(x2), y) -> o(P(x1, x2, y)) Q21(x1, o(x2), y) -> o(P(x1, x2, y)) Q11(o(x1), y) -> o(P(x1, 0, y)) a(P(x1, x2, S(y))) -> R2(x1, a(x2), x2, y) a(P(x1, 0, S(y))) -> R1(a(x1), x1, y) R2(x1, o(x2), y, z) -> o(P(x1, x2, P(x1, y, z))) R1(o(x1), y, z) -> o(P(x1, 0, P(y, 0, z))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = J2^1(S(x2), l(x2''), y') evaluates to t =J2^1(S(x2), x2, 0) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [x2 / l(x2''), y' / 0] -------------------------------------------------------------------------------- Rewriting sequence J2^1(S(l(x2'')), l(x2''), 0) -> P^1(S(l(x2'')), J2(S(l(x2'')), x2'', 0), 0) with rule J2^1(x1', l(x2'''), y') -> P^1(x1', J2(x1', x2''', y'), 0) at position [] and matcher [x1' / S(l(x2'')), x2''' / x2'', y' / 0] P^1(S(l(x2'')), J2(S(l(x2'')), x2'', 0), 0) -> P^1(S(l(x2'')), S(l(x2'')), 0) with rule J2(x1', x2', x3) -> x1' at position [1] and matcher [x1' / S(l(x2'')), x2' / x2'', x3 / 0] P^1(S(l(x2'')), S(l(x2'')), 0) -> J2^1(S(l(x2'')), l(x2''), 0) with rule P^1(x1, S(x2), y) -> J2^1(x1, x2, y) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (12) NO