5.06/2.19 YES 5.06/2.20 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.06/2.20 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.06/2.20 5.06/2.20 5.06/2.20 Termination w.r.t. Q of the given QTRS could be proven: 5.06/2.20 5.06/2.20 (0) QTRS 5.06/2.20 (1) QTRSRRRProof [EQUIVALENT, 70 ms] 5.06/2.20 (2) QTRS 5.06/2.20 (3) QTRSRRRProof [EQUIVALENT, 21 ms] 5.06/2.20 (4) QTRS 5.06/2.20 (5) QTRSRRRProof [EQUIVALENT, 15 ms] 5.06/2.20 (6) QTRS 5.06/2.20 (7) QTRSRRRProof [EQUIVALENT, 0 ms] 5.06/2.20 (8) QTRS 5.06/2.20 (9) QTRSRRRProof [EQUIVALENT, 10 ms] 5.06/2.20 (10) QTRS 5.06/2.20 (11) QTRSRRRProof [EQUIVALENT, 0 ms] 5.06/2.20 (12) QTRS 5.06/2.20 (13) QTRSRRRProof [EQUIVALENT, 7 ms] 5.06/2.20 (14) QTRS 5.06/2.20 (15) QTRSRRRProof [EQUIVALENT, 9 ms] 5.06/2.20 (16) QTRS 5.06/2.20 (17) QTRSRRRProof [EQUIVALENT, 0 ms] 5.06/2.20 (18) QTRS 5.06/2.20 (19) RisEmptyProof [EQUIVALENT, 0 ms] 5.06/2.20 (20) YES 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (0) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 The TRS R consists of the following rules: 5.06/2.20 5.06/2.20 a__nats -> a__adx(a__zeros) 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__incr(cons(X, Y)) -> cons(s(X), incr(Y)) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 a__hd(cons(X, Y)) -> mark(X) 5.06/2.20 a__tl(cons(X, Y)) -> mark(Y) 5.06/2.20 mark(nats) -> a__nats 5.06/2.20 mark(adx(X)) -> a__adx(mark(X)) 5.06/2.20 mark(zeros) -> a__zeros 5.06/2.20 mark(incr(X)) -> a__incr(mark(X)) 5.06/2.20 mark(hd(X)) -> a__hd(mark(X)) 5.06/2.20 mark(tl(X)) -> a__tl(mark(X)) 5.06/2.20 mark(cons(X1, X2)) -> cons(X1, X2) 5.06/2.20 mark(0) -> 0 5.06/2.20 mark(s(X)) -> s(X) 5.06/2.20 a__nats -> nats 5.06/2.20 a__adx(X) -> adx(X) 5.06/2.20 a__zeros -> zeros 5.06/2.20 a__incr(X) -> incr(X) 5.06/2.20 a__hd(X) -> hd(X) 5.06/2.20 a__tl(X) -> tl(X) 5.06/2.20 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (1) QTRSRRRProof (EQUIVALENT) 5.06/2.20 Used ordering: 5.06/2.20 Polynomial interpretation [POLO]: 5.06/2.20 5.06/2.20 POL(0) = 0 5.06/2.20 POL(a__adx(x_1)) = x_1 5.06/2.20 POL(a__hd(x_1)) = 1 + 2*x_1 5.06/2.20 POL(a__incr(x_1)) = x_1 5.06/2.20 POL(a__nats) = 0 5.06/2.20 POL(a__tl(x_1)) = 1 + 2*x_1 5.06/2.20 POL(a__zeros) = 0 5.06/2.20 POL(adx(x_1)) = x_1 5.06/2.20 POL(cons(x_1, x_2)) = x_1 + 2*x_2 5.06/2.20 POL(hd(x_1)) = 1 + 2*x_1 5.06/2.20 POL(incr(x_1)) = x_1 5.06/2.20 POL(mark(x_1)) = 2*x_1 5.06/2.20 POL(nats) = 0 5.06/2.20 POL(s(x_1)) = x_1 5.06/2.20 POL(tl(x_1)) = 1 + 2*x_1 5.06/2.20 POL(zeros) = 0 5.06/2.20 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.06/2.20 5.06/2.20 a__hd(cons(X, Y)) -> mark(X) 5.06/2.20 a__tl(cons(X, Y)) -> mark(Y) 5.06/2.20 mark(hd(X)) -> a__hd(mark(X)) 5.06/2.20 mark(tl(X)) -> a__tl(mark(X)) 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (2) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 The TRS R consists of the following rules: 5.06/2.20 5.06/2.20 a__nats -> a__adx(a__zeros) 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__incr(cons(X, Y)) -> cons(s(X), incr(Y)) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 mark(nats) -> a__nats 5.06/2.20 mark(adx(X)) -> a__adx(mark(X)) 5.06/2.20 mark(zeros) -> a__zeros 5.06/2.20 mark(incr(X)) -> a__incr(mark(X)) 5.06/2.20 mark(cons(X1, X2)) -> cons(X1, X2) 5.06/2.20 mark(0) -> 0 5.06/2.20 mark(s(X)) -> s(X) 5.06/2.20 a__nats -> nats 5.06/2.20 a__adx(X) -> adx(X) 5.06/2.20 a__zeros -> zeros 5.06/2.20 a__incr(X) -> incr(X) 5.06/2.20 a__hd(X) -> hd(X) 5.06/2.20 a__tl(X) -> tl(X) 5.06/2.20 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (3) QTRSRRRProof (EQUIVALENT) 5.06/2.20 Used ordering: 5.06/2.20 Polynomial interpretation [POLO]: 5.06/2.20 5.06/2.20 POL(0) = 0 5.06/2.20 POL(a__adx(x_1)) = x_1 5.06/2.20 POL(a__hd(x_1)) = 2 + 2*x_1 5.06/2.20 POL(a__incr(x_1)) = x_1 5.06/2.20 POL(a__nats) = 0 5.06/2.20 POL(a__tl(x_1)) = 1 + 2*x_1 5.06/2.20 POL(a__zeros) = 0 5.06/2.20 POL(adx(x_1)) = x_1 5.06/2.20 POL(cons(x_1, x_2)) = x_1 + x_2 5.06/2.20 POL(hd(x_1)) = 2 + 2*x_1 5.06/2.20 POL(incr(x_1)) = x_1 5.06/2.20 POL(mark(x_1)) = 2*x_1 5.06/2.20 POL(nats) = 0 5.06/2.20 POL(s(x_1)) = x_1 5.06/2.20 POL(tl(x_1)) = 2*x_1 5.06/2.20 POL(zeros) = 0 5.06/2.20 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.06/2.20 5.06/2.20 a__tl(X) -> tl(X) 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (4) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 The TRS R consists of the following rules: 5.06/2.20 5.06/2.20 a__nats -> a__adx(a__zeros) 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__incr(cons(X, Y)) -> cons(s(X), incr(Y)) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 mark(nats) -> a__nats 5.06/2.20 mark(adx(X)) -> a__adx(mark(X)) 5.06/2.20 mark(zeros) -> a__zeros 5.06/2.20 mark(incr(X)) -> a__incr(mark(X)) 5.06/2.20 mark(cons(X1, X2)) -> cons(X1, X2) 5.06/2.20 mark(0) -> 0 5.06/2.20 mark(s(X)) -> s(X) 5.06/2.20 a__nats -> nats 5.06/2.20 a__adx(X) -> adx(X) 5.06/2.20 a__zeros -> zeros 5.06/2.20 a__incr(X) -> incr(X) 5.06/2.20 a__hd(X) -> hd(X) 5.06/2.20 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (5) QTRSRRRProof (EQUIVALENT) 5.06/2.20 Used ordering: 5.06/2.20 Polynomial interpretation [POLO]: 5.06/2.20 5.06/2.20 POL(0) = 0 5.06/2.20 POL(a__adx(x_1)) = x_1 5.06/2.20 POL(a__hd(x_1)) = 1 + x_1 5.06/2.20 POL(a__incr(x_1)) = x_1 5.06/2.20 POL(a__nats) = 0 5.06/2.20 POL(a__zeros) = 0 5.06/2.20 POL(adx(x_1)) = x_1 5.06/2.20 POL(cons(x_1, x_2)) = x_1 + x_2 5.06/2.20 POL(hd(x_1)) = x_1 5.06/2.20 POL(incr(x_1)) = x_1 5.06/2.20 POL(mark(x_1)) = 2*x_1 5.06/2.20 POL(nats) = 0 5.06/2.20 POL(s(x_1)) = x_1 5.06/2.20 POL(zeros) = 0 5.06/2.20 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.06/2.20 5.06/2.20 a__hd(X) -> hd(X) 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (6) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 The TRS R consists of the following rules: 5.06/2.20 5.06/2.20 a__nats -> a__adx(a__zeros) 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__incr(cons(X, Y)) -> cons(s(X), incr(Y)) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 mark(nats) -> a__nats 5.06/2.20 mark(adx(X)) -> a__adx(mark(X)) 5.06/2.20 mark(zeros) -> a__zeros 5.06/2.20 mark(incr(X)) -> a__incr(mark(X)) 5.06/2.20 mark(cons(X1, X2)) -> cons(X1, X2) 5.06/2.20 mark(0) -> 0 5.06/2.20 mark(s(X)) -> s(X) 5.06/2.20 a__nats -> nats 5.06/2.20 a__adx(X) -> adx(X) 5.06/2.20 a__zeros -> zeros 5.06/2.20 a__incr(X) -> incr(X) 5.06/2.20 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (7) QTRSRRRProof (EQUIVALENT) 5.06/2.20 Used ordering: 5.06/2.20 Polynomial interpretation [POLO]: 5.06/2.20 5.06/2.20 POL(0) = 0 5.06/2.20 POL(a__adx(x_1)) = x_1 5.06/2.20 POL(a__incr(x_1)) = x_1 5.06/2.20 POL(a__nats) = 1 5.06/2.20 POL(a__zeros) = 0 5.06/2.20 POL(adx(x_1)) = x_1 5.06/2.20 POL(cons(x_1, x_2)) = x_1 + 2*x_2 5.06/2.20 POL(incr(x_1)) = x_1 5.06/2.20 POL(mark(x_1)) = 2*x_1 5.06/2.20 POL(nats) = 1 5.06/2.20 POL(s(x_1)) = x_1 5.06/2.20 POL(zeros) = 0 5.06/2.20 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.06/2.20 5.06/2.20 a__nats -> a__adx(a__zeros) 5.06/2.20 mark(nats) -> a__nats 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (8) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 The TRS R consists of the following rules: 5.06/2.20 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__incr(cons(X, Y)) -> cons(s(X), incr(Y)) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 mark(adx(X)) -> a__adx(mark(X)) 5.06/2.20 mark(zeros) -> a__zeros 5.06/2.20 mark(incr(X)) -> a__incr(mark(X)) 5.06/2.20 mark(cons(X1, X2)) -> cons(X1, X2) 5.06/2.20 mark(0) -> 0 5.06/2.20 mark(s(X)) -> s(X) 5.06/2.20 a__nats -> nats 5.06/2.20 a__adx(X) -> adx(X) 5.06/2.20 a__zeros -> zeros 5.06/2.20 a__incr(X) -> incr(X) 5.06/2.20 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (9) QTRSRRRProof (EQUIVALENT) 5.06/2.20 Used ordering: 5.06/2.20 Polynomial interpretation [POLO]: 5.06/2.20 5.06/2.20 POL(0) = 0 5.06/2.20 POL(a__adx(x_1)) = x_1 5.06/2.20 POL(a__incr(x_1)) = x_1 5.06/2.20 POL(a__nats) = 1 5.06/2.20 POL(a__zeros) = 0 5.06/2.20 POL(adx(x_1)) = x_1 5.06/2.20 POL(cons(x_1, x_2)) = 2*x_1 + x_2 5.06/2.20 POL(incr(x_1)) = x_1 5.06/2.20 POL(mark(x_1)) = x_1 5.06/2.20 POL(nats) = 0 5.06/2.20 POL(s(x_1)) = x_1 5.06/2.20 POL(zeros) = 0 5.06/2.20 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.06/2.20 5.06/2.20 a__nats -> nats 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (10) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 The TRS R consists of the following rules: 5.06/2.20 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__incr(cons(X, Y)) -> cons(s(X), incr(Y)) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 mark(adx(X)) -> a__adx(mark(X)) 5.06/2.20 mark(zeros) -> a__zeros 5.06/2.20 mark(incr(X)) -> a__incr(mark(X)) 5.06/2.20 mark(cons(X1, X2)) -> cons(X1, X2) 5.06/2.20 mark(0) -> 0 5.06/2.20 mark(s(X)) -> s(X) 5.06/2.20 a__adx(X) -> adx(X) 5.06/2.20 a__zeros -> zeros 5.06/2.20 a__incr(X) -> incr(X) 5.06/2.20 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (11) QTRSRRRProof (EQUIVALENT) 5.06/2.20 Used ordering: 5.06/2.20 Polynomial interpretation [POLO]: 5.06/2.20 5.06/2.20 POL(0) = 0 5.06/2.20 POL(a__adx(x_1)) = 2 + 2*x_1 5.06/2.20 POL(a__incr(x_1)) = 2 + x_1 5.06/2.20 POL(a__zeros) = 2 5.06/2.20 POL(adx(x_1)) = 1 + 2*x_1 5.06/2.20 POL(cons(x_1, x_2)) = 1 + 2*x_1 + x_2 5.06/2.20 POL(incr(x_1)) = 1 + x_1 5.06/2.20 POL(mark(x_1)) = 2*x_1 5.06/2.20 POL(s(x_1)) = x_1 5.06/2.20 POL(zeros) = 1 5.06/2.20 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.06/2.20 5.06/2.20 a__incr(cons(X, Y)) -> cons(s(X), incr(Y)) 5.06/2.20 mark(cons(X1, X2)) -> cons(X1, X2) 5.06/2.20 a__adx(X) -> adx(X) 5.06/2.20 a__zeros -> zeros 5.06/2.20 a__incr(X) -> incr(X) 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (12) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 The TRS R consists of the following rules: 5.06/2.20 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 mark(adx(X)) -> a__adx(mark(X)) 5.06/2.20 mark(zeros) -> a__zeros 5.06/2.20 mark(incr(X)) -> a__incr(mark(X)) 5.06/2.20 mark(0) -> 0 5.06/2.20 mark(s(X)) -> s(X) 5.06/2.20 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (13) QTRSRRRProof (EQUIVALENT) 5.06/2.20 Used ordering: 5.06/2.20 Polynomial interpretation [POLO]: 5.06/2.20 5.06/2.20 POL(0) = 0 5.06/2.20 POL(a__adx(x_1)) = 2 + x_1 5.06/2.20 POL(a__incr(x_1)) = 1 + x_1 5.06/2.20 POL(a__zeros) = 1 5.06/2.20 POL(adx(x_1)) = 1 + x_1 5.06/2.20 POL(cons(x_1, x_2)) = 2*x_1 + x_2 5.06/2.20 POL(incr(x_1)) = 2 + 2*x_1 5.06/2.20 POL(mark(x_1)) = 2*x_1 5.06/2.20 POL(s(x_1)) = 1 + 2*x_1 5.06/2.20 POL(zeros) = 1 5.06/2.20 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.06/2.20 5.06/2.20 mark(zeros) -> a__zeros 5.06/2.20 mark(incr(X)) -> a__incr(mark(X)) 5.06/2.20 mark(s(X)) -> s(X) 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (14) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 The TRS R consists of the following rules: 5.06/2.20 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 mark(adx(X)) -> a__adx(mark(X)) 5.06/2.20 mark(0) -> 0 5.06/2.20 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (15) QTRSRRRProof (EQUIVALENT) 5.06/2.20 Used ordering: 5.06/2.20 Polynomial interpretation [POLO]: 5.06/2.20 5.06/2.20 POL(0) = 0 5.06/2.20 POL(a__adx(x_1)) = 2*x_1 5.06/2.20 POL(a__incr(x_1)) = x_1 5.06/2.20 POL(a__zeros) = 2 5.06/2.20 POL(adx(x_1)) = 2 + 2*x_1 5.06/2.20 POL(cons(x_1, x_2)) = 2 + 2*x_1 + x_2 5.06/2.20 POL(mark(x_1)) = 1 + 2*x_1 5.06/2.20 POL(zeros) = 0 5.06/2.20 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.06/2.20 5.06/2.20 mark(adx(X)) -> a__adx(mark(X)) 5.06/2.20 mark(0) -> 0 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (16) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 The TRS R consists of the following rules: 5.06/2.20 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (17) QTRSRRRProof (EQUIVALENT) 5.06/2.20 Used ordering: 5.06/2.20 Knuth-Bendix order [KBO] with precedence:adx_1 > a__adx_1 > a__incr_1 > zeros > 0 > a__zeros > cons_2 5.06/2.20 5.06/2.20 and weight map: 5.06/2.20 5.06/2.20 a__zeros=2 5.06/2.20 0=1 5.06/2.20 zeros=1 5.06/2.20 a__adx_1=2 5.06/2.20 a__incr_1=1 5.06/2.20 adx_1=1 5.06/2.20 cons_2=0 5.06/2.20 5.06/2.20 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.06/2.20 5.06/2.20 a__zeros -> cons(0, zeros) 5.06/2.20 a__adx(cons(X, Y)) -> a__incr(cons(X, adx(Y))) 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (18) 5.06/2.20 Obligation: 5.06/2.20 Q restricted rewrite system: 5.06/2.20 R is empty. 5.06/2.20 The set Q consists of the following terms: 5.06/2.20 5.06/2.20 a__nats 5.06/2.20 a__zeros 5.06/2.20 mark(nats) 5.06/2.20 mark(adx(x0)) 5.06/2.20 mark(zeros) 5.06/2.20 mark(incr(x0)) 5.06/2.20 mark(hd(x0)) 5.06/2.20 mark(tl(x0)) 5.06/2.20 mark(cons(x0, x1)) 5.06/2.20 mark(0) 5.06/2.20 mark(s(x0)) 5.06/2.20 a__adx(x0) 5.06/2.20 a__incr(x0) 5.06/2.20 a__hd(x0) 5.06/2.20 a__tl(x0) 5.06/2.20 5.06/2.20 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (19) RisEmptyProof (EQUIVALENT) 5.06/2.20 The TRS R is empty. Hence, termination is trivially proven. 5.06/2.20 ---------------------------------------- 5.06/2.20 5.06/2.20 (20) 5.06/2.20 YES 5.06/2.22 EOF