5.91/2.28 YES 5.91/2.29 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.91/2.29 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.91/2.29 5.91/2.29 5.91/2.29 Termination w.r.t. Q of the given QTRS could be proven: 5.91/2.29 5.91/2.29 (0) QTRS 5.91/2.29 (1) QTRSRRRProof [EQUIVALENT, 107 ms] 5.91/2.29 (2) QTRS 5.91/2.29 (3) QTRSRRRProof [EQUIVALENT, 25 ms] 5.91/2.29 (4) QTRS 5.91/2.29 (5) QTRSRRRProof [EQUIVALENT, 21 ms] 5.91/2.29 (6) QTRS 5.91/2.29 (7) QTRSRRRProof [EQUIVALENT, 21 ms] 5.91/2.29 (8) QTRS 5.91/2.29 (9) QTRSRRRProof [EQUIVALENT, 19 ms] 5.91/2.29 (10) QTRS 5.91/2.29 (11) QTRSRRRProof [EQUIVALENT, 10 ms] 5.91/2.29 (12) QTRS 5.91/2.29 (13) QTRSRRRProof [EQUIVALENT, 0 ms] 5.91/2.29 (14) QTRS 5.91/2.29 (15) RisEmptyProof [EQUIVALENT, 0 ms] 5.91/2.29 (16) YES 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (0) 5.91/2.29 Obligation: 5.91/2.29 Q restricted rewrite system: 5.91/2.29 The TRS R consists of the following rules: 5.91/2.29 5.91/2.29 active(U11(tt, M, N)) -> mark(U12(tt, M, N)) 5.91/2.29 active(U12(tt, M, N)) -> mark(s(plus(N, M))) 5.91/2.29 active(plus(N, 0)) -> mark(N) 5.91/2.29 active(plus(N, s(M))) -> mark(U11(tt, M, N)) 5.91/2.29 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 5.91/2.29 mark(tt) -> active(tt) 5.91/2.29 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 5.91/2.29 mark(s(X)) -> active(s(mark(X))) 5.91/2.29 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 5.91/2.29 mark(0) -> active(0) 5.91/2.29 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 5.91/2.29 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 5.91/2.29 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 5.91/2.29 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 5.91/2.29 s(mark(X)) -> s(X) 5.91/2.29 s(active(X)) -> s(X) 5.91/2.29 plus(mark(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, mark(X2)) -> plus(X1, X2) 5.91/2.29 plus(active(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, active(X2)) -> plus(X1, X2) 5.91/2.29 5.91/2.29 The set Q consists of the following terms: 5.91/2.29 5.91/2.29 active(U11(tt, x0, x1)) 5.91/2.29 active(U12(tt, x0, x1)) 5.91/2.29 active(plus(x0, 0)) 5.91/2.29 active(plus(x0, s(x1))) 5.91/2.29 mark(U11(x0, x1, x2)) 5.91/2.29 mark(tt) 5.91/2.29 mark(U12(x0, x1, x2)) 5.91/2.29 mark(s(x0)) 5.91/2.29 mark(plus(x0, x1)) 5.91/2.29 mark(0) 5.91/2.29 U11(mark(x0), x1, x2) 5.91/2.29 U11(x0, mark(x1), x2) 5.91/2.29 U11(x0, x1, mark(x2)) 5.91/2.29 U11(active(x0), x1, x2) 5.91/2.29 U11(x0, active(x1), x2) 5.91/2.29 U11(x0, x1, active(x2)) 5.91/2.29 U12(mark(x0), x1, x2) 5.91/2.29 U12(x0, mark(x1), x2) 5.91/2.29 U12(x0, x1, mark(x2)) 5.91/2.29 U12(active(x0), x1, x2) 5.91/2.29 U12(x0, active(x1), x2) 5.91/2.29 U12(x0, x1, active(x2)) 5.91/2.29 s(mark(x0)) 5.91/2.29 s(active(x0)) 5.91/2.29 plus(mark(x0), x1) 5.91/2.29 plus(x0, mark(x1)) 5.91/2.29 plus(active(x0), x1) 5.91/2.29 plus(x0, active(x1)) 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (1) QTRSRRRProof (EQUIVALENT) 5.91/2.29 Used ordering: 5.91/2.29 Polynomial interpretation [POLO]: 5.91/2.29 5.91/2.29 POL(0) = 0 5.91/2.29 POL(U11(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + x_3 5.91/2.29 POL(U12(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + x_3 5.91/2.29 POL(active(x_1)) = x_1 5.91/2.29 POL(mark(x_1)) = x_1 5.91/2.29 POL(plus(x_1, x_2)) = x_1 + 2*x_2 5.91/2.29 POL(s(x_1)) = 2 + x_1 5.91/2.29 POL(tt) = 0 5.91/2.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.91/2.29 5.91/2.29 active(plus(N, s(M))) -> mark(U11(tt, M, N)) 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (2) 5.91/2.29 Obligation: 5.91/2.29 Q restricted rewrite system: 5.91/2.29 The TRS R consists of the following rules: 5.91/2.29 5.91/2.29 active(U11(tt, M, N)) -> mark(U12(tt, M, N)) 5.91/2.29 active(U12(tt, M, N)) -> mark(s(plus(N, M))) 5.91/2.29 active(plus(N, 0)) -> mark(N) 5.91/2.29 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 5.91/2.29 mark(tt) -> active(tt) 5.91/2.29 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 5.91/2.29 mark(s(X)) -> active(s(mark(X))) 5.91/2.29 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 5.91/2.29 mark(0) -> active(0) 5.91/2.29 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 5.91/2.29 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 5.91/2.29 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 5.91/2.29 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 5.91/2.29 s(mark(X)) -> s(X) 5.91/2.29 s(active(X)) -> s(X) 5.91/2.29 plus(mark(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, mark(X2)) -> plus(X1, X2) 5.91/2.29 plus(active(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, active(X2)) -> plus(X1, X2) 5.91/2.29 5.91/2.29 The set Q consists of the following terms: 5.91/2.29 5.91/2.29 active(U11(tt, x0, x1)) 5.91/2.29 active(U12(tt, x0, x1)) 5.91/2.29 active(plus(x0, 0)) 5.91/2.29 active(plus(x0, s(x1))) 5.91/2.29 mark(U11(x0, x1, x2)) 5.91/2.29 mark(tt) 5.91/2.29 mark(U12(x0, x1, x2)) 5.91/2.29 mark(s(x0)) 5.91/2.29 mark(plus(x0, x1)) 5.91/2.29 mark(0) 5.91/2.29 U11(mark(x0), x1, x2) 5.91/2.29 U11(x0, mark(x1), x2) 5.91/2.29 U11(x0, x1, mark(x2)) 5.91/2.29 U11(active(x0), x1, x2) 5.91/2.29 U11(x0, active(x1), x2) 5.91/2.29 U11(x0, x1, active(x2)) 5.91/2.29 U12(mark(x0), x1, x2) 5.91/2.29 U12(x0, mark(x1), x2) 5.91/2.29 U12(x0, x1, mark(x2)) 5.91/2.29 U12(active(x0), x1, x2) 5.91/2.29 U12(x0, active(x1), x2) 5.91/2.29 U12(x0, x1, active(x2)) 5.91/2.29 s(mark(x0)) 5.91/2.29 s(active(x0)) 5.91/2.29 plus(mark(x0), x1) 5.91/2.29 plus(x0, mark(x1)) 5.91/2.29 plus(active(x0), x1) 5.91/2.29 plus(x0, active(x1)) 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (3) QTRSRRRProof (EQUIVALENT) 5.91/2.29 Used ordering: 5.91/2.29 Polynomial interpretation [POLO]: 5.91/2.29 5.91/2.29 POL(0) = 2 5.91/2.29 POL(U11(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 5.91/2.29 POL(U12(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 5.91/2.29 POL(active(x_1)) = x_1 5.91/2.29 POL(mark(x_1)) = x_1 5.91/2.29 POL(plus(x_1, x_2)) = x_1 + 2*x_2 5.91/2.29 POL(s(x_1)) = x_1 5.91/2.29 POL(tt) = 0 5.91/2.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.91/2.29 5.91/2.29 active(plus(N, 0)) -> mark(N) 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (4) 5.91/2.29 Obligation: 5.91/2.29 Q restricted rewrite system: 5.91/2.29 The TRS R consists of the following rules: 5.91/2.29 5.91/2.29 active(U11(tt, M, N)) -> mark(U12(tt, M, N)) 5.91/2.29 active(U12(tt, M, N)) -> mark(s(plus(N, M))) 5.91/2.29 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 5.91/2.29 mark(tt) -> active(tt) 5.91/2.29 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 5.91/2.29 mark(s(X)) -> active(s(mark(X))) 5.91/2.29 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 5.91/2.29 mark(0) -> active(0) 5.91/2.29 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 5.91/2.29 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 5.91/2.29 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 5.91/2.29 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 5.91/2.29 s(mark(X)) -> s(X) 5.91/2.29 s(active(X)) -> s(X) 5.91/2.29 plus(mark(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, mark(X2)) -> plus(X1, X2) 5.91/2.29 plus(active(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, active(X2)) -> plus(X1, X2) 5.91/2.29 5.91/2.29 The set Q consists of the following terms: 5.91/2.29 5.91/2.29 active(U11(tt, x0, x1)) 5.91/2.29 active(U12(tt, x0, x1)) 5.91/2.29 active(plus(x0, 0)) 5.91/2.29 active(plus(x0, s(x1))) 5.91/2.29 mark(U11(x0, x1, x2)) 5.91/2.29 mark(tt) 5.91/2.29 mark(U12(x0, x1, x2)) 5.91/2.29 mark(s(x0)) 5.91/2.29 mark(plus(x0, x1)) 5.91/2.29 mark(0) 5.91/2.29 U11(mark(x0), x1, x2) 5.91/2.29 U11(x0, mark(x1), x2) 5.91/2.29 U11(x0, x1, mark(x2)) 5.91/2.29 U11(active(x0), x1, x2) 5.91/2.29 U11(x0, active(x1), x2) 5.91/2.29 U11(x0, x1, active(x2)) 5.91/2.29 U12(mark(x0), x1, x2) 5.91/2.29 U12(x0, mark(x1), x2) 5.91/2.29 U12(x0, x1, mark(x2)) 5.91/2.29 U12(active(x0), x1, x2) 5.91/2.29 U12(x0, active(x1), x2) 5.91/2.29 U12(x0, x1, active(x2)) 5.91/2.29 s(mark(x0)) 5.91/2.29 s(active(x0)) 5.91/2.29 plus(mark(x0), x1) 5.91/2.29 plus(x0, mark(x1)) 5.91/2.29 plus(active(x0), x1) 5.91/2.29 plus(x0, active(x1)) 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (5) QTRSRRRProof (EQUIVALENT) 5.91/2.29 Used ordering: 5.91/2.29 Polynomial interpretation [POLO]: 5.91/2.29 5.91/2.29 POL(0) = 0 5.91/2.29 POL(U11(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 5.91/2.29 POL(U12(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 5.91/2.29 POL(active(x_1)) = x_1 5.91/2.29 POL(mark(x_1)) = x_1 5.91/2.29 POL(plus(x_1, x_2)) = x_1 + x_2 5.91/2.29 POL(s(x_1)) = 2*x_1 5.91/2.29 POL(tt) = 0 5.91/2.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.91/2.29 5.91/2.29 active(U11(tt, M, N)) -> mark(U12(tt, M, N)) 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (6) 5.91/2.29 Obligation: 5.91/2.29 Q restricted rewrite system: 5.91/2.29 The TRS R consists of the following rules: 5.91/2.29 5.91/2.29 active(U12(tt, M, N)) -> mark(s(plus(N, M))) 5.91/2.29 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 5.91/2.29 mark(tt) -> active(tt) 5.91/2.29 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 5.91/2.29 mark(s(X)) -> active(s(mark(X))) 5.91/2.29 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 5.91/2.29 mark(0) -> active(0) 5.91/2.29 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 5.91/2.29 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 5.91/2.29 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 5.91/2.29 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 5.91/2.29 s(mark(X)) -> s(X) 5.91/2.29 s(active(X)) -> s(X) 5.91/2.29 plus(mark(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, mark(X2)) -> plus(X1, X2) 5.91/2.29 plus(active(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, active(X2)) -> plus(X1, X2) 5.91/2.29 5.91/2.29 The set Q consists of the following terms: 5.91/2.29 5.91/2.29 active(U11(tt, x0, x1)) 5.91/2.29 active(U12(tt, x0, x1)) 5.91/2.29 active(plus(x0, 0)) 5.91/2.29 active(plus(x0, s(x1))) 5.91/2.29 mark(U11(x0, x1, x2)) 5.91/2.29 mark(tt) 5.91/2.29 mark(U12(x0, x1, x2)) 5.91/2.29 mark(s(x0)) 5.91/2.29 mark(plus(x0, x1)) 5.91/2.29 mark(0) 5.91/2.29 U11(mark(x0), x1, x2) 5.91/2.29 U11(x0, mark(x1), x2) 5.91/2.29 U11(x0, x1, mark(x2)) 5.91/2.29 U11(active(x0), x1, x2) 5.91/2.29 U11(x0, active(x1), x2) 5.91/2.29 U11(x0, x1, active(x2)) 5.91/2.29 U12(mark(x0), x1, x2) 5.91/2.29 U12(x0, mark(x1), x2) 5.91/2.29 U12(x0, x1, mark(x2)) 5.91/2.29 U12(active(x0), x1, x2) 5.91/2.29 U12(x0, active(x1), x2) 5.91/2.29 U12(x0, x1, active(x2)) 5.91/2.29 s(mark(x0)) 5.91/2.29 s(active(x0)) 5.91/2.29 plus(mark(x0), x1) 5.91/2.29 plus(x0, mark(x1)) 5.91/2.29 plus(active(x0), x1) 5.91/2.29 plus(x0, active(x1)) 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (7) QTRSRRRProof (EQUIVALENT) 5.91/2.29 Used ordering: 5.91/2.29 Polynomial interpretation [POLO]: 5.91/2.29 5.91/2.29 POL(0) = 0 5.91/2.29 POL(U11(x_1, x_2, x_3)) = x_1 + x_2 + x_3 5.91/2.29 POL(U12(x_1, x_2, x_3)) = 2 + x_1 + x_2 + 2*x_3 5.91/2.29 POL(active(x_1)) = x_1 5.91/2.29 POL(mark(x_1)) = x_1 5.91/2.29 POL(plus(x_1, x_2)) = 2*x_1 + x_2 5.91/2.29 POL(s(x_1)) = x_1 5.91/2.29 POL(tt) = 0 5.91/2.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.91/2.29 5.91/2.29 active(U12(tt, M, N)) -> mark(s(plus(N, M))) 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (8) 5.91/2.29 Obligation: 5.91/2.29 Q restricted rewrite system: 5.91/2.29 The TRS R consists of the following rules: 5.91/2.29 5.91/2.29 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 5.91/2.29 mark(tt) -> active(tt) 5.91/2.29 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 5.91/2.29 mark(s(X)) -> active(s(mark(X))) 5.91/2.29 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 5.91/2.29 mark(0) -> active(0) 5.91/2.29 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 5.91/2.29 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 5.91/2.29 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 5.91/2.29 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 5.91/2.29 s(mark(X)) -> s(X) 5.91/2.29 s(active(X)) -> s(X) 5.91/2.29 plus(mark(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, mark(X2)) -> plus(X1, X2) 5.91/2.29 plus(active(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, active(X2)) -> plus(X1, X2) 5.91/2.29 5.91/2.29 The set Q consists of the following terms: 5.91/2.29 5.91/2.29 active(U11(tt, x0, x1)) 5.91/2.29 active(U12(tt, x0, x1)) 5.91/2.29 active(plus(x0, 0)) 5.91/2.29 active(plus(x0, s(x1))) 5.91/2.29 mark(U11(x0, x1, x2)) 5.91/2.29 mark(tt) 5.91/2.29 mark(U12(x0, x1, x2)) 5.91/2.29 mark(s(x0)) 5.91/2.29 mark(plus(x0, x1)) 5.91/2.29 mark(0) 5.91/2.29 U11(mark(x0), x1, x2) 5.91/2.29 U11(x0, mark(x1), x2) 5.91/2.29 U11(x0, x1, mark(x2)) 5.91/2.29 U11(active(x0), x1, x2) 5.91/2.29 U11(x0, active(x1), x2) 5.91/2.29 U11(x0, x1, active(x2)) 5.91/2.29 U12(mark(x0), x1, x2) 5.91/2.29 U12(x0, mark(x1), x2) 5.91/2.29 U12(x0, x1, mark(x2)) 5.91/2.29 U12(active(x0), x1, x2) 5.91/2.29 U12(x0, active(x1), x2) 5.91/2.29 U12(x0, x1, active(x2)) 5.91/2.29 s(mark(x0)) 5.91/2.29 s(active(x0)) 5.91/2.29 plus(mark(x0), x1) 5.91/2.29 plus(x0, mark(x1)) 5.91/2.29 plus(active(x0), x1) 5.91/2.29 plus(x0, active(x1)) 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (9) QTRSRRRProof (EQUIVALENT) 5.91/2.29 Used ordering: 5.91/2.29 Polynomial interpretation [POLO]: 5.91/2.29 5.91/2.29 POL(0) = 2 5.91/2.29 POL(U11(x_1, x_2, x_3)) = 2 + 2*x_1 + x_2 + x_3 5.91/2.29 POL(U12(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 5.91/2.29 POL(active(x_1)) = x_1 5.91/2.29 POL(mark(x_1)) = 1 + 2*x_1 5.91/2.29 POL(plus(x_1, x_2)) = 2 + 2*x_1 + x_2 5.91/2.29 POL(s(x_1)) = 1 + x_1 5.91/2.29 POL(tt) = 2 5.91/2.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.91/2.29 5.91/2.29 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 5.91/2.29 mark(tt) -> active(tt) 5.91/2.29 mark(U12(X1, X2, X3)) -> active(U12(mark(X1), X2, X3)) 5.91/2.29 mark(s(X)) -> active(s(mark(X))) 5.91/2.29 mark(0) -> active(0) 5.91/2.29 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 5.91/2.29 U12(mark(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, mark(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, mark(X3)) -> U12(X1, X2, X3) 5.91/2.29 s(mark(X)) -> s(X) 5.91/2.29 plus(mark(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, mark(X2)) -> plus(X1, X2) 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (10) 5.91/2.29 Obligation: 5.91/2.29 Q restricted rewrite system: 5.91/2.29 The TRS R consists of the following rules: 5.91/2.29 5.91/2.29 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 5.91/2.29 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 5.91/2.29 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 5.91/2.29 s(active(X)) -> s(X) 5.91/2.29 plus(active(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, active(X2)) -> plus(X1, X2) 5.91/2.29 5.91/2.29 The set Q consists of the following terms: 5.91/2.29 5.91/2.29 active(U11(tt, x0, x1)) 5.91/2.29 active(U12(tt, x0, x1)) 5.91/2.29 active(plus(x0, 0)) 5.91/2.29 active(plus(x0, s(x1))) 5.91/2.29 mark(U11(x0, x1, x2)) 5.91/2.29 mark(tt) 5.91/2.29 mark(U12(x0, x1, x2)) 5.91/2.29 mark(s(x0)) 5.91/2.29 mark(plus(x0, x1)) 5.91/2.29 mark(0) 5.91/2.29 U11(mark(x0), x1, x2) 5.91/2.29 U11(x0, mark(x1), x2) 5.91/2.29 U11(x0, x1, mark(x2)) 5.91/2.29 U11(active(x0), x1, x2) 5.91/2.29 U11(x0, active(x1), x2) 5.91/2.29 U11(x0, x1, active(x2)) 5.91/2.29 U12(mark(x0), x1, x2) 5.91/2.29 U12(x0, mark(x1), x2) 5.91/2.29 U12(x0, x1, mark(x2)) 5.91/2.29 U12(active(x0), x1, x2) 5.91/2.29 U12(x0, active(x1), x2) 5.91/2.29 U12(x0, x1, active(x2)) 5.91/2.29 s(mark(x0)) 5.91/2.29 s(active(x0)) 5.91/2.29 plus(mark(x0), x1) 5.91/2.29 plus(x0, mark(x1)) 5.91/2.29 plus(active(x0), x1) 5.91/2.29 plus(x0, active(x1)) 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (11) QTRSRRRProof (EQUIVALENT) 5.91/2.29 Used ordering: 5.91/2.29 Polynomial interpretation [POLO]: 5.91/2.29 5.91/2.29 POL(U11(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 5.91/2.29 POL(U12(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 5.91/2.29 POL(active(x_1)) = 2 + x_1 5.91/2.29 POL(mark(x_1)) = 2*x_1 5.91/2.29 POL(plus(x_1, x_2)) = 2 + 2*x_1 + x_2 5.91/2.29 POL(s(x_1)) = x_1 5.91/2.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.91/2.29 5.91/2.29 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 5.91/2.29 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 5.91/2.29 U12(active(X1), X2, X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, active(X2), X3) -> U12(X1, X2, X3) 5.91/2.29 U12(X1, X2, active(X3)) -> U12(X1, X2, X3) 5.91/2.29 s(active(X)) -> s(X) 5.91/2.29 plus(active(X1), X2) -> plus(X1, X2) 5.91/2.29 plus(X1, active(X2)) -> plus(X1, X2) 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (12) 5.91/2.29 Obligation: 5.91/2.29 Q restricted rewrite system: 5.91/2.29 The TRS R consists of the following rules: 5.91/2.29 5.91/2.29 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 5.91/2.29 5.91/2.29 The set Q consists of the following terms: 5.91/2.29 5.91/2.29 active(U11(tt, x0, x1)) 5.91/2.29 active(U12(tt, x0, x1)) 5.91/2.29 active(plus(x0, 0)) 5.91/2.29 active(plus(x0, s(x1))) 5.91/2.29 mark(U11(x0, x1, x2)) 5.91/2.29 mark(tt) 5.91/2.29 mark(U12(x0, x1, x2)) 5.91/2.29 mark(s(x0)) 5.91/2.29 mark(plus(x0, x1)) 5.91/2.29 mark(0) 5.91/2.29 U11(mark(x0), x1, x2) 5.91/2.29 U11(x0, mark(x1), x2) 5.91/2.29 U11(x0, x1, mark(x2)) 5.91/2.29 U11(active(x0), x1, x2) 5.91/2.29 U11(x0, active(x1), x2) 5.91/2.29 U11(x0, x1, active(x2)) 5.91/2.29 U12(mark(x0), x1, x2) 5.91/2.29 U12(x0, mark(x1), x2) 5.91/2.29 U12(x0, x1, mark(x2)) 5.91/2.29 U12(active(x0), x1, x2) 5.91/2.29 U12(x0, active(x1), x2) 5.91/2.29 U12(x0, x1, active(x2)) 5.91/2.29 s(mark(x0)) 5.91/2.29 s(active(x0)) 5.91/2.29 plus(mark(x0), x1) 5.91/2.29 plus(x0, mark(x1)) 5.91/2.29 plus(active(x0), x1) 5.91/2.29 plus(x0, active(x1)) 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (13) QTRSRRRProof (EQUIVALENT) 5.91/2.29 Used ordering: 5.91/2.29 Polynomial interpretation [POLO]: 5.91/2.29 5.91/2.29 POL(active(x_1)) = x_1 5.91/2.29 POL(mark(x_1)) = 2*x_1 5.91/2.29 POL(plus(x_1, x_2)) = 1 + x_1 + 2*x_2 5.91/2.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.91/2.29 5.91/2.29 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (14) 5.91/2.29 Obligation: 5.91/2.29 Q restricted rewrite system: 5.91/2.29 R is empty. 5.91/2.29 The set Q consists of the following terms: 5.91/2.29 5.91/2.29 active(U11(tt, x0, x1)) 5.91/2.29 active(U12(tt, x0, x1)) 5.91/2.29 active(plus(x0, 0)) 5.91/2.29 active(plus(x0, s(x1))) 5.91/2.29 mark(U11(x0, x1, x2)) 5.91/2.29 mark(tt) 5.91/2.29 mark(U12(x0, x1, x2)) 5.91/2.29 mark(s(x0)) 5.91/2.29 mark(plus(x0, x1)) 5.91/2.29 mark(0) 5.91/2.29 U11(mark(x0), x1, x2) 5.91/2.29 U11(x0, mark(x1), x2) 5.91/2.29 U11(x0, x1, mark(x2)) 5.91/2.29 U11(active(x0), x1, x2) 5.91/2.29 U11(x0, active(x1), x2) 5.91/2.29 U11(x0, x1, active(x2)) 5.91/2.29 U12(mark(x0), x1, x2) 5.91/2.29 U12(x0, mark(x1), x2) 5.91/2.29 U12(x0, x1, mark(x2)) 5.91/2.29 U12(active(x0), x1, x2) 5.91/2.29 U12(x0, active(x1), x2) 5.91/2.29 U12(x0, x1, active(x2)) 5.91/2.29 s(mark(x0)) 5.91/2.29 s(active(x0)) 5.91/2.29 plus(mark(x0), x1) 5.91/2.29 plus(x0, mark(x1)) 5.91/2.29 plus(active(x0), x1) 5.91/2.29 plus(x0, active(x1)) 5.91/2.29 5.91/2.29 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (15) RisEmptyProof (EQUIVALENT) 5.91/2.29 The TRS R is empty. Hence, termination is trivially proven. 5.91/2.29 ---------------------------------------- 5.91/2.29 5.91/2.29 (16) 5.91/2.29 YES 5.98/2.32 EOF