/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. !plus : [o * o] --> o 0 : [] --> o J1 : [o * o] --> o J2 : [o * o * o] --> o J3 : [o * o * o * o] --> o J4 : [o * o * o * o * o] --> o J5 : [o * o * o * o * o * o] --> o J6 : [o * o * o * o * o * o * o] --> o M : [o * o * o * o * o * o * o] --> o P : [o * o * o * o * o * o * o] --> o Q11 : [o * o] --> o Q21 : [o * o * o] --> o Q22 : [o * o * o] --> o Q31 : [o * o * o * o] --> o Q32 : [o * o * o * o] --> o Q33 : [o * o * o * o] --> o Q41 : [o * o * o * o * o] --> o Q42 : [o * o * o * o * o] --> o Q43 : [o * o * o * o * o] --> o Q44 : [o * o * o * o * o] --> o Q51 : [o * o * o * o * o * o] --> o Q52 : [o * o * o * o * o * o] --> o Q53 : [o * o * o * o * o * o] --> o Q54 : [o * o * o * o * o * o] --> o Q55 : [o * o * o * o * o * o] --> o Q61 : [o * o * o * o * o * o * o] --> o Q62 : [o * o * o * o * o * o * o] --> o Q63 : [o * o * o * o * o * o * o] --> o Q64 : [o * o * o * o * o * o * o] --> o Q65 : [o * o * o * o * o * o * o] --> o Q66 : [o * o * o * o * o * o * o] --> o R1 : [o * o * o] --> o R2 : [o * o * o * o] --> o R3 : [o * o * o * o * o] --> o R4 : [o * o * o * o * o * o] --> o R5 : [o * o * o * o * o * o * o] --> o R6 : [o * o * o * o * o * o * o * o] --> o S : [o] --> o a : [o] --> o l : [o] --> o o : [o] --> o a(X) => X o(X) => X l(X) => X S(X) => X !plus(X, Y) => Y !plus(X, Y) => X P(X, Y, Z, U, V, W, Q) => Q P(X, Y, Z, U, V, W, Q) => W P(X, Y, Z, U, V, W, Q) => V P(X, Y, Z, U, V, W, Q) => U P(X, Y, Z, U, V, W, Q) => Z P(X, Y, Z, U, V, W, Q) => Y P(X, Y, Z, U, V, W, Q) => X M(X, Y, Z, U, V, W, Q) => Q M(X, Y, Z, U, V, W, Q) => W M(X, Y, Z, U, V, W, Q) => V M(X, Y, Z, U, V, W, Q) => U M(X, Y, Z, U, V, W, Q) => Z M(X, Y, Z, U, V, W, Q) => Y M(X, Y, Z, U, V, W, Q) => X J1(X, Y) => Y J1(X, Y) => X J2(X, Y, Z) => Z J2(X, Y, Z) => Y J2(X, Y, Z) => X J3(X, Y, Z, U) => U J3(X, Y, Z, U) => Z J3(X, Y, Z, U) => Y J3(X, Y, Z, U) => X J4(X, Y, Z, U, V) => V J4(X, Y, Z, U, V) => U J4(X, Y, Z, U, V) => Z J4(X, Y, Z, U, V) => Y J4(X, Y, Z, U, V) => X J5(X, Y, Z, U, V, W) => W J5(X, Y, Z, U, V, W) => V J5(X, Y, Z, U, V, W) => U J5(X, Y, Z, U, V, W) => Z J5(X, Y, Z, U, V, W) => Y J5(X, Y, Z, U, V, W) => X J6(X, Y, Z, U, V, W, Q) => Q J6(X, Y, Z, U, V, W, Q) => W J6(X, Y, Z, U, V, W, Q) => V J6(X, Y, Z, U, V, W, Q) => U J6(X, Y, Z, U, V, W, Q) => Z J6(X, Y, Z, U, V, W, Q) => Y J6(X, Y, Z, U, V, W, Q) => X Q11(X, Y) => Y Q11(X, Y) => X Q21(X, Y, Z) => Z Q21(X, Y, Z) => Y Q21(X, Y, Z) => X Q22(X, Y, Z) => Z Q22(X, Y, Z) => Y Q22(X, Y, Z) => X Q31(X, Y, Z, U) => U Q31(X, Y, Z, U) => Z Q31(X, Y, Z, U) => Y Q31(X, Y, Z, U) => X Q32(X, Y, Z, U) => U Q32(X, Y, Z, U) => Z Q32(X, Y, Z, U) => Y Q32(X, Y, Z, U) => X Q33(X, Y, Z, U) => U Q33(X, Y, Z, U) => Z Q33(X, Y, Z, U) => Y Q33(X, Y, Z, U) => X Q41(X, Y, Z, U, V) => V Q41(X, Y, Z, U, V) => U Q41(X, Y, Z, U, V) => Z Q41(X, Y, Z, U, V) => Y Q41(X, Y, Z, U, V) => X Q42(X, Y, Z, U, V) => V Q42(X, Y, Z, U, V) => U Q42(X, Y, Z, U, V) => Z Q42(X, Y, Z, U, V) => Y Q42(X, Y, Z, U, V) => X Q43(X, Y, Z, U, V) => V Q43(X, Y, Z, U, V) => U Q43(X, Y, Z, U, V) => Z Q43(X, Y, Z, U, V) => Y Q43(X, Y, Z, U, V) => X Q44(X, Y, Z, U, V) => V Q44(X, Y, Z, U, V) => U Q44(X, Y, Z, U, V) => Z Q44(X, Y, Z, U, V) => Y Q44(X, Y, Z, U, V) => X Q51(X, Y, Z, U, V, W) => W Q51(X, Y, Z, U, V, W) => V Q51(X, Y, Z, U, V, W) => U Q51(X, Y, Z, U, V, W) => Z Q51(X, Y, Z, U, V, W) => Y Q51(X, Y, Z, U, V, W) => X Q52(X, Y, Z, U, V, W) => W Q52(X, Y, Z, U, V, W) => V Q52(X, Y, Z, U, V, W) => U Q52(X, Y, Z, U, V, W) => Z Q52(X, Y, Z, U, V, W) => Y Q52(X, Y, Z, U, V, W) => X Q53(X, Y, Z, U, V, W) => W Q53(X, Y, Z, U, V, W) => V Q53(X, Y, Z, U, V, W) => U Q53(X, Y, Z, U, V, W) => Z Q53(X, Y, Z, U, V, W) => Y Q53(X, Y, Z, U, V, W) => X Q54(X, Y, Z, U, V, W) => W Q54(X, Y, Z, U, V, W) => V Q54(X, Y, Z, U, V, W) => U Q54(X, Y, Z, U, V, W) => Z Q54(X, Y, Z, U, V, W) => Y Q54(X, Y, Z, U, V, W) => X Q55(X, Y, Z, U, V, W) => W Q55(X, Y, Z, U, V, W) => V Q55(X, Y, Z, U, V, W) => U Q55(X, Y, Z, U, V, W) => Z Q55(X, Y, Z, U, V, W) => Y Q55(X, Y, Z, U, V, W) => X Q61(X, Y, Z, U, V, W, Q) => Q Q61(X, Y, Z, U, V, W, Q) => W Q61(X, Y, Z, U, V, W, Q) => V Q61(X, Y, Z, U, V, W, Q) => U Q61(X, Y, Z, U, V, W, Q) => Z Q61(X, Y, Z, U, V, W, Q) => Y Q61(X, Y, Z, U, V, W, Q) => X Q62(X, Y, Z, U, V, W, Q) => Q Q62(X, Y, Z, U, V, W, Q) => W Q62(X, Y, Z, U, V, W, Q) => V Q62(X, Y, Z, U, V, W, Q) => U Q62(X, Y, Z, U, V, W, Q) => Z Q62(X, Y, Z, U, V, W, Q) => Y Q62(X, Y, Z, U, V, W, Q) => X Q63(X, Y, Z, U, V, W, Q) => Q Q63(X, Y, Z, U, V, W, Q) => W Q63(X, Y, Z, U, V, W, Q) => V Q63(X, Y, Z, U, V, W, Q) => U Q63(X, Y, Z, U, V, W, Q) => Z Q63(X, Y, Z, U, V, W, Q) => Y Q63(X, Y, Z, U, V, W, Q) => X Q64(X, Y, Z, U, V, W, Q) => Q Q64(X, Y, Z, U, V, W, Q) => W Q64(X, Y, Z, U, V, W, Q) => V Q64(X, Y, Z, U, V, W, Q) => U Q64(X, Y, Z, U, V, W, Q) => Z Q64(X, Y, Z, U, V, W, Q) => Y Q64(X, Y, Z, U, V, W, Q) => X Q65(X, Y, Z, U, V, W, Q) => Q Q65(X, Y, Z, U, V, W, Q) => W Q65(X, Y, Z, U, V, W, Q) => V Q65(X, Y, Z, U, V, W, Q) => U Q65(X, Y, Z, U, V, W, Q) => Z Q65(X, Y, Z, U, V, W, Q) => Y Q65(X, Y, Z, U, V, W, Q) => X Q66(X, Y, Z, U, V, W, Q) => Q Q66(X, Y, Z, U, V, W, Q) => W Q66(X, Y, Z, U, V, W, Q) => V Q66(X, Y, Z, U, V, W, Q) => U Q66(X, Y, Z, U, V, W, Q) => Z Q66(X, Y, Z, U, V, W, Q) => Y Q66(X, Y, Z, U, V, W, Q) => X R1(X, Y, Z) => Z R1(X, Y, Z) => Y R1(X, Y, Z) => X R2(X, Y, Z, U) => U R2(X, Y, Z, U) => Z R2(X, Y, Z, U) => Y R2(X, Y, Z, U) => X R3(X, Y, Z, U, V) => V R3(X, Y, Z, U, V) => U R3(X, Y, Z, U, V) => Z R3(X, Y, Z, U, V) => Y R3(X, Y, Z, U, V) => X R4(X, Y, Z, U, V, W) => W R4(X, Y, Z, U, V, W) => V R4(X, Y, Z, U, V, W) => U R4(X, Y, Z, U, V, W) => Z R4(X, Y, Z, U, V, W) => Y R4(X, Y, Z, U, V, W) => X R5(X, Y, Z, U, V, W, Q) => Q R5(X, Y, Z, U, V, W, Q) => W R5(X, Y, Z, U, V, W, Q) => V R5(X, Y, Z, U, V, W, Q) => U R5(X, Y, Z, U, V, W, Q) => Z R5(X, Y, Z, U, V, W, Q) => Y R5(X, Y, Z, U, V, W, Q) => X R6(X, Y, Z, U, V, W, Q, R) => R R6(X, Y, Z, U, V, W, Q, R) => Q R6(X, Y, Z, U, V, W, Q, R) => W R6(X, Y, Z, U, V, W, Q, R) => V R6(X, Y, Z, U, V, W, Q, R) => U R6(X, Y, Z, U, V, W, Q, R) => Z R6(X, Y, Z, U, V, W, Q, R) => Y R6(X, Y, Z, U, V, W, Q, R) => X P(0, 0, 0, 0, 0, 0, 0) => S(0) !plus(X, S(Y)) => S(!plus(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(!plus(X, Y)) => !plus(l(X), Y) a(!plus(X, Y)) => !plus(X, l(Y)) a(P(X, Y, Z, U, V, W, Q)) => P(X, Y, Z, U, V, W, l(Q)) a(P(X, Y, Z, U, V, W, Q)) => P(X, Y, Z, U, V, l(W), Q) a(P(X, Y, Z, U, V, W, Q)) => P(X, Y, Z, U, l(V), W, Q) a(P(X, Y, Z, U, V, W, Q)) => P(X, Y, Z, l(U), V, W, Q) a(P(X, Y, Z, U, V, W, Q)) => P(X, Y, l(Z), U, V, W, Q) a(P(X, Y, Z, U, V, W, Q)) => P(X, l(Y), Z, U, V, W, Q) a(P(X, Y, Z, U, V, W, Q)) => P(l(X), Y, Z, U, V, W, Q) !plus(X, o(Y)) => o(!plus(X, Y)) P(X, Y, Z, U, V, W, o(Q)) => o(P(X, Y, Z, U, V, W, Q)) P(X, Y, Z, U, V, o(W), Q) => o(P(X, Y, Z, U, V, W, Q)) P(X, Y, Z, U, o(V), W, Q) => o(P(X, Y, Z, U, V, W, Q)) P(X, Y, Z, o(U), V, W, Q) => o(P(X, Y, Z, U, V, W, Q)) P(X, Y, o(Z), U, V, W, Q) => o(P(X, Y, Z, U, V, W, Q)) P(X, o(Y), Z, U, V, W, Q) => o(P(X, Y, Z, U, V, W, Q)) P(o(X), Y, Z, U, V, W, Q) => o(P(X, Y, Z, U, V, W, Q)) M(X, Y, Z, U, V, W, l(Q)) => !plus(M(X, Y, Z, U, V, W, Q), P(X, Y, Z, U, V, W, Q)) J6(X, Y, Z, U, V, l(W), Q) => P(X, Y, Z, U, V, J6(X, Y, Z, U, V, W, Q), 0) J5(X, Y, Z, U, l(V), W) => P(X, Y, Z, U, J5(X, Y, Z, U, V, W), 0, 0) J4(X, Y, Z, l(U), V) => P(X, Y, Z, J4(X, Y, Z, U, V), 0, 0, 0) J3(X, Y, l(Z), U) => P(X, Y, J3(X, Y, Z, U), 0, 0, 0, 0) J2(X, l(Y), Z) => P(X, J2(X, Y, Z), 0, 0, 0, 0, 0) J1(l(X), Y) => P(J1(X, Y), 0, 0, 0, 0, 0, 0) a(S(X)) => o(X) P(0, 0, 0, 0, 0, 0, S(X)) => o(M(0, 0, 0, 0, 0, 0, X)) P(0, 0, 0, 0, 0, 0, P(X, Y, Z, U, V, W, Q)) => o(M(X, Y, Z, U, V, W, Q)) P(X, Y, Z, U, V, S(W), Q) => o(J6(X, Y, Z, U, V, W, Q)) P(X, Y, Z, U, S(V), 0, W) => o(J5(X, Y, Z, U, V, W)) P(X, Y, Z, S(U), 0, 0, V) => o(J4(X, Y, Z, U, V)) P(X, Y, S(Z), 0, 0, 0, U) => o(J3(X, Y, Z, U)) P(X, S(Y), 0, 0, 0, 0, Z) => o(J2(X, Y, Z)) P(S(X), 0, 0, 0, 0, 0, Y) => o(J1(X, Y)) P(X, Y, Z, U, V, S(W), S(Q)) => o(J6(X, Y, Z, U, V, W, P(X, Y, Z, U, V, S(W), Q))) P(X, Y, Z, U, S(V), 0, S(W)) => o(J5(X, Y, Z, U, V, P(X, Y, Z, U, S(V), 0, W))) P(X, Y, Z, S(U), 0, 0, S(V)) => o(J4(X, Y, Z, U, P(X, Y, Z, S(U), 0, 0, V))) P(X, Y, S(Z), 0, 0, 0, S(U)) => o(J3(X, Y, Z, P(X, Y, S(Z), 0, 0, 0, U))) P(X, S(Y), 0, 0, 0, 0, S(Z)) => o(J2(X, Y, P(X, S(Y), 0, 0, 0, 0, Z))) P(S(X), 0, 0, 0, 0, 0, S(Y)) => o(J1(X, P(S(X), 0, 0, 0, 0, 0, Y))) a(P(X, Y, Z, U, V, W, 0)) => Q66(X, Y, Z, U, V, a(W), W) a(P(X, Y, Z, U, V, W, 0)) => Q65(X, Y, Z, U, V, a(W), V) a(P(X, Y, Z, U, V, W, 0)) => Q64(X, Y, Z, U, V, a(W), U) a(P(X, Y, Z, U, V, W, 0)) => Q63(X, Y, Z, U, V, a(W), Z) a(P(X, Y, Z, U, V, W, 0)) => Q62(X, Y, Z, U, V, a(W), Y) a(P(X, Y, Z, U, V, W, 0)) => Q61(X, Y, Z, U, V, a(W), X) a(P(X, Y, Z, U, V, 0, 0)) => Q55(X, Y, Z, U, a(V), V) a(P(X, Y, Z, U, V, 0, 0)) => Q54(X, Y, Z, U, a(V), U) a(P(X, Y, Z, U, V, 0, 0)) => Q53(X, Y, Z, U, a(V), Z) a(P(X, Y, Z, U, V, 0, 0)) => Q52(X, Y, Z, U, a(V), Y) a(P(X, Y, Z, U, V, 0, 0)) => Q51(X, Y, Z, U, a(V), X) a(P(X, Y, Z, U, 0, 0, 0)) => Q44(X, Y, Z, a(U), U) a(P(X, Y, Z, U, 0, 0, 0)) => Q43(X, Y, Z, a(U), Z) a(P(X, Y, Z, U, 0, 0, 0)) => Q42(X, Y, Z, a(U), Y) a(P(X, Y, Z, U, 0, 0, 0)) => Q41(X, Y, Z, a(U), X) a(P(X, Y, Z, 0, 0, 0, 0)) => Q33(X, Y, a(Z), Z) a(P(X, Y, Z, 0, 0, 0, 0)) => Q32(X, Y, a(Z), Y) a(P(X, Y, Z, 0, 0, 0, 0)) => Q31(X, Y, a(Z), X) a(P(X, Y, 0, 0, 0, 0, 0)) => Q22(X, a(Y), Y) a(P(X, Y, 0, 0, 0, 0, 0)) => Q21(X, a(Y), X) a(P(X, 0, 0, 0, 0, 0, 0)) => Q11(a(X), X) Q66(X, Y, Z, U, V, o(W), Q) => o(P(X, Y, Z, U, V, W, Q)) Q65(X, Y, Z, U, V, o(W), Q) => o(P(X, Y, Z, U, V, W, Q)) Q64(X, Y, Z, U, V, o(W), Q) => o(P(X, Y, Z, U, V, W, Q)) Q63(X, Y, Z, U, V, o(W), Q) => o(P(X, Y, Z, U, V, W, Q)) Q62(X, Y, Z, U, V, o(W), Q) => o(P(X, Y, Z, U, V, W, Q)) Q61(X, Y, Z, U, V, o(W), Q) => o(P(X, Y, Z, U, V, W, Q)) Q55(X, Y, Z, U, o(V), W) => o(P(X, Y, Z, U, V, 0, W)) Q54(X, Y, Z, U, o(V), W) => o(P(X, Y, Z, U, V, 0, W)) Q53(X, Y, Z, U, o(V), W) => o(P(X, Y, Z, U, V, 0, W)) Q52(X, Y, Z, U, o(V), W) => o(P(X, Y, Z, U, V, 0, W)) Q51(X, Y, Z, U, o(V), W) => o(P(X, Y, Z, U, V, 0, W)) Q44(X, Y, Z, o(U), V) => o(P(X, Y, Z, U, 0, 0, V)) Q43(X, Y, Z, o(U), V) => o(P(X, Y, Z, U, 0, 0, V)) Q42(X, Y, Z, o(U), V) => o(P(X, Y, Z, U, 0, 0, V)) Q41(X, Y, Z, o(U), V) => o(P(X, Y, Z, U, 0, 0, V)) Q33(X, Y, o(Z), U) => o(P(X, Y, Z, 0, 0, 0, U)) Q32(X, Y, o(Z), U) => o(P(X, Y, Z, 0, 0, 0, U)) Q31(X, Y, o(Z), U) => o(P(X, Y, Z, 0, 0, 0, U)) Q22(X, o(Y), Z) => o(P(X, Y, 0, 0, 0, 0, Z)) Q21(X, o(Y), Z) => o(P(X, Y, 0, 0, 0, 0, Z)) Q11(o(X), Y) => o(P(X, 0, 0, 0, 0, 0, Y)) a(P(X, Y, Z, U, V, W, S(Q))) => R6(X, Y, Z, U, V, a(W), W, Q) a(P(X, Y, Z, U, V, 0, S(W))) => R5(X, Y, Z, U, a(V), V, W) a(P(X, Y, Z, U, 0, 0, S(V))) => R4(X, Y, Z, a(U), U, V) a(P(X, Y, Z, 0, 0, 0, S(U))) => R3(X, Y, a(Z), Z, U) a(P(X, Y, 0, 0, 0, 0, S(Z))) => R2(X, a(Y), Y, Z) a(P(X, 0, 0, 0, 0, 0, S(Y))) => R1(a(X), X, Y) R6(X, Y, Z, U, V, o(W), Q, R) => o(P(X, Y, Z, U, V, W, P(X, Y, Z, U, V, Q, R))) R5(X, Y, Z, U, o(V), W, Q) => o(P(X, Y, Z, U, V, 0, P(X, Y, Z, U, W, 0, Q))) R4(X, Y, Z, o(U), V, W) => o(P(X, Y, Z, U, 0, 0, P(X, Y, Z, V, 0, 0, W))) R3(X, Y, o(Z), U, V) => o(P(X, Y, Z, 0, 0, 0, P(X, Y, U, 0, 0, 0, V))) R2(X, o(Y), Z, U) => o(P(X, Y, 0, 0, 0, 0, P(X, Z, 0, 0, 0, 0, U))) R1(o(X), Y, Z) => o(P(X, 0, 0, 0, 0, 0, P(Y, 0, 0, 0, 0, 0, Z)))