4.93/2.07 YES 4.93/2.08 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.93/2.08 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.93/2.08 4.93/2.08 4.93/2.08 Termination w.r.t. Q of the given QTRS could be proven: 4.93/2.08 4.93/2.08 (0) QTRS 4.93/2.08 (1) QTRSRRRProof [EQUIVALENT, 242 ms] 4.93/2.08 (2) QTRS 4.93/2.08 (3) QTRSRRRProof [EQUIVALENT, 21 ms] 4.93/2.08 (4) QTRS 4.93/2.08 (5) QTRSRRRProof [EQUIVALENT, 0 ms] 4.93/2.08 (6) QTRS 4.93/2.08 (7) RisEmptyProof [EQUIVALENT, 0 ms] 4.93/2.08 (8) YES 4.93/2.08 4.93/2.08 4.93/2.08 ---------------------------------------- 4.93/2.08 4.93/2.08 (0) 4.93/2.08 Obligation: 4.93/2.08 Q restricted rewrite system: 4.93/2.08 The TRS R consists of the following rules: 4.93/2.08 4.93/2.08 active(U11(tt, N)) -> mark(N) 4.93/2.08 active(U21(tt, M, N)) -> mark(s(plus(N, M))) 4.93/2.08 active(and(tt, X)) -> mark(X) 4.93/2.08 active(isNat(0)) -> mark(tt) 4.93/2.08 active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2))) 4.93/2.08 active(isNat(s(V1))) -> mark(isNat(V1)) 4.93/2.08 active(plus(N, 0)) -> mark(U11(isNat(N), N)) 4.93/2.08 active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N)) 4.93/2.08 mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) 4.93/2.08 mark(tt) -> active(tt) 4.93/2.08 mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3)) 4.93/2.08 mark(s(X)) -> active(s(mark(X))) 4.93/2.08 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 4.93/2.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 4.93/2.08 mark(isNat(X)) -> active(isNat(X)) 4.93/2.08 mark(0) -> active(0) 4.93/2.08 U11(mark(X1), X2) -> U11(X1, X2) 4.93/2.08 U11(X1, mark(X2)) -> U11(X1, X2) 4.93/2.08 U11(active(X1), X2) -> U11(X1, X2) 4.93/2.08 U11(X1, active(X2)) -> U11(X1, X2) 4.93/2.08 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 4.93/2.08 U21(active(X1), X2, X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, active(X2), X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, X2, active(X3)) -> U21(X1, X2, X3) 4.93/2.08 s(mark(X)) -> s(X) 4.93/2.08 s(active(X)) -> s(X) 4.93/2.08 plus(mark(X1), X2) -> plus(X1, X2) 4.93/2.08 plus(X1, mark(X2)) -> plus(X1, X2) 4.93/2.08 plus(active(X1), X2) -> plus(X1, X2) 4.93/2.08 plus(X1, active(X2)) -> plus(X1, X2) 4.93/2.08 and(mark(X1), X2) -> and(X1, X2) 4.93/2.08 and(X1, mark(X2)) -> and(X1, X2) 4.93/2.08 and(active(X1), X2) -> and(X1, X2) 4.93/2.08 and(X1, active(X2)) -> and(X1, X2) 4.93/2.08 isNat(mark(X)) -> isNat(X) 4.93/2.08 isNat(active(X)) -> isNat(X) 4.93/2.08 4.93/2.08 The set Q consists of the following terms: 4.93/2.08 4.93/2.08 active(U11(tt, x0)) 4.93/2.08 active(U21(tt, x0, x1)) 4.93/2.08 active(and(tt, x0)) 4.93/2.08 active(isNat(0)) 4.93/2.08 active(isNat(plus(x0, x1))) 4.93/2.08 active(isNat(s(x0))) 4.93/2.08 active(plus(x0, 0)) 4.93/2.08 active(plus(x0, s(x1))) 4.93/2.08 mark(U11(x0, x1)) 4.93/2.08 mark(tt) 4.93/2.08 mark(U21(x0, x1, x2)) 4.93/2.08 mark(s(x0)) 4.93/2.08 mark(plus(x0, x1)) 4.93/2.08 mark(and(x0, x1)) 4.93/2.08 mark(isNat(x0)) 4.93/2.08 mark(0) 4.93/2.08 U11(mark(x0), x1) 4.93/2.08 U11(x0, mark(x1)) 4.93/2.08 U11(active(x0), x1) 4.93/2.08 U11(x0, active(x1)) 4.93/2.08 U21(mark(x0), x1, x2) 4.93/2.08 U21(x0, mark(x1), x2) 4.93/2.08 U21(x0, x1, mark(x2)) 4.93/2.08 U21(active(x0), x1, x2) 4.93/2.08 U21(x0, active(x1), x2) 4.93/2.08 U21(x0, x1, active(x2)) 4.93/2.08 s(mark(x0)) 4.93/2.08 s(active(x0)) 4.93/2.08 plus(mark(x0), x1) 4.93/2.08 plus(x0, mark(x1)) 4.93/2.08 plus(active(x0), x1) 4.93/2.08 plus(x0, active(x1)) 4.93/2.08 and(mark(x0), x1) 4.93/2.08 and(x0, mark(x1)) 4.93/2.08 and(active(x0), x1) 4.93/2.08 and(x0, active(x1)) 4.93/2.08 isNat(mark(x0)) 4.93/2.08 isNat(active(x0)) 4.93/2.08 4.93/2.08 4.93/2.08 ---------------------------------------- 4.93/2.08 4.93/2.08 (1) QTRSRRRProof (EQUIVALENT) 4.93/2.08 Used ordering: 4.93/2.08 active/1)YES( 4.93/2.08 U11/2(YES,YES) 4.93/2.08 tt/0) 4.93/2.08 mark/1)YES( 4.93/2.08 U21/3(YES,YES,YES) 4.93/2.08 s/1(YES) 4.93/2.08 plus/2(YES,YES) 4.93/2.08 and/2(YES,YES) 4.93/2.08 isNat/1(YES) 4.93/2.08 0/0) 4.93/2.08 4.93/2.08 Quasi precedence: 4.93/2.08 [tt, U21_3, plus_2, 0] > U11_2 4.93/2.08 [tt, U21_3, plus_2, 0] > [s_1, and_2, isNat_1] 4.93/2.08 4.93/2.08 4.93/2.08 Status: 4.93/2.08 U11_2: multiset status 4.93/2.08 tt: multiset status 4.93/2.08 U21_3: [3,2,1] 4.93/2.08 s_1: multiset status 4.93/2.08 plus_2: [1,2] 4.93/2.08 and_2: multiset status 4.93/2.08 isNat_1: multiset status 4.93/2.08 0: multiset status 4.93/2.08 4.93/2.08 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.93/2.08 4.93/2.08 active(U11(tt, N)) -> mark(N) 4.93/2.08 active(U21(tt, M, N)) -> mark(s(plus(N, M))) 4.93/2.08 active(and(tt, X)) -> mark(X) 4.93/2.08 active(isNat(0)) -> mark(tt) 4.93/2.08 active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2))) 4.93/2.08 active(isNat(s(V1))) -> mark(isNat(V1)) 4.93/2.08 active(plus(N, 0)) -> mark(U11(isNat(N), N)) 4.93/2.08 active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N)) 4.93/2.08 4.93/2.08 4.93/2.08 4.93/2.08 4.93/2.08 ---------------------------------------- 4.93/2.08 4.93/2.08 (2) 4.93/2.08 Obligation: 4.93/2.08 Q restricted rewrite system: 4.93/2.08 The TRS R consists of the following rules: 4.93/2.08 4.93/2.08 mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) 4.93/2.08 mark(tt) -> active(tt) 4.93/2.08 mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3)) 4.93/2.08 mark(s(X)) -> active(s(mark(X))) 4.93/2.08 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 4.93/2.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 4.93/2.08 mark(isNat(X)) -> active(isNat(X)) 4.93/2.08 mark(0) -> active(0) 4.93/2.08 U11(mark(X1), X2) -> U11(X1, X2) 4.93/2.08 U11(X1, mark(X2)) -> U11(X1, X2) 4.93/2.08 U11(active(X1), X2) -> U11(X1, X2) 4.93/2.08 U11(X1, active(X2)) -> U11(X1, X2) 4.93/2.08 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 4.93/2.08 U21(active(X1), X2, X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, active(X2), X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, X2, active(X3)) -> U21(X1, X2, X3) 4.93/2.08 s(mark(X)) -> s(X) 4.93/2.08 s(active(X)) -> s(X) 4.93/2.08 plus(mark(X1), X2) -> plus(X1, X2) 4.93/2.08 plus(X1, mark(X2)) -> plus(X1, X2) 4.93/2.08 plus(active(X1), X2) -> plus(X1, X2) 4.93/2.08 plus(X1, active(X2)) -> plus(X1, X2) 4.93/2.08 and(mark(X1), X2) -> and(X1, X2) 4.93/2.08 and(X1, mark(X2)) -> and(X1, X2) 4.93/2.08 and(active(X1), X2) -> and(X1, X2) 4.93/2.08 and(X1, active(X2)) -> and(X1, X2) 4.93/2.08 isNat(mark(X)) -> isNat(X) 4.93/2.08 isNat(active(X)) -> isNat(X) 4.93/2.08 4.93/2.08 The set Q consists of the following terms: 4.93/2.08 4.93/2.08 active(U11(tt, x0)) 4.93/2.08 active(U21(tt, x0, x1)) 4.93/2.08 active(and(tt, x0)) 4.93/2.08 active(isNat(0)) 4.93/2.08 active(isNat(plus(x0, x1))) 4.93/2.08 active(isNat(s(x0))) 4.93/2.08 active(plus(x0, 0)) 4.93/2.08 active(plus(x0, s(x1))) 4.93/2.08 mark(U11(x0, x1)) 4.93/2.08 mark(tt) 4.93/2.08 mark(U21(x0, x1, x2)) 4.93/2.08 mark(s(x0)) 4.93/2.08 mark(plus(x0, x1)) 4.93/2.08 mark(and(x0, x1)) 4.93/2.08 mark(isNat(x0)) 4.93/2.08 mark(0) 4.93/2.08 U11(mark(x0), x1) 4.93/2.08 U11(x0, mark(x1)) 4.93/2.08 U11(active(x0), x1) 4.93/2.08 U11(x0, active(x1)) 4.93/2.08 U21(mark(x0), x1, x2) 4.93/2.08 U21(x0, mark(x1), x2) 4.93/2.08 U21(x0, x1, mark(x2)) 4.93/2.08 U21(active(x0), x1, x2) 4.93/2.08 U21(x0, active(x1), x2) 4.93/2.08 U21(x0, x1, active(x2)) 4.93/2.08 s(mark(x0)) 4.93/2.08 s(active(x0)) 4.93/2.08 plus(mark(x0), x1) 4.93/2.08 plus(x0, mark(x1)) 4.93/2.08 plus(active(x0), x1) 4.93/2.08 plus(x0, active(x1)) 4.93/2.08 and(mark(x0), x1) 4.93/2.08 and(x0, mark(x1)) 4.93/2.08 and(active(x0), x1) 4.93/2.08 and(x0, active(x1)) 4.93/2.08 isNat(mark(x0)) 4.93/2.08 isNat(active(x0)) 4.93/2.08 4.93/2.08 4.93/2.08 ---------------------------------------- 4.93/2.08 4.93/2.08 (3) QTRSRRRProof (EQUIVALENT) 4.93/2.08 Used ordering: 4.93/2.08 Polynomial interpretation [POLO]: 4.93/2.08 4.93/2.08 POL(0) = 2 4.93/2.08 POL(U11(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 4.93/2.08 POL(U21(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 4.93/2.08 POL(active(x_1)) = 1 + x_1 4.93/2.08 POL(and(x_1, x_2)) = 2 + 2*x_1 + x_2 4.93/2.08 POL(isNat(x_1)) = 2 + x_1 4.93/2.08 POL(mark(x_1)) = 2*x_1 4.93/2.08 POL(plus(x_1, x_2)) = 2 + x_1 + 2*x_2 4.93/2.08 POL(s(x_1)) = 2 + x_1 4.93/2.08 POL(tt) = 2 4.93/2.08 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.93/2.08 4.93/2.08 mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) 4.93/2.08 mark(tt) -> active(tt) 4.93/2.08 mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3)) 4.93/2.08 mark(s(X)) -> active(s(mark(X))) 4.93/2.08 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 4.93/2.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 4.93/2.08 mark(isNat(X)) -> active(isNat(X)) 4.93/2.08 mark(0) -> active(0) 4.93/2.08 U11(active(X1), X2) -> U11(X1, X2) 4.93/2.08 U11(X1, active(X2)) -> U11(X1, X2) 4.93/2.08 U21(active(X1), X2, X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, active(X2), X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, X2, active(X3)) -> U21(X1, X2, X3) 4.93/2.08 s(active(X)) -> s(X) 4.93/2.08 plus(active(X1), X2) -> plus(X1, X2) 4.93/2.08 plus(X1, active(X2)) -> plus(X1, X2) 4.93/2.08 and(active(X1), X2) -> and(X1, X2) 4.93/2.08 and(X1, active(X2)) -> and(X1, X2) 4.93/2.08 isNat(active(X)) -> isNat(X) 4.93/2.08 4.93/2.08 4.93/2.08 4.93/2.08 4.93/2.08 ---------------------------------------- 4.93/2.08 4.93/2.08 (4) 4.93/2.08 Obligation: 4.93/2.08 Q restricted rewrite system: 4.93/2.08 The TRS R consists of the following rules: 4.93/2.08 4.93/2.08 U11(mark(X1), X2) -> U11(X1, X2) 4.93/2.08 U11(X1, mark(X2)) -> U11(X1, X2) 4.93/2.08 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 4.93/2.08 s(mark(X)) -> s(X) 4.93/2.08 plus(mark(X1), X2) -> plus(X1, X2) 4.93/2.08 plus(X1, mark(X2)) -> plus(X1, X2) 4.93/2.08 and(mark(X1), X2) -> and(X1, X2) 4.93/2.08 and(X1, mark(X2)) -> and(X1, X2) 4.93/2.08 isNat(mark(X)) -> isNat(X) 4.93/2.08 4.93/2.08 The set Q consists of the following terms: 4.93/2.08 4.93/2.08 active(U11(tt, x0)) 4.93/2.08 active(U21(tt, x0, x1)) 4.93/2.08 active(and(tt, x0)) 4.93/2.08 active(isNat(0)) 4.93/2.08 active(isNat(plus(x0, x1))) 4.93/2.08 active(isNat(s(x0))) 4.93/2.08 active(plus(x0, 0)) 4.93/2.08 active(plus(x0, s(x1))) 4.93/2.08 mark(U11(x0, x1)) 4.93/2.08 mark(tt) 4.93/2.08 mark(U21(x0, x1, x2)) 4.93/2.08 mark(s(x0)) 4.93/2.08 mark(plus(x0, x1)) 4.93/2.08 mark(and(x0, x1)) 4.93/2.08 mark(isNat(x0)) 4.93/2.08 mark(0) 4.93/2.08 U11(mark(x0), x1) 4.93/2.08 U11(x0, mark(x1)) 4.93/2.08 U11(active(x0), x1) 4.93/2.08 U11(x0, active(x1)) 4.93/2.08 U21(mark(x0), x1, x2) 4.93/2.08 U21(x0, mark(x1), x2) 4.93/2.08 U21(x0, x1, mark(x2)) 4.93/2.08 U21(active(x0), x1, x2) 4.93/2.08 U21(x0, active(x1), x2) 4.93/2.08 U21(x0, x1, active(x2)) 4.93/2.08 s(mark(x0)) 4.93/2.08 s(active(x0)) 4.93/2.08 plus(mark(x0), x1) 4.93/2.08 plus(x0, mark(x1)) 4.93/2.08 plus(active(x0), x1) 4.93/2.08 plus(x0, active(x1)) 4.93/2.08 and(mark(x0), x1) 4.93/2.08 and(x0, mark(x1)) 4.93/2.08 and(active(x0), x1) 4.93/2.08 and(x0, active(x1)) 4.93/2.08 isNat(mark(x0)) 4.93/2.08 isNat(active(x0)) 4.93/2.08 4.93/2.08 4.93/2.08 ---------------------------------------- 4.93/2.08 4.93/2.08 (5) QTRSRRRProof (EQUIVALENT) 4.93/2.08 Used ordering: 4.93/2.08 Knuth-Bendix order [KBO] with precedence:mark_1 > isNat_1 > and_2 > plus_2 > s_1 > U11_2 > U21_3 4.93/2.08 4.93/2.08 and weight map: 4.93/2.08 4.93/2.08 mark_1=0 4.93/2.08 s_1=1 4.93/2.08 isNat_1=1 4.93/2.08 U11_2=0 4.93/2.08 U21_3=0 4.93/2.08 plus_2=0 4.93/2.08 and_2=0 4.93/2.08 4.93/2.08 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.93/2.08 4.93/2.08 U11(mark(X1), X2) -> U11(X1, X2) 4.93/2.08 U11(X1, mark(X2)) -> U11(X1, X2) 4.93/2.08 U21(mark(X1), X2, X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, mark(X2), X3) -> U21(X1, X2, X3) 4.93/2.08 U21(X1, X2, mark(X3)) -> U21(X1, X2, X3) 4.93/2.08 s(mark(X)) -> s(X) 4.93/2.08 plus(mark(X1), X2) -> plus(X1, X2) 4.93/2.08 plus(X1, mark(X2)) -> plus(X1, X2) 4.93/2.08 and(mark(X1), X2) -> and(X1, X2) 4.93/2.08 and(X1, mark(X2)) -> and(X1, X2) 4.93/2.08 isNat(mark(X)) -> isNat(X) 4.93/2.08 4.93/2.08 4.93/2.08 4.93/2.08 4.93/2.08 ---------------------------------------- 4.93/2.08 4.93/2.08 (6) 4.93/2.08 Obligation: 4.93/2.08 Q restricted rewrite system: 4.93/2.08 R is empty. 4.93/2.08 The set Q consists of the following terms: 4.93/2.08 4.93/2.08 active(U11(tt, x0)) 4.93/2.08 active(U21(tt, x0, x1)) 4.93/2.08 active(and(tt, x0)) 4.93/2.08 active(isNat(0)) 4.93/2.08 active(isNat(plus(x0, x1))) 4.93/2.08 active(isNat(s(x0))) 4.93/2.08 active(plus(x0, 0)) 4.93/2.08 active(plus(x0, s(x1))) 4.93/2.08 mark(U11(x0, x1)) 4.93/2.08 mark(tt) 4.93/2.08 mark(U21(x0, x1, x2)) 4.93/2.08 mark(s(x0)) 4.93/2.08 mark(plus(x0, x1)) 4.93/2.08 mark(and(x0, x1)) 4.93/2.08 mark(isNat(x0)) 4.93/2.08 mark(0) 4.93/2.08 U11(mark(x0), x1) 4.93/2.08 U11(x0, mark(x1)) 4.93/2.08 U11(active(x0), x1) 4.93/2.08 U11(x0, active(x1)) 4.93/2.08 U21(mark(x0), x1, x2) 4.93/2.08 U21(x0, mark(x1), x2) 4.93/2.08 U21(x0, x1, mark(x2)) 4.93/2.08 U21(active(x0), x1, x2) 4.93/2.08 U21(x0, active(x1), x2) 4.93/2.08 U21(x0, x1, active(x2)) 4.93/2.08 s(mark(x0)) 4.93/2.08 s(active(x0)) 4.93/2.08 plus(mark(x0), x1) 4.93/2.08 plus(x0, mark(x1)) 4.93/2.08 plus(active(x0), x1) 4.93/2.08 plus(x0, active(x1)) 4.93/2.08 and(mark(x0), x1) 4.93/2.08 and(x0, mark(x1)) 4.93/2.08 and(active(x0), x1) 4.93/2.08 and(x0, active(x1)) 4.93/2.08 isNat(mark(x0)) 4.93/2.08 isNat(active(x0)) 4.93/2.08 4.93/2.08 4.93/2.08 ---------------------------------------- 4.93/2.08 4.93/2.08 (7) RisEmptyProof (EQUIVALENT) 4.93/2.08 The TRS R is empty. Hence, termination is trivially proven. 4.93/2.08 ---------------------------------------- 4.93/2.08 4.93/2.08 (8) 4.93/2.08 YES 5.11/2.11 EOF