7.31/2.87 YES 7.31/2.88 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 7.31/2.88 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.31/2.88 7.31/2.88 7.31/2.88 Termination w.r.t. Q of the given QTRS could be proven: 7.31/2.88 7.31/2.88 (0) QTRS 7.31/2.88 (1) QTRSRRRProof [EQUIVALENT, 338 ms] 7.31/2.88 (2) QTRS 7.31/2.88 (3) QTRSRRRProof [EQUIVALENT, 53 ms] 7.31/2.88 (4) QTRS 7.31/2.88 (5) QTRSRRRProof [EQUIVALENT, 36 ms] 7.31/2.88 (6) QTRS 7.31/2.88 (7) QTRSRRRProof [EQUIVALENT, 34 ms] 7.31/2.88 (8) QTRS 7.31/2.88 (9) QTRSRRRProof [EQUIVALENT, 43 ms] 7.31/2.88 (10) QTRS 7.31/2.88 (11) QTRSRRRProof [EQUIVALENT, 0 ms] 7.31/2.88 (12) QTRS 7.31/2.88 (13) QTRSRRRProof [EQUIVALENT, 0 ms] 7.31/2.88 (14) QTRS 7.31/2.88 (15) RisEmptyProof [EQUIVALENT, 0 ms] 7.31/2.88 (16) YES 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (0) 7.31/2.88 Obligation: 7.31/2.88 Q restricted rewrite system: 7.31/2.88 The TRS R consists of the following rules: 7.31/2.88 7.31/2.88 active(U11(tt, M, N)) -> mark(U12(tt, M, N)) 7.31/2.88 active(U12(tt, M, N)) -> mark(s(plus(N, M))) 7.31/2.88 active(U21(tt, M, N)) -> mark(U22(tt, M, N)) 7.31/2.88 active(U22(tt, M, N)) -> mark(plus(x(N, M), N)) 7.31/2.88 active(plus(N, 0)) -> mark(N) 7.31/2.88 active(plus(N, s(M))) -> mark(U11(tt, M, N)) 7.31/2.88 active(x(N, 0)) -> mark(0) 7.31/2.88 active(x(N, s(M))) -> mark(U21(tt, M, N)) 7.31/2.88 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 7.31/2.88 mark(tt) -> active(tt) 7.31/2.88 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 7.31/2.88 mark(s(X)) -> active(s(mark(X))) 7.31/2.88 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 7.31/2.88 mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3)) 7.31/2.88 mark(U22(X1, X2, X3)) -> active(U22(mark(X1), X2, X3)) 7.31/2.88 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 7.31/2.88 mark(0) -> active(0) 7.31/2.88 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 7.31/2.88 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 7.31/2.88 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 7.31/2.88 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 7.31/2.88 s(mark(X)) -> s(X) 7.31/2.88 s(active(X)) -> s(X) 7.31/2.88 plus(mark(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, mark(X2)) -> plus(X1, X2) 7.31/2.88 plus(active(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, active(X2)) -> plus(X1, X2) 7.31/2.88 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 7.31/2.88 U21(active(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, active(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, active(X3)) -> U21(X1, X2, X3) 7.31/2.88 U22(mark(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, mark(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, mark(X3)) -> U22(X1, X2, X3) 7.31/2.88 U22(active(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, active(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, active(X3)) -> U22(X1, X2, X3) 7.31/2.88 x(mark(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, mark(X2)) -> x(X1, X2) 7.31/2.88 x(active(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, active(X2)) -> x(X1, X2) 7.31/2.88 7.31/2.88 The set Q consists of the following terms: 7.31/2.88 7.31/2.88 active(U11(tt, x0, x1)) 7.31/2.88 active(U12(tt, x0, x1)) 7.31/2.88 active(U21(tt, x0, x1)) 7.31/2.88 active(U22(tt, x0, x1)) 7.31/2.88 active(plus(x0, 0)) 7.31/2.88 active(plus(x0, s(x1))) 7.31/2.88 active(x(x0, 0)) 7.31/2.88 active(x(x0, s(x1))) 7.31/2.88 mark(U11(x0, x1, x2)) 7.31/2.88 mark(tt) 7.31/2.88 mark(U12(x0, x1, x2)) 7.31/2.88 mark(s(x0)) 7.31/2.88 mark(plus(x0, x1)) 7.31/2.88 mark(U21(x0, x1, x2)) 7.31/2.88 mark(U22(x0, x1, x2)) 7.31/2.88 mark(x(x0, x1)) 7.31/2.88 mark(0) 7.31/2.88 U11(mark(x0), x1, x2) 7.31/2.88 U11(x0, mark(x1), x2) 7.31/2.88 U11(x0, x1, mark(x2)) 7.31/2.88 U11(active(x0), x1, x2) 7.31/2.88 U11(x0, active(x1), x2) 7.31/2.88 U11(x0, x1, active(x2)) 7.31/2.88 U12(mark(x0), x1, x2) 7.31/2.88 U12(x0, mark(x1), x2) 7.31/2.88 U12(x0, x1, mark(x2)) 7.31/2.88 U12(active(x0), x1, x2) 7.31/2.88 U12(x0, active(x1), x2) 7.31/2.88 U12(x0, x1, active(x2)) 7.31/2.88 s(mark(x0)) 7.31/2.88 s(active(x0)) 7.31/2.88 plus(mark(x0), x1) 7.31/2.88 plus(x0, mark(x1)) 7.31/2.88 plus(active(x0), x1) 7.31/2.88 plus(x0, active(x1)) 7.31/2.88 U21(mark(x0), x1, x2) 7.31/2.88 U21(x0, mark(x1), x2) 7.31/2.88 U21(x0, x1, mark(x2)) 7.31/2.88 U21(active(x0), x1, x2) 7.31/2.88 U21(x0, active(x1), x2) 7.31/2.88 U21(x0, x1, active(x2)) 7.31/2.88 U22(mark(x0), x1, x2) 7.31/2.88 U22(x0, mark(x1), x2) 7.31/2.88 U22(x0, x1, mark(x2)) 7.31/2.88 U22(active(x0), x1, x2) 7.31/2.88 U22(x0, active(x1), x2) 7.31/2.88 U22(x0, x1, active(x2)) 7.31/2.88 x(mark(x0), x1) 7.31/2.88 x(x0, mark(x1)) 7.31/2.88 x(active(x0), x1) 7.31/2.88 x(x0, active(x1)) 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (1) QTRSRRRProof (EQUIVALENT) 7.31/2.88 Used ordering: 7.31/2.88 active/1)YES( 7.31/2.88 U11/3(YES,YES,YES) 7.31/2.88 tt/0) 7.31/2.88 mark/1)YES( 7.31/2.88 U12/3(YES,YES,YES) 7.31/2.88 s/1(YES) 7.31/2.88 plus/2(YES,YES) 7.31/2.88 U21/3(YES,YES,YES) 7.31/2.88 U22/3(YES,YES,YES) 7.31/2.88 x/2(YES,YES) 7.31/2.88 0/0) 7.31/2.88 7.31/2.88 Quasi precedence: 7.31/2.88 [U21_3, U22_3, x_2] > [U11_3, tt, U12_3, plus_2] > s_1 7.31/2.88 7.31/2.88 7.31/2.88 Status: 7.31/2.88 U11_3: [3,2,1] 7.31/2.88 tt: multiset status 7.31/2.88 U12_3: [3,2,1] 7.31/2.88 s_1: multiset status 7.31/2.88 plus_2: [1,2] 7.31/2.88 U21_3: [2,3,1] 7.31/2.88 U22_3: [2,3,1] 7.31/2.88 x_2: [2,1] 7.31/2.88 0: multiset status 7.31/2.88 7.31/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.31/2.88 7.31/2.88 active(U12(tt, M, N)) -> mark(s(plus(N, M))) 7.31/2.88 active(U22(tt, M, N)) -> mark(plus(x(N, M), N)) 7.31/2.88 active(plus(N, 0)) -> mark(N) 7.31/2.88 active(plus(N, s(M))) -> mark(U11(tt, M, N)) 7.31/2.88 active(x(N, 0)) -> mark(0) 7.31/2.88 active(x(N, s(M))) -> mark(U21(tt, M, N)) 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (2) 7.31/2.88 Obligation: 7.31/2.88 Q restricted rewrite system: 7.31/2.88 The TRS R consists of the following rules: 7.31/2.88 7.31/2.88 active(U11(tt, M, N)) -> mark(U12(tt, M, N)) 7.31/2.88 active(U21(tt, M, N)) -> mark(U22(tt, M, N)) 7.31/2.88 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 7.31/2.88 mark(tt) -> active(tt) 7.31/2.88 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 7.31/2.88 mark(s(X)) -> active(s(mark(X))) 7.31/2.88 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 7.31/2.88 mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3)) 7.31/2.88 mark(U22(X1, X2, X3)) -> active(U22(mark(X1), X2, X3)) 7.31/2.88 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 7.31/2.88 mark(0) -> active(0) 7.31/2.88 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 7.31/2.88 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 7.31/2.88 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 7.31/2.88 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 7.31/2.88 s(mark(X)) -> s(X) 7.31/2.88 s(active(X)) -> s(X) 7.31/2.88 plus(mark(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, mark(X2)) -> plus(X1, X2) 7.31/2.88 plus(active(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, active(X2)) -> plus(X1, X2) 7.31/2.88 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 7.31/2.88 U21(active(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, active(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, active(X3)) -> U21(X1, X2, X3) 7.31/2.88 U22(mark(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, mark(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, mark(X3)) -> U22(X1, X2, X3) 7.31/2.88 U22(active(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, active(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, active(X3)) -> U22(X1, X2, X3) 7.31/2.88 x(mark(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, mark(X2)) -> x(X1, X2) 7.31/2.88 x(active(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, active(X2)) -> x(X1, X2) 7.31/2.88 7.31/2.88 The set Q consists of the following terms: 7.31/2.88 7.31/2.88 active(U11(tt, x0, x1)) 7.31/2.88 active(U12(tt, x0, x1)) 7.31/2.88 active(U21(tt, x0, x1)) 7.31/2.88 active(U22(tt, x0, x1)) 7.31/2.88 active(plus(x0, 0)) 7.31/2.88 active(plus(x0, s(x1))) 7.31/2.88 active(x(x0, 0)) 7.31/2.88 active(x(x0, s(x1))) 7.31/2.88 mark(U11(x0, x1, x2)) 7.31/2.88 mark(tt) 7.31/2.88 mark(U12(x0, x1, x2)) 7.31/2.88 mark(s(x0)) 7.31/2.88 mark(plus(x0, x1)) 7.31/2.88 mark(U21(x0, x1, x2)) 7.31/2.88 mark(U22(x0, x1, x2)) 7.31/2.88 mark(x(x0, x1)) 7.31/2.88 mark(0) 7.31/2.88 U11(mark(x0), x1, x2) 7.31/2.88 U11(x0, mark(x1), x2) 7.31/2.88 U11(x0, x1, mark(x2)) 7.31/2.88 U11(active(x0), x1, x2) 7.31/2.88 U11(x0, active(x1), x2) 7.31/2.88 U11(x0, x1, active(x2)) 7.31/2.88 U12(mark(x0), x1, x2) 7.31/2.88 U12(x0, mark(x1), x2) 7.31/2.88 U12(x0, x1, mark(x2)) 7.31/2.88 U12(active(x0), x1, x2) 7.31/2.88 U12(x0, active(x1), x2) 7.31/2.88 U12(x0, x1, active(x2)) 7.31/2.88 s(mark(x0)) 7.31/2.88 s(active(x0)) 7.31/2.88 plus(mark(x0), x1) 7.31/2.88 plus(x0, mark(x1)) 7.31/2.88 plus(active(x0), x1) 7.31/2.88 plus(x0, active(x1)) 7.31/2.88 U21(mark(x0), x1, x2) 7.31/2.88 U21(x0, mark(x1), x2) 7.31/2.88 U21(x0, x1, mark(x2)) 7.31/2.88 U21(active(x0), x1, x2) 7.31/2.88 U21(x0, active(x1), x2) 7.31/2.88 U21(x0, x1, active(x2)) 7.31/2.88 U22(mark(x0), x1, x2) 7.31/2.88 U22(x0, mark(x1), x2) 7.31/2.88 U22(x0, x1, mark(x2)) 7.31/2.88 U22(active(x0), x1, x2) 7.31/2.88 U22(x0, active(x1), x2) 7.31/2.88 U22(x0, x1, active(x2)) 7.31/2.88 x(mark(x0), x1) 7.31/2.88 x(x0, mark(x1)) 7.31/2.88 x(active(x0), x1) 7.31/2.88 x(x0, active(x1)) 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (3) QTRSRRRProof (EQUIVALENT) 7.31/2.88 Used ordering: 7.31/2.88 Polynomial interpretation [POLO]: 7.31/2.88 7.31/2.88 POL(0) = 0 7.31/2.88 POL(U11(x_1, x_2, x_3)) = 2 + 2*x_1 + x_2 + x_3 7.31/2.88 POL(U12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.31/2.88 POL(U21(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + x_3 7.31/2.88 POL(U22(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.31/2.88 POL(active(x_1)) = x_1 7.31/2.88 POL(mark(x_1)) = x_1 7.31/2.88 POL(plus(x_1, x_2)) = x_1 + 2*x_2 7.31/2.88 POL(s(x_1)) = x_1 7.31/2.88 POL(tt) = 0 7.31/2.88 POL(x(x_1, x_2)) = x_1 + x_2 7.31/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.31/2.88 7.31/2.88 active(U11(tt, M, N)) -> mark(U12(tt, M, N)) 7.31/2.88 active(U21(tt, M, N)) -> mark(U22(tt, M, N)) 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (4) 7.31/2.88 Obligation: 7.31/2.88 Q restricted rewrite system: 7.31/2.88 The TRS R consists of the following rules: 7.31/2.88 7.31/2.88 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 7.31/2.88 mark(tt) -> active(tt) 7.31/2.88 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 7.31/2.88 mark(s(X)) -> active(s(mark(X))) 7.31/2.88 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 7.31/2.88 mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3)) 7.31/2.88 mark(U22(X1, X2, X3)) -> active(U22(mark(X1), X2, X3)) 7.31/2.88 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 7.31/2.88 mark(0) -> active(0) 7.31/2.88 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 7.31/2.88 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 7.31/2.88 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 7.31/2.88 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 7.31/2.88 s(mark(X)) -> s(X) 7.31/2.88 s(active(X)) -> s(X) 7.31/2.88 plus(mark(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, mark(X2)) -> plus(X1, X2) 7.31/2.88 plus(active(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, active(X2)) -> plus(X1, X2) 7.31/2.88 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 7.31/2.88 U21(active(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, active(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, active(X3)) -> U21(X1, X2, X3) 7.31/2.88 U22(mark(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, mark(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, mark(X3)) -> U22(X1, X2, X3) 7.31/2.88 U22(active(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, active(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, active(X3)) -> U22(X1, X2, X3) 7.31/2.88 x(mark(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, mark(X2)) -> x(X1, X2) 7.31/2.88 x(active(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, active(X2)) -> x(X1, X2) 7.31/2.88 7.31/2.88 The set Q consists of the following terms: 7.31/2.88 7.31/2.88 active(U11(tt, x0, x1)) 7.31/2.88 active(U12(tt, x0, x1)) 7.31/2.88 active(U21(tt, x0, x1)) 7.31/2.88 active(U22(tt, x0, x1)) 7.31/2.88 active(plus(x0, 0)) 7.31/2.88 active(plus(x0, s(x1))) 7.31/2.88 active(x(x0, 0)) 7.31/2.88 active(x(x0, s(x1))) 7.31/2.88 mark(U11(x0, x1, x2)) 7.31/2.88 mark(tt) 7.31/2.88 mark(U12(x0, x1, x2)) 7.31/2.88 mark(s(x0)) 7.31/2.88 mark(plus(x0, x1)) 7.31/2.88 mark(U21(x0, x1, x2)) 7.31/2.88 mark(U22(x0, x1, x2)) 7.31/2.88 mark(x(x0, x1)) 7.31/2.88 mark(0) 7.31/2.88 U11(mark(x0), x1, x2) 7.31/2.88 U11(x0, mark(x1), x2) 7.31/2.88 U11(x0, x1, mark(x2)) 7.31/2.88 U11(active(x0), x1, x2) 7.31/2.88 U11(x0, active(x1), x2) 7.31/2.88 U11(x0, x1, active(x2)) 7.31/2.88 U12(mark(x0), x1, x2) 7.31/2.88 U12(x0, mark(x1), x2) 7.31/2.88 U12(x0, x1, mark(x2)) 7.31/2.88 U12(active(x0), x1, x2) 7.31/2.88 U12(x0, active(x1), x2) 7.31/2.88 U12(x0, x1, active(x2)) 7.31/2.88 s(mark(x0)) 7.31/2.88 s(active(x0)) 7.31/2.88 plus(mark(x0), x1) 7.31/2.88 plus(x0, mark(x1)) 7.31/2.88 plus(active(x0), x1) 7.31/2.88 plus(x0, active(x1)) 7.31/2.88 U21(mark(x0), x1, x2) 7.31/2.88 U21(x0, mark(x1), x2) 7.31/2.88 U21(x0, x1, mark(x2)) 7.31/2.88 U21(active(x0), x1, x2) 7.31/2.88 U21(x0, active(x1), x2) 7.31/2.88 U21(x0, x1, active(x2)) 7.31/2.88 U22(mark(x0), x1, x2) 7.31/2.88 U22(x0, mark(x1), x2) 7.31/2.88 U22(x0, x1, mark(x2)) 7.31/2.88 U22(active(x0), x1, x2) 7.31/2.88 U22(x0, active(x1), x2) 7.31/2.88 U22(x0, x1, active(x2)) 7.31/2.88 x(mark(x0), x1) 7.31/2.88 x(x0, mark(x1)) 7.31/2.88 x(active(x0), x1) 7.31/2.88 x(x0, active(x1)) 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (5) QTRSRRRProof (EQUIVALENT) 7.31/2.88 Used ordering: 7.31/2.88 Polynomial interpretation [POLO]: 7.31/2.88 7.31/2.88 POL(0) = 2 7.31/2.88 POL(U11(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 7.31/2.88 POL(U12(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 7.31/2.88 POL(U21(x_1, x_2, x_3)) = 1 + 2*x_1 + x_2 + 2*x_3 7.31/2.88 POL(U22(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + x_3 7.31/2.88 POL(active(x_1)) = x_1 7.31/2.88 POL(mark(x_1)) = 2*x_1 7.31/2.88 POL(plus(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 7.31/2.88 POL(s(x_1)) = 1 + 2*x_1 7.31/2.88 POL(tt) = 1 7.31/2.88 POL(x(x_1, x_2)) = x_1 + 2*x_2 7.31/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.31/2.88 7.31/2.88 mark(tt) -> active(tt) 7.31/2.88 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 7.31/2.88 mark(s(X)) -> active(s(mark(X))) 7.31/2.88 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 7.31/2.88 mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3)) 7.31/2.88 mark(U22(X1, X2, X3)) -> active(U22(mark(X1), X2, X3)) 7.31/2.88 mark(0) -> active(0) 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (6) 7.31/2.88 Obligation: 7.31/2.88 Q restricted rewrite system: 7.31/2.88 The TRS R consists of the following rules: 7.31/2.88 7.31/2.88 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 7.31/2.88 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 7.31/2.88 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 7.31/2.88 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 7.31/2.88 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 7.31/2.88 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 7.31/2.88 s(mark(X)) -> s(X) 7.31/2.88 s(active(X)) -> s(X) 7.31/2.88 plus(mark(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, mark(X2)) -> plus(X1, X2) 7.31/2.88 plus(active(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, active(X2)) -> plus(X1, X2) 7.31/2.88 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 7.31/2.88 U21(active(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, active(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, active(X3)) -> U21(X1, X2, X3) 7.31/2.88 U22(mark(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, mark(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, mark(X3)) -> U22(X1, X2, X3) 7.31/2.88 U22(active(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, active(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, active(X3)) -> U22(X1, X2, X3) 7.31/2.88 x(mark(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, mark(X2)) -> x(X1, X2) 7.31/2.88 x(active(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, active(X2)) -> x(X1, X2) 7.31/2.88 7.31/2.88 The set Q consists of the following terms: 7.31/2.88 7.31/2.88 active(U11(tt, x0, x1)) 7.31/2.88 active(U12(tt, x0, x1)) 7.31/2.88 active(U21(tt, x0, x1)) 7.31/2.88 active(U22(tt, x0, x1)) 7.31/2.88 active(plus(x0, 0)) 7.31/2.88 active(plus(x0, s(x1))) 7.31/2.88 active(x(x0, 0)) 7.31/2.88 active(x(x0, s(x1))) 7.31/2.88 mark(U11(x0, x1, x2)) 7.31/2.88 mark(tt) 7.31/2.88 mark(U12(x0, x1, x2)) 7.31/2.88 mark(s(x0)) 7.31/2.88 mark(plus(x0, x1)) 7.31/2.88 mark(U21(x0, x1, x2)) 7.31/2.88 mark(U22(x0, x1, x2)) 7.31/2.88 mark(x(x0, x1)) 7.31/2.88 mark(0) 7.31/2.88 U11(mark(x0), x1, x2) 7.31/2.88 U11(x0, mark(x1), x2) 7.31/2.88 U11(x0, x1, mark(x2)) 7.31/2.88 U11(active(x0), x1, x2) 7.31/2.88 U11(x0, active(x1), x2) 7.31/2.88 U11(x0, x1, active(x2)) 7.31/2.88 U12(mark(x0), x1, x2) 7.31/2.88 U12(x0, mark(x1), x2) 7.31/2.88 U12(x0, x1, mark(x2)) 7.31/2.88 U12(active(x0), x1, x2) 7.31/2.88 U12(x0, active(x1), x2) 7.31/2.88 U12(x0, x1, active(x2)) 7.31/2.88 s(mark(x0)) 7.31/2.88 s(active(x0)) 7.31/2.88 plus(mark(x0), x1) 7.31/2.88 plus(x0, mark(x1)) 7.31/2.88 plus(active(x0), x1) 7.31/2.88 plus(x0, active(x1)) 7.31/2.88 U21(mark(x0), x1, x2) 7.31/2.88 U21(x0, mark(x1), x2) 7.31/2.88 U21(x0, x1, mark(x2)) 7.31/2.88 U21(active(x0), x1, x2) 7.31/2.88 U21(x0, active(x1), x2) 7.31/2.88 U21(x0, x1, active(x2)) 7.31/2.88 U22(mark(x0), x1, x2) 7.31/2.88 U22(x0, mark(x1), x2) 7.31/2.88 U22(x0, x1, mark(x2)) 7.31/2.88 U22(active(x0), x1, x2) 7.31/2.88 U22(x0, active(x1), x2) 7.31/2.88 U22(x0, x1, active(x2)) 7.31/2.88 x(mark(x0), x1) 7.31/2.88 x(x0, mark(x1)) 7.31/2.88 x(active(x0), x1) 7.31/2.88 x(x0, active(x1)) 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (7) QTRSRRRProof (EQUIVALENT) 7.31/2.88 Used ordering: 7.31/2.88 Polynomial interpretation [POLO]: 7.31/2.88 7.31/2.88 POL(U11(x_1, x_2, x_3)) = 2 + x_1 + x_2 + 2*x_3 7.31/2.88 POL(U12(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 7.31/2.88 POL(U21(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 7.31/2.88 POL(U22(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 7.31/2.88 POL(active(x_1)) = x_1 7.31/2.88 POL(mark(x_1)) = 2*x_1 7.31/2.88 POL(plus(x_1, x_2)) = 2*x_1 + 2*x_2 7.31/2.88 POL(s(x_1)) = 2*x_1 7.31/2.88 POL(x(x_1, x_2)) = x_1 + x_2 7.31/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.31/2.88 7.31/2.88 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (8) 7.31/2.88 Obligation: 7.31/2.88 Q restricted rewrite system: 7.31/2.88 The TRS R consists of the following rules: 7.31/2.88 7.31/2.88 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 7.31/2.88 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 7.31/2.88 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 7.31/2.88 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 7.31/2.88 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 7.31/2.88 s(mark(X)) -> s(X) 7.31/2.88 s(active(X)) -> s(X) 7.31/2.88 plus(mark(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, mark(X2)) -> plus(X1, X2) 7.31/2.88 plus(active(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, active(X2)) -> plus(X1, X2) 7.31/2.88 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 7.31/2.88 U21(active(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, active(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, active(X3)) -> U21(X1, X2, X3) 7.31/2.88 U22(mark(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, mark(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, mark(X3)) -> U22(X1, X2, X3) 7.31/2.88 U22(active(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, active(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, active(X3)) -> U22(X1, X2, X3) 7.31/2.88 x(mark(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, mark(X2)) -> x(X1, X2) 7.31/2.88 x(active(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, active(X2)) -> x(X1, X2) 7.31/2.88 7.31/2.88 The set Q consists of the following terms: 7.31/2.88 7.31/2.88 active(U11(tt, x0, x1)) 7.31/2.88 active(U12(tt, x0, x1)) 7.31/2.88 active(U21(tt, x0, x1)) 7.31/2.88 active(U22(tt, x0, x1)) 7.31/2.88 active(plus(x0, 0)) 7.31/2.88 active(plus(x0, s(x1))) 7.31/2.88 active(x(x0, 0)) 7.31/2.88 active(x(x0, s(x1))) 7.31/2.88 mark(U11(x0, x1, x2)) 7.31/2.88 mark(tt) 7.31/2.88 mark(U12(x0, x1, x2)) 7.31/2.88 mark(s(x0)) 7.31/2.88 mark(plus(x0, x1)) 7.31/2.88 mark(U21(x0, x1, x2)) 7.31/2.88 mark(U22(x0, x1, x2)) 7.31/2.88 mark(x(x0, x1)) 7.31/2.88 mark(0) 7.31/2.88 U11(mark(x0), x1, x2) 7.31/2.88 U11(x0, mark(x1), x2) 7.31/2.88 U11(x0, x1, mark(x2)) 7.31/2.88 U11(active(x0), x1, x2) 7.31/2.88 U11(x0, active(x1), x2) 7.31/2.88 U11(x0, x1, active(x2)) 7.31/2.88 U12(mark(x0), x1, x2) 7.31/2.88 U12(x0, mark(x1), x2) 7.31/2.88 U12(x0, x1, mark(x2)) 7.31/2.88 U12(active(x0), x1, x2) 7.31/2.88 U12(x0, active(x1), x2) 7.31/2.88 U12(x0, x1, active(x2)) 7.31/2.88 s(mark(x0)) 7.31/2.88 s(active(x0)) 7.31/2.88 plus(mark(x0), x1) 7.31/2.88 plus(x0, mark(x1)) 7.31/2.88 plus(active(x0), x1) 7.31/2.88 plus(x0, active(x1)) 7.31/2.88 U21(mark(x0), x1, x2) 7.31/2.88 U21(x0, mark(x1), x2) 7.31/2.88 U21(x0, x1, mark(x2)) 7.31/2.88 U21(active(x0), x1, x2) 7.31/2.88 U21(x0, active(x1), x2) 7.31/2.88 U21(x0, x1, active(x2)) 7.31/2.88 U22(mark(x0), x1, x2) 7.31/2.88 U22(x0, mark(x1), x2) 7.31/2.88 U22(x0, x1, mark(x2)) 7.31/2.88 U22(active(x0), x1, x2) 7.31/2.88 U22(x0, active(x1), x2) 7.31/2.88 U22(x0, x1, active(x2)) 7.31/2.88 x(mark(x0), x1) 7.31/2.88 x(x0, mark(x1)) 7.31/2.88 x(active(x0), x1) 7.31/2.88 x(x0, active(x1)) 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (9) QTRSRRRProof (EQUIVALENT) 7.31/2.88 Used ordering: 7.31/2.88 Polynomial interpretation [POLO]: 7.31/2.88 7.31/2.88 POL(U11(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.31/2.88 POL(U12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.31/2.88 POL(U21(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.31/2.88 POL(U22(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.31/2.88 POL(active(x_1)) = 2 + x_1 7.31/2.88 POL(mark(x_1)) = 2*x_1 7.31/2.88 POL(plus(x_1, x_2)) = x_1 + x_2 7.31/2.88 POL(s(x_1)) = x_1 7.31/2.88 POL(x(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 7.31/2.88 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.31/2.88 7.31/2.88 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 7.31/2.88 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 7.31/2.88 s(active(X)) -> s(X) 7.31/2.88 plus(active(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, active(X2)) -> plus(X1, X2) 7.31/2.88 U21(active(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, active(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, active(X3)) -> U21(X1, X2, X3) 7.31/2.88 U22(active(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, active(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, active(X3)) -> U22(X1, X2, X3) 7.31/2.88 x(active(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, active(X2)) -> x(X1, X2) 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 7.31/2.88 ---------------------------------------- 7.31/2.88 7.31/2.88 (10) 7.31/2.88 Obligation: 7.31/2.88 Q restricted rewrite system: 7.31/2.88 The TRS R consists of the following rules: 7.31/2.88 7.31/2.88 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 7.31/2.88 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 7.31/2.88 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 7.31/2.88 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 7.31/2.88 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 7.31/2.88 s(mark(X)) -> s(X) 7.31/2.88 plus(mark(X1), X2) -> plus(X1, X2) 7.31/2.88 plus(X1, mark(X2)) -> plus(X1, X2) 7.31/2.88 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 7.31/2.88 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 7.31/2.88 U22(mark(X1), X2, X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, mark(X2), X3) -> U22(X1, X2, X3) 7.31/2.88 U22(X1, X2, mark(X3)) -> U22(X1, X2, X3) 7.31/2.88 x(mark(X1), X2) -> x(X1, X2) 7.31/2.88 x(X1, mark(X2)) -> x(X1, X2) 7.31/2.88 7.31/2.88 The set Q consists of the following terms: 7.31/2.88 7.31/2.88 active(U11(tt, x0, x1)) 7.31/2.88 active(U12(tt, x0, x1)) 7.31/2.88 active(U21(tt, x0, x1)) 7.31/2.88 active(U22(tt, x0, x1)) 7.31/2.88 active(plus(x0, 0)) 7.31/2.88 active(plus(x0, s(x1))) 7.31/2.88 active(x(x0, 0)) 7.31/2.88 active(x(x0, s(x1))) 7.31/2.88 mark(U11(x0, x1, x2)) 7.31/2.88 mark(tt) 7.31/2.88 mark(U12(x0, x1, x2)) 7.31/2.88 mark(s(x0)) 7.31/2.88 mark(plus(x0, x1)) 7.31/2.88 mark(U21(x0, x1, x2)) 7.31/2.88 mark(U22(x0, x1, x2)) 7.31/2.88 mark(x(x0, x1)) 7.31/2.88 mark(0) 7.31/2.88 U11(mark(x0), x1, x2) 7.31/2.88 U11(x0, mark(x1), x2) 7.31/2.88 U11(x0, x1, mark(x2)) 7.31/2.88 U11(active(x0), x1, x2) 7.31/2.88 U11(x0, active(x1), x2) 7.31/2.88 U11(x0, x1, active(x2)) 7.31/2.88 U12(mark(x0), x1, x2) 7.31/2.88 U12(x0, mark(x1), x2) 7.31/2.88 U12(x0, x1, mark(x2)) 7.31/2.89 U12(active(x0), x1, x2) 7.31/2.89 U12(x0, active(x1), x2) 7.31/2.89 U12(x0, x1, active(x2)) 7.31/2.89 s(mark(x0)) 7.31/2.89 s(active(x0)) 7.31/2.89 plus(mark(x0), x1) 7.31/2.89 plus(x0, mark(x1)) 7.31/2.89 plus(active(x0), x1) 7.31/2.89 plus(x0, active(x1)) 7.31/2.89 U21(mark(x0), x1, x2) 7.31/2.89 U21(x0, mark(x1), x2) 7.31/2.89 U21(x0, x1, mark(x2)) 7.31/2.89 U21(active(x0), x1, x2) 7.31/2.89 U21(x0, active(x1), x2) 7.31/2.89 U21(x0, x1, active(x2)) 7.31/2.89 U22(mark(x0), x1, x2) 7.31/2.89 U22(x0, mark(x1), x2) 7.31/2.89 U22(x0, x1, mark(x2)) 7.31/2.89 U22(active(x0), x1, x2) 7.31/2.89 U22(x0, active(x1), x2) 7.31/2.89 U22(x0, x1, active(x2)) 7.31/2.89 x(mark(x0), x1) 7.31/2.89 x(x0, mark(x1)) 7.31/2.89 x(active(x0), x1) 7.31/2.89 x(x0, active(x1)) 7.31/2.89 7.31/2.89 7.31/2.89 ---------------------------------------- 7.31/2.89 7.31/2.89 (11) QTRSRRRProof (EQUIVALENT) 7.31/2.89 Used ordering: 7.31/2.89 Polynomial interpretation [POLO]: 7.31/2.89 7.31/2.89 POL(U11(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 7.31/2.89 POL(U12(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 7.31/2.89 POL(U21(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 7.31/2.89 POL(U22(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 7.31/2.89 POL(active(x_1)) = x_1 7.31/2.89 POL(mark(x_1)) = 2*x_1 7.31/2.89 POL(plus(x_1, x_2)) = 2*x_1 + 2*x_2 7.62/2.89 POL(s(x_1)) = x_1 7.62/2.89 POL(x(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 7.62/2.89 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.62/2.89 7.62/2.89 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 7.62/2.89 7.62/2.89 7.62/2.89 7.62/2.89 7.62/2.89 ---------------------------------------- 7.62/2.89 7.62/2.89 (12) 7.62/2.89 Obligation: 7.62/2.89 Q restricted rewrite system: 7.62/2.89 The TRS R consists of the following rules: 7.62/2.89 7.62/2.89 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 7.62/2.89 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 7.62/2.89 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 7.62/2.89 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 7.62/2.89 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 7.62/2.89 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 7.62/2.89 s(mark(X)) -> s(X) 7.62/2.89 plus(mark(X1), X2) -> plus(X1, X2) 7.62/2.89 plus(X1, mark(X2)) -> plus(X1, X2) 7.62/2.89 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 7.62/2.89 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 7.62/2.89 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 7.62/2.89 U22(mark(X1), X2, X3) -> U22(X1, X2, X3) 7.62/2.89 U22(X1, mark(X2), X3) -> U22(X1, X2, X3) 7.62/2.89 U22(X1, X2, mark(X3)) -> U22(X1, X2, X3) 7.62/2.89 x(mark(X1), X2) -> x(X1, X2) 7.62/2.89 x(X1, mark(X2)) -> x(X1, X2) 7.62/2.89 7.62/2.89 The set Q consists of the following terms: 7.62/2.89 7.62/2.89 active(U11(tt, x0, x1)) 7.62/2.89 active(U12(tt, x0, x1)) 7.62/2.89 active(U21(tt, x0, x1)) 7.62/2.89 active(U22(tt, x0, x1)) 7.62/2.89 active(plus(x0, 0)) 7.62/2.89 active(plus(x0, s(x1))) 7.62/2.89 active(x(x0, 0)) 7.62/2.89 active(x(x0, s(x1))) 7.62/2.89 mark(U11(x0, x1, x2)) 7.62/2.89 mark(tt) 7.62/2.89 mark(U12(x0, x1, x2)) 7.62/2.89 mark(s(x0)) 7.62/2.89 mark(plus(x0, x1)) 7.62/2.89 mark(U21(x0, x1, x2)) 7.62/2.89 mark(U22(x0, x1, x2)) 7.62/2.89 mark(x(x0, x1)) 7.62/2.89 mark(0) 7.62/2.89 U11(mark(x0), x1, x2) 7.62/2.89 U11(x0, mark(x1), x2) 7.62/2.89 U11(x0, x1, mark(x2)) 7.62/2.89 U11(active(x0), x1, x2) 7.62/2.89 U11(x0, active(x1), x2) 7.62/2.89 U11(x0, x1, active(x2)) 7.62/2.89 U12(mark(x0), x1, x2) 7.62/2.89 U12(x0, mark(x1), x2) 7.62/2.89 U12(x0, x1, mark(x2)) 7.62/2.89 U12(active(x0), x1, x2) 7.62/2.89 U12(x0, active(x1), x2) 7.62/2.89 U12(x0, x1, active(x2)) 7.62/2.89 s(mark(x0)) 7.62/2.89 s(active(x0)) 7.62/2.89 plus(mark(x0), x1) 7.62/2.89 plus(x0, mark(x1)) 7.62/2.89 plus(active(x0), x1) 7.62/2.89 plus(x0, active(x1)) 7.62/2.89 U21(mark(x0), x1, x2) 7.62/2.89 U21(x0, mark(x1), x2) 7.62/2.89 U21(x0, x1, mark(x2)) 7.62/2.89 U21(active(x0), x1, x2) 7.62/2.89 U21(x0, active(x1), x2) 7.62/2.89 U21(x0, x1, active(x2)) 7.62/2.89 U22(mark(x0), x1, x2) 7.62/2.89 U22(x0, mark(x1), x2) 7.62/2.89 U22(x0, x1, mark(x2)) 7.62/2.89 U22(active(x0), x1, x2) 7.62/2.89 U22(x0, active(x1), x2) 7.62/2.89 U22(x0, x1, active(x2)) 7.62/2.89 x(mark(x0), x1) 7.62/2.89 x(x0, mark(x1)) 7.62/2.89 x(active(x0), x1) 7.62/2.89 x(x0, active(x1)) 7.62/2.89 7.62/2.89 7.62/2.89 ---------------------------------------- 7.62/2.89 7.62/2.89 (13) QTRSRRRProof (EQUIVALENT) 7.62/2.89 Used ordering: 7.62/2.89 Knuth-Bendix order [KBO] with precedence:mark_1 > x_2 > U22_3 > U21_3 > plus_2 > s_1 > U12_3 > U11_3 7.62/2.89 7.62/2.89 and weight map: 7.62/2.89 7.62/2.89 mark_1=0 7.62/2.89 s_1=1 7.62/2.89 U11_3=0 7.62/2.89 U12_3=0 7.62/2.89 plus_2=0 7.62/2.89 U21_3=0 7.62/2.89 U22_3=0 7.62/2.89 x_2=0 7.62/2.89 7.62/2.89 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.62/2.89 7.62/2.89 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 7.62/2.89 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 7.62/2.89 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 7.62/2.89 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 7.62/2.89 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 7.62/2.89 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 7.62/2.89 s(mark(X)) -> s(X) 7.62/2.89 plus(mark(X1), X2) -> plus(X1, X2) 7.62/2.89 plus(X1, mark(X2)) -> plus(X1, X2) 7.62/2.89 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 7.62/2.89 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 7.62/2.89 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 7.62/2.89 U22(mark(X1), X2, X3) -> U22(X1, X2, X3) 7.62/2.89 U22(X1, mark(X2), X3) -> U22(X1, X2, X3) 7.62/2.89 U22(X1, X2, mark(X3)) -> U22(X1, X2, X3) 7.62/2.89 x(mark(X1), X2) -> x(X1, X2) 7.62/2.89 x(X1, mark(X2)) -> x(X1, X2) 7.62/2.89 7.62/2.89 7.62/2.89 7.62/2.89 7.62/2.89 ---------------------------------------- 7.62/2.89 7.62/2.89 (14) 7.62/2.89 Obligation: 7.62/2.89 Q restricted rewrite system: 7.62/2.89 R is empty. 7.62/2.89 The set Q consists of the following terms: 7.62/2.89 7.62/2.89 active(U11(tt, x0, x1)) 7.62/2.89 active(U12(tt, x0, x1)) 7.62/2.89 active(U21(tt, x0, x1)) 7.62/2.89 active(U22(tt, x0, x1)) 7.62/2.89 active(plus(x0, 0)) 7.62/2.89 active(plus(x0, s(x1))) 7.62/2.89 active(x(x0, 0)) 7.62/2.89 active(x(x0, s(x1))) 7.62/2.89 mark(U11(x0, x1, x2)) 7.62/2.89 mark(tt) 7.62/2.89 mark(U12(x0, x1, x2)) 7.62/2.89 mark(s(x0)) 7.62/2.89 mark(plus(x0, x1)) 7.62/2.89 mark(U21(x0, x1, x2)) 7.62/2.89 mark(U22(x0, x1, x2)) 7.62/2.89 mark(x(x0, x1)) 7.62/2.89 mark(0) 7.62/2.89 U11(mark(x0), x1, x2) 7.62/2.89 U11(x0, mark(x1), x2) 7.62/2.89 U11(x0, x1, mark(x2)) 7.62/2.89 U11(active(x0), x1, x2) 7.62/2.89 U11(x0, active(x1), x2) 7.62/2.89 U11(x0, x1, active(x2)) 7.62/2.89 U12(mark(x0), x1, x2) 7.62/2.89 U12(x0, mark(x1), x2) 7.62/2.89 U12(x0, x1, mark(x2)) 7.62/2.89 U12(active(x0), x1, x2) 7.62/2.89 U12(x0, active(x1), x2) 7.62/2.89 U12(x0, x1, active(x2)) 7.62/2.89 s(mark(x0)) 7.62/2.89 s(active(x0)) 7.62/2.89 plus(mark(x0), x1) 7.62/2.89 plus(x0, mark(x1)) 7.62/2.89 plus(active(x0), x1) 7.62/2.89 plus(x0, active(x1)) 7.62/2.89 U21(mark(x0), x1, x2) 7.62/2.89 U21(x0, mark(x1), x2) 7.62/2.89 U21(x0, x1, mark(x2)) 7.62/2.89 U21(active(x0), x1, x2) 7.62/2.89 U21(x0, active(x1), x2) 7.62/2.89 U21(x0, x1, active(x2)) 7.62/2.89 U22(mark(x0), x1, x2) 7.62/2.89 U22(x0, mark(x1), x2) 7.62/2.89 U22(x0, x1, mark(x2)) 7.62/2.89 U22(active(x0), x1, x2) 7.62/2.89 U22(x0, active(x1), x2) 7.62/2.89 U22(x0, x1, active(x2)) 7.62/2.89 x(mark(x0), x1) 7.62/2.89 x(x0, mark(x1)) 7.62/2.89 x(active(x0), x1) 7.62/2.89 x(x0, active(x1)) 7.62/2.89 7.62/2.89 7.62/2.89 ---------------------------------------- 7.62/2.89 7.62/2.89 (15) RisEmptyProof (EQUIVALENT) 7.62/2.89 The TRS R is empty. Hence, termination is trivially proven. 7.62/2.89 ---------------------------------------- 7.62/2.89 7.62/2.89 (16) 7.62/2.89 YES 7.62/2.97 EOF