4.63/2.00 YES 4.63/2.02 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.63/2.02 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.63/2.02 4.63/2.02 4.63/2.02 Termination w.r.t. Q of the given QTRS could be proven: 4.63/2.02 4.63/2.02 (0) QTRS 4.63/2.02 (1) QTRSRRRProof [EQUIVALENT, 134 ms] 4.63/2.02 (2) QTRS 4.63/2.02 (3) QTRSRRRProof [EQUIVALENT, 18 ms] 4.63/2.02 (4) QTRS 4.63/2.02 (5) QTRSRRRProof [EQUIVALENT, 17 ms] 4.63/2.02 (6) QTRS 4.63/2.02 (7) QTRSRRRProof [EQUIVALENT, 0 ms] 4.63/2.02 (8) QTRS 4.63/2.02 (9) QTRSRRRProof [EQUIVALENT, 0 ms] 4.63/2.02 (10) QTRS 4.63/2.02 (11) RisEmptyProof [EQUIVALENT, 0 ms] 4.63/2.02 (12) YES 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (0) 4.63/2.02 Obligation: 4.63/2.02 Q restricted rewrite system: 4.63/2.02 The TRS R consists of the following rules: 4.63/2.02 4.63/2.02 active(and(tt, X)) -> mark(X) 4.63/2.02 active(plus(N, 0)) -> mark(N) 4.63/2.02 active(plus(N, s(M))) -> mark(s(plus(N, M))) 4.63/2.02 active(x(N, 0)) -> mark(0) 4.63/2.02 active(x(N, s(M))) -> mark(plus(x(N, M), N)) 4.63/2.02 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 4.63/2.02 mark(tt) -> active(tt) 4.63/2.02 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 4.63/2.02 mark(0) -> active(0) 4.63/2.02 mark(s(X)) -> active(s(mark(X))) 4.63/2.02 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 4.63/2.02 and(mark(X1), X2) -> and(X1, X2) 4.63/2.02 and(X1, mark(X2)) -> and(X1, X2) 4.63/2.02 and(active(X1), X2) -> and(X1, X2) 4.63/2.02 and(X1, active(X2)) -> and(X1, X2) 4.63/2.02 plus(mark(X1), X2) -> plus(X1, X2) 4.63/2.02 plus(X1, mark(X2)) -> plus(X1, X2) 4.63/2.02 plus(active(X1), X2) -> plus(X1, X2) 4.63/2.02 plus(X1, active(X2)) -> plus(X1, X2) 4.63/2.02 s(mark(X)) -> s(X) 4.63/2.02 s(active(X)) -> s(X) 4.63/2.02 x(mark(X1), X2) -> x(X1, X2) 4.63/2.02 x(X1, mark(X2)) -> x(X1, X2) 4.63/2.02 x(active(X1), X2) -> x(X1, X2) 4.63/2.02 x(X1, active(X2)) -> x(X1, X2) 4.63/2.02 4.63/2.02 The set Q consists of the following terms: 4.63/2.02 4.63/2.02 active(and(tt, x0)) 4.63/2.02 active(plus(x0, 0)) 4.63/2.02 active(plus(x0, s(x1))) 4.63/2.02 active(x(x0, 0)) 4.63/2.02 active(x(x0, s(x1))) 4.63/2.02 mark(and(x0, x1)) 4.63/2.02 mark(tt) 4.63/2.02 mark(plus(x0, x1)) 4.63/2.02 mark(0) 4.63/2.02 mark(s(x0)) 4.63/2.02 mark(x(x0, x1)) 4.63/2.02 and(mark(x0), x1) 4.63/2.02 and(x0, mark(x1)) 4.63/2.02 and(active(x0), x1) 4.63/2.02 and(x0, active(x1)) 4.63/2.02 plus(mark(x0), x1) 4.63/2.02 plus(x0, mark(x1)) 4.63/2.02 plus(active(x0), x1) 4.63/2.02 plus(x0, active(x1)) 4.63/2.02 s(mark(x0)) 4.63/2.02 s(active(x0)) 4.63/2.02 x(mark(x0), x1) 4.63/2.02 x(x0, mark(x1)) 4.63/2.02 x(active(x0), x1) 4.63/2.02 x(x0, active(x1)) 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (1) QTRSRRRProof (EQUIVALENT) 4.63/2.02 Used ordering: 4.63/2.02 active/1)YES( 4.63/2.02 and/2(YES,YES) 4.63/2.02 tt/0) 4.63/2.02 mark/1)YES( 4.63/2.02 plus/2(YES,YES) 4.63/2.02 0/0) 4.63/2.02 s/1(YES) 4.63/2.02 x/2(YES,YES) 4.63/2.02 4.63/2.02 Quasi precedence: 4.63/2.02 [0, x_2] > plus_2 > s_1 4.63/2.02 4.63/2.02 4.63/2.02 Status: 4.63/2.02 and_2: multiset status 4.63/2.02 tt: multiset status 4.63/2.02 plus_2: multiset status 4.63/2.02 0: multiset status 4.63/2.02 s_1: multiset status 4.63/2.02 x_2: multiset status 4.63/2.02 4.63/2.02 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.63/2.02 4.63/2.02 active(and(tt, X)) -> mark(X) 4.63/2.02 active(plus(N, 0)) -> mark(N) 4.63/2.02 active(plus(N, s(M))) -> mark(s(plus(N, M))) 4.63/2.02 active(x(N, 0)) -> mark(0) 4.63/2.02 active(x(N, s(M))) -> mark(plus(x(N, M), N)) 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (2) 4.63/2.02 Obligation: 4.63/2.02 Q restricted rewrite system: 4.63/2.02 The TRS R consists of the following rules: 4.63/2.02 4.63/2.02 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 4.63/2.02 mark(tt) -> active(tt) 4.63/2.02 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 4.63/2.02 mark(0) -> active(0) 4.63/2.02 mark(s(X)) -> active(s(mark(X))) 4.63/2.02 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 4.63/2.02 and(mark(X1), X2) -> and(X1, X2) 4.63/2.02 and(X1, mark(X2)) -> and(X1, X2) 4.63/2.02 and(active(X1), X2) -> and(X1, X2) 4.63/2.02 and(X1, active(X2)) -> and(X1, X2) 4.63/2.02 plus(mark(X1), X2) -> plus(X1, X2) 4.63/2.02 plus(X1, mark(X2)) -> plus(X1, X2) 4.63/2.02 plus(active(X1), X2) -> plus(X1, X2) 4.63/2.02 plus(X1, active(X2)) -> plus(X1, X2) 4.63/2.02 s(mark(X)) -> s(X) 4.63/2.02 s(active(X)) -> s(X) 4.63/2.02 x(mark(X1), X2) -> x(X1, X2) 4.63/2.02 x(X1, mark(X2)) -> x(X1, X2) 4.63/2.02 x(active(X1), X2) -> x(X1, X2) 4.63/2.02 x(X1, active(X2)) -> x(X1, X2) 4.63/2.02 4.63/2.02 The set Q consists of the following terms: 4.63/2.02 4.63/2.02 active(and(tt, x0)) 4.63/2.02 active(plus(x0, 0)) 4.63/2.02 active(plus(x0, s(x1))) 4.63/2.02 active(x(x0, 0)) 4.63/2.02 active(x(x0, s(x1))) 4.63/2.02 mark(and(x0, x1)) 4.63/2.02 mark(tt) 4.63/2.02 mark(plus(x0, x1)) 4.63/2.02 mark(0) 4.63/2.02 mark(s(x0)) 4.63/2.02 mark(x(x0, x1)) 4.63/2.02 and(mark(x0), x1) 4.63/2.02 and(x0, mark(x1)) 4.63/2.02 and(active(x0), x1) 4.63/2.02 and(x0, active(x1)) 4.63/2.02 plus(mark(x0), x1) 4.63/2.02 plus(x0, mark(x1)) 4.63/2.02 plus(active(x0), x1) 4.63/2.02 plus(x0, active(x1)) 4.63/2.02 s(mark(x0)) 4.63/2.02 s(active(x0)) 4.63/2.02 x(mark(x0), x1) 4.63/2.02 x(x0, mark(x1)) 4.63/2.02 x(active(x0), x1) 4.63/2.02 x(x0, active(x1)) 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (3) QTRSRRRProof (EQUIVALENT) 4.63/2.02 Used ordering: 4.63/2.02 Polynomial interpretation [POLO]: 4.63/2.02 4.63/2.02 POL(0) = 2 4.63/2.02 POL(active(x_1)) = 2 + x_1 4.63/2.02 POL(and(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 4.63/2.02 POL(mark(x_1)) = 2*x_1 4.63/2.02 POL(plus(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 4.63/2.02 POL(s(x_1)) = 2 + 2*x_1 4.63/2.02 POL(tt) = 2 4.63/2.02 POL(x(x_1, x_2)) = 2 + 2*x_1 + x_2 4.63/2.02 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.63/2.02 4.63/2.02 and(active(X1), X2) -> and(X1, X2) 4.63/2.02 and(X1, active(X2)) -> and(X1, X2) 4.63/2.02 plus(active(X1), X2) -> plus(X1, X2) 4.63/2.02 plus(X1, active(X2)) -> plus(X1, X2) 4.63/2.02 s(active(X)) -> s(X) 4.63/2.02 x(active(X1), X2) -> x(X1, X2) 4.63/2.02 x(X1, active(X2)) -> x(X1, X2) 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (4) 4.63/2.02 Obligation: 4.63/2.02 Q restricted rewrite system: 4.63/2.02 The TRS R consists of the following rules: 4.63/2.02 4.63/2.02 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 4.63/2.02 mark(tt) -> active(tt) 4.63/2.02 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 4.63/2.02 mark(0) -> active(0) 4.63/2.02 mark(s(X)) -> active(s(mark(X))) 4.63/2.02 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 4.63/2.02 and(mark(X1), X2) -> and(X1, X2) 4.63/2.02 and(X1, mark(X2)) -> and(X1, X2) 4.63/2.02 plus(mark(X1), X2) -> plus(X1, X2) 4.63/2.02 plus(X1, mark(X2)) -> plus(X1, X2) 4.63/2.02 s(mark(X)) -> s(X) 4.63/2.02 x(mark(X1), X2) -> x(X1, X2) 4.63/2.02 x(X1, mark(X2)) -> x(X1, X2) 4.63/2.02 4.63/2.02 The set Q consists of the following terms: 4.63/2.02 4.63/2.02 active(and(tt, x0)) 4.63/2.02 active(plus(x0, 0)) 4.63/2.02 active(plus(x0, s(x1))) 4.63/2.02 active(x(x0, 0)) 4.63/2.02 active(x(x0, s(x1))) 4.63/2.02 mark(and(x0, x1)) 4.63/2.02 mark(tt) 4.63/2.02 mark(plus(x0, x1)) 4.63/2.02 mark(0) 4.63/2.02 mark(s(x0)) 4.63/2.02 mark(x(x0, x1)) 4.63/2.02 and(mark(x0), x1) 4.63/2.02 and(x0, mark(x1)) 4.63/2.02 and(active(x0), x1) 4.63/2.02 and(x0, active(x1)) 4.63/2.02 plus(mark(x0), x1) 4.63/2.02 plus(x0, mark(x1)) 4.63/2.02 plus(active(x0), x1) 4.63/2.02 plus(x0, active(x1)) 4.63/2.02 s(mark(x0)) 4.63/2.02 s(active(x0)) 4.63/2.02 x(mark(x0), x1) 4.63/2.02 x(x0, mark(x1)) 4.63/2.02 x(active(x0), x1) 4.63/2.02 x(x0, active(x1)) 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (5) QTRSRRRProof (EQUIVALENT) 4.63/2.02 Used ordering: 4.63/2.02 Polynomial interpretation [POLO]: 4.63/2.02 4.63/2.02 POL(0) = 1 4.63/2.02 POL(active(x_1)) = x_1 4.63/2.02 POL(and(x_1, x_2)) = x_1 + x_2 4.63/2.02 POL(mark(x_1)) = 2*x_1 4.63/2.02 POL(plus(x_1, x_2)) = 1 + 2*x_1 + x_2 4.63/2.02 POL(s(x_1)) = 2*x_1 4.63/2.02 POL(tt) = 1 4.63/2.02 POL(x(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 4.63/2.02 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.63/2.02 4.63/2.02 mark(tt) -> active(tt) 4.63/2.02 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 4.63/2.02 mark(0) -> active(0) 4.63/2.02 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (6) 4.63/2.02 Obligation: 4.63/2.02 Q restricted rewrite system: 4.63/2.02 The TRS R consists of the following rules: 4.63/2.02 4.63/2.02 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 4.63/2.02 mark(s(X)) -> active(s(mark(X))) 4.63/2.02 and(mark(X1), X2) -> and(X1, X2) 4.63/2.02 and(X1, mark(X2)) -> and(X1, X2) 4.63/2.02 plus(mark(X1), X2) -> plus(X1, X2) 4.63/2.02 plus(X1, mark(X2)) -> plus(X1, X2) 4.63/2.02 s(mark(X)) -> s(X) 4.63/2.02 x(mark(X1), X2) -> x(X1, X2) 4.63/2.02 x(X1, mark(X2)) -> x(X1, X2) 4.63/2.02 4.63/2.02 The set Q consists of the following terms: 4.63/2.02 4.63/2.02 active(and(tt, x0)) 4.63/2.02 active(plus(x0, 0)) 4.63/2.02 active(plus(x0, s(x1))) 4.63/2.02 active(x(x0, 0)) 4.63/2.02 active(x(x0, s(x1))) 4.63/2.02 mark(and(x0, x1)) 4.63/2.02 mark(tt) 4.63/2.02 mark(plus(x0, x1)) 4.63/2.02 mark(0) 4.63/2.02 mark(s(x0)) 4.63/2.02 mark(x(x0, x1)) 4.63/2.02 and(mark(x0), x1) 4.63/2.02 and(x0, mark(x1)) 4.63/2.02 and(active(x0), x1) 4.63/2.02 and(x0, active(x1)) 4.63/2.02 plus(mark(x0), x1) 4.63/2.02 plus(x0, mark(x1)) 4.63/2.02 plus(active(x0), x1) 4.63/2.02 plus(x0, active(x1)) 4.63/2.02 s(mark(x0)) 4.63/2.02 s(active(x0)) 4.63/2.02 x(mark(x0), x1) 4.63/2.02 x(x0, mark(x1)) 4.63/2.02 x(active(x0), x1) 4.63/2.02 x(x0, active(x1)) 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (7) QTRSRRRProof (EQUIVALENT) 4.63/2.02 Used ordering: 4.63/2.02 Polynomial interpretation [POLO]: 4.63/2.02 4.63/2.02 POL(active(x_1)) = 1 + x_1 4.63/2.02 POL(and(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 4.63/2.02 POL(mark(x_1)) = 2*x_1 4.63/2.02 POL(plus(x_1, x_2)) = x_1 + x_2 4.63/2.02 POL(s(x_1)) = 2 + 2*x_1 4.63/2.02 POL(x(x_1, x_2)) = x_1 + 2*x_2 4.63/2.02 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.63/2.02 4.63/2.02 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 4.63/2.02 mark(s(X)) -> active(s(mark(X))) 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (8) 4.63/2.02 Obligation: 4.63/2.02 Q restricted rewrite system: 4.63/2.02 The TRS R consists of the following rules: 4.63/2.02 4.63/2.02 and(mark(X1), X2) -> and(X1, X2) 4.63/2.02 and(X1, mark(X2)) -> and(X1, X2) 4.63/2.02 plus(mark(X1), X2) -> plus(X1, X2) 4.63/2.02 plus(X1, mark(X2)) -> plus(X1, X2) 4.63/2.02 s(mark(X)) -> s(X) 4.63/2.02 x(mark(X1), X2) -> x(X1, X2) 4.63/2.02 x(X1, mark(X2)) -> x(X1, X2) 4.63/2.02 4.63/2.02 The set Q consists of the following terms: 4.63/2.02 4.63/2.02 active(and(tt, x0)) 4.63/2.02 active(plus(x0, 0)) 4.63/2.02 active(plus(x0, s(x1))) 4.63/2.02 active(x(x0, 0)) 4.63/2.02 active(x(x0, s(x1))) 4.63/2.02 mark(and(x0, x1)) 4.63/2.02 mark(tt) 4.63/2.02 mark(plus(x0, x1)) 4.63/2.02 mark(0) 4.63/2.02 mark(s(x0)) 4.63/2.02 mark(x(x0, x1)) 4.63/2.02 and(mark(x0), x1) 4.63/2.02 and(x0, mark(x1)) 4.63/2.02 and(active(x0), x1) 4.63/2.02 and(x0, active(x1)) 4.63/2.02 plus(mark(x0), x1) 4.63/2.02 plus(x0, mark(x1)) 4.63/2.02 plus(active(x0), x1) 4.63/2.02 plus(x0, active(x1)) 4.63/2.02 s(mark(x0)) 4.63/2.02 s(active(x0)) 4.63/2.02 x(mark(x0), x1) 4.63/2.02 x(x0, mark(x1)) 4.63/2.02 x(active(x0), x1) 4.63/2.02 x(x0, active(x1)) 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (9) QTRSRRRProof (EQUIVALENT) 4.63/2.02 Used ordering: 4.63/2.02 Knuth-Bendix order [KBO] with precedence:mark_1 > x_2 > s_1 > plus_2 > and_2 4.63/2.02 4.63/2.02 and weight map: 4.63/2.02 4.63/2.02 mark_1=0 4.63/2.02 s_1=1 4.63/2.02 and_2=0 4.63/2.02 plus_2=0 4.63/2.02 x_2=0 4.63/2.02 4.63/2.02 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.63/2.02 4.63/2.02 and(mark(X1), X2) -> and(X1, X2) 4.63/2.02 and(X1, mark(X2)) -> and(X1, X2) 4.63/2.02 plus(mark(X1), X2) -> plus(X1, X2) 4.63/2.02 plus(X1, mark(X2)) -> plus(X1, X2) 4.63/2.02 s(mark(X)) -> s(X) 4.63/2.02 x(mark(X1), X2) -> x(X1, X2) 4.63/2.02 x(X1, mark(X2)) -> x(X1, X2) 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (10) 4.63/2.02 Obligation: 4.63/2.02 Q restricted rewrite system: 4.63/2.02 R is empty. 4.63/2.02 The set Q consists of the following terms: 4.63/2.02 4.63/2.02 active(and(tt, x0)) 4.63/2.02 active(plus(x0, 0)) 4.63/2.02 active(plus(x0, s(x1))) 4.63/2.02 active(x(x0, 0)) 4.63/2.02 active(x(x0, s(x1))) 4.63/2.02 mark(and(x0, x1)) 4.63/2.02 mark(tt) 4.63/2.02 mark(plus(x0, x1)) 4.63/2.02 mark(0) 4.63/2.02 mark(s(x0)) 4.63/2.02 mark(x(x0, x1)) 4.63/2.02 and(mark(x0), x1) 4.63/2.02 and(x0, mark(x1)) 4.63/2.02 and(active(x0), x1) 4.63/2.02 and(x0, active(x1)) 4.63/2.02 plus(mark(x0), x1) 4.63/2.02 plus(x0, mark(x1)) 4.63/2.02 plus(active(x0), x1) 4.63/2.02 plus(x0, active(x1)) 4.63/2.02 s(mark(x0)) 4.63/2.02 s(active(x0)) 4.63/2.02 x(mark(x0), x1) 4.63/2.02 x(x0, mark(x1)) 4.63/2.02 x(active(x0), x1) 4.63/2.02 x(x0, active(x1)) 4.63/2.02 4.63/2.02 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (11) RisEmptyProof (EQUIVALENT) 4.63/2.02 The TRS R is empty. Hence, termination is trivially proven. 4.63/2.02 ---------------------------------------- 4.63/2.02 4.63/2.02 (12) 4.63/2.02 YES 4.86/2.12 EOF