6.71/2.70 YES 6.96/2.71 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 6.96/2.71 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.96/2.71 6.96/2.71 6.96/2.71 Termination w.r.t. Q of the given QTRS could be proven: 6.96/2.71 6.96/2.71 (0) QTRS 6.96/2.71 (1) QTRSRRRProof [EQUIVALENT, 66 ms] 6.96/2.71 (2) QTRS 6.96/2.71 (3) QTRSRRRProof [EQUIVALENT, 13 ms] 6.96/2.71 (4) QTRS 6.96/2.71 (5) QTRSRRRProof [EQUIVALENT, 16 ms] 6.96/2.71 (6) QTRS 6.96/2.71 (7) QTRSRRRProof [EQUIVALENT, 17 ms] 6.96/2.71 (8) QTRS 6.96/2.71 (9) DependencyPairsProof [EQUIVALENT, 0 ms] 6.96/2.71 (10) QDP 6.96/2.71 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 6.96/2.71 (12) QDP 6.96/2.71 (13) MRRProof [EQUIVALENT, 18 ms] 6.96/2.71 (14) QDP 6.96/2.71 (15) MRRProof [EQUIVALENT, 30 ms] 6.96/2.71 (16) QDP 6.96/2.71 (17) MRRProof [EQUIVALENT, 0 ms] 6.96/2.71 (18) QDP 6.96/2.71 (19) DependencyGraphProof [EQUIVALENT, 0 ms] 6.96/2.71 (20) QDP 6.96/2.71 (21) QDPOrderProof [EQUIVALENT, 36 ms] 6.96/2.71 (22) QDP 6.96/2.71 (23) PisEmptyProof [EQUIVALENT, 0 ms] 6.96/2.71 (24) YES 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (0) 6.96/2.71 Obligation: 6.96/2.71 Q restricted rewrite system: 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(nil) -> nil 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__nats -> a__adx(a__zeros) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 a__head(cons(X, L)) -> mark(X) 6.96/2.71 a__tail(cons(X, L)) -> mark(L) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.71 mark(nats) -> a__nats 6.96/2.71 mark(zeros) -> a__zeros 6.96/2.71 mark(head(X)) -> a__head(mark(X)) 6.96/2.71 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.71 mark(nil) -> nil 6.96/2.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.71 mark(s(X)) -> s(mark(X)) 6.96/2.71 mark(0) -> 0 6.96/2.71 a__incr(X) -> incr(X) 6.96/2.71 a__adx(X) -> adx(X) 6.96/2.71 a__nats -> nats 6.96/2.71 a__zeros -> zeros 6.96/2.71 a__head(X) -> head(X) 6.96/2.71 a__tail(X) -> tail(X) 6.96/2.71 6.96/2.71 The set Q consists of the following terms: 6.96/2.71 6.96/2.71 a__nats 6.96/2.71 a__zeros 6.96/2.71 mark(incr(x0)) 6.96/2.71 mark(adx(x0)) 6.96/2.71 mark(nats) 6.96/2.71 mark(zeros) 6.96/2.71 mark(head(x0)) 6.96/2.71 mark(tail(x0)) 6.96/2.71 mark(nil) 6.96/2.71 mark(cons(x0, x1)) 6.96/2.71 mark(s(x0)) 6.96/2.71 mark(0) 6.96/2.71 a__incr(x0) 6.96/2.71 a__adx(x0) 6.96/2.71 a__head(x0) 6.96/2.71 a__tail(x0) 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (1) QTRSRRRProof (EQUIVALENT) 6.96/2.71 Used ordering: 6.96/2.71 Polynomial interpretation [POLO]: 6.96/2.71 6.96/2.71 POL(0) = 0 6.96/2.71 POL(a__adx(x_1)) = x_1 6.96/2.71 POL(a__head(x_1)) = 2*x_1 6.96/2.71 POL(a__incr(x_1)) = x_1 6.96/2.71 POL(a__nats) = 1 6.96/2.71 POL(a__tail(x_1)) = 2*x_1 6.96/2.71 POL(a__zeros) = 0 6.96/2.71 POL(adx(x_1)) = x_1 6.96/2.71 POL(cons(x_1, x_2)) = x_1 + x_2 6.96/2.71 POL(head(x_1)) = 2*x_1 6.96/2.71 POL(incr(x_1)) = x_1 6.96/2.71 POL(mark(x_1)) = x_1 6.96/2.71 POL(nats) = 1 6.96/2.71 POL(nil) = 0 6.96/2.71 POL(s(x_1)) = x_1 6.96/2.71 POL(tail(x_1)) = 2*x_1 6.96/2.71 POL(zeros) = 0 6.96/2.71 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.96/2.71 6.96/2.71 a__nats -> a__adx(a__zeros) 6.96/2.71 6.96/2.71 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (2) 6.96/2.71 Obligation: 6.96/2.71 Q restricted rewrite system: 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(nil) -> nil 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 a__head(cons(X, L)) -> mark(X) 6.96/2.71 a__tail(cons(X, L)) -> mark(L) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.71 mark(nats) -> a__nats 6.96/2.71 mark(zeros) -> a__zeros 6.96/2.71 mark(head(X)) -> a__head(mark(X)) 6.96/2.71 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.71 mark(nil) -> nil 6.96/2.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.71 mark(s(X)) -> s(mark(X)) 6.96/2.71 mark(0) -> 0 6.96/2.71 a__incr(X) -> incr(X) 6.96/2.71 a__adx(X) -> adx(X) 6.96/2.71 a__nats -> nats 6.96/2.71 a__zeros -> zeros 6.96/2.71 a__head(X) -> head(X) 6.96/2.71 a__tail(X) -> tail(X) 6.96/2.71 6.96/2.71 The set Q consists of the following terms: 6.96/2.71 6.96/2.71 a__nats 6.96/2.71 a__zeros 6.96/2.71 mark(incr(x0)) 6.96/2.71 mark(adx(x0)) 6.96/2.71 mark(nats) 6.96/2.71 mark(zeros) 6.96/2.71 mark(head(x0)) 6.96/2.71 mark(tail(x0)) 6.96/2.71 mark(nil) 6.96/2.71 mark(cons(x0, x1)) 6.96/2.71 mark(s(x0)) 6.96/2.71 mark(0) 6.96/2.71 a__incr(x0) 6.96/2.71 a__adx(x0) 6.96/2.71 a__head(x0) 6.96/2.71 a__tail(x0) 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (3) QTRSRRRProof (EQUIVALENT) 6.96/2.71 Used ordering: 6.96/2.71 Polynomial interpretation [POLO]: 6.96/2.71 6.96/2.71 POL(0) = 0 6.96/2.71 POL(a__adx(x_1)) = x_1 6.96/2.71 POL(a__head(x_1)) = 1 + 2*x_1 6.96/2.71 POL(a__incr(x_1)) = x_1 6.96/2.71 POL(a__nats) = 0 6.96/2.71 POL(a__tail(x_1)) = 2*x_1 6.96/2.71 POL(a__zeros) = 0 6.96/2.71 POL(adx(x_1)) = x_1 6.96/2.71 POL(cons(x_1, x_2)) = x_1 + 2*x_2 6.96/2.71 POL(head(x_1)) = 1 + 2*x_1 6.96/2.71 POL(incr(x_1)) = x_1 6.96/2.71 POL(mark(x_1)) = x_1 6.96/2.71 POL(nats) = 0 6.96/2.71 POL(nil) = 0 6.96/2.71 POL(s(x_1)) = x_1 6.96/2.71 POL(tail(x_1)) = 2*x_1 6.96/2.71 POL(zeros) = 0 6.96/2.71 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.96/2.71 6.96/2.71 a__head(cons(X, L)) -> mark(X) 6.96/2.71 6.96/2.71 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (4) 6.96/2.71 Obligation: 6.96/2.71 Q restricted rewrite system: 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(nil) -> nil 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 a__tail(cons(X, L)) -> mark(L) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.71 mark(nats) -> a__nats 6.96/2.71 mark(zeros) -> a__zeros 6.96/2.71 mark(head(X)) -> a__head(mark(X)) 6.96/2.71 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.71 mark(nil) -> nil 6.96/2.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.71 mark(s(X)) -> s(mark(X)) 6.96/2.71 mark(0) -> 0 6.96/2.71 a__incr(X) -> incr(X) 6.96/2.71 a__adx(X) -> adx(X) 6.96/2.71 a__nats -> nats 6.96/2.71 a__zeros -> zeros 6.96/2.71 a__head(X) -> head(X) 6.96/2.71 a__tail(X) -> tail(X) 6.96/2.71 6.96/2.71 The set Q consists of the following terms: 6.96/2.71 6.96/2.71 a__nats 6.96/2.71 a__zeros 6.96/2.71 mark(incr(x0)) 6.96/2.71 mark(adx(x0)) 6.96/2.71 mark(nats) 6.96/2.71 mark(zeros) 6.96/2.71 mark(head(x0)) 6.96/2.71 mark(tail(x0)) 6.96/2.71 mark(nil) 6.96/2.71 mark(cons(x0, x1)) 6.96/2.71 mark(s(x0)) 6.96/2.71 mark(0) 6.96/2.71 a__incr(x0) 6.96/2.71 a__adx(x0) 6.96/2.71 a__head(x0) 6.96/2.71 a__tail(x0) 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (5) QTRSRRRProof (EQUIVALENT) 6.96/2.71 Used ordering: 6.96/2.71 Polynomial interpretation [POLO]: 6.96/2.71 6.96/2.71 POL(0) = 0 6.96/2.71 POL(a__adx(x_1)) = 1 + x_1 6.96/2.71 POL(a__head(x_1)) = 2*x_1 6.96/2.71 POL(a__incr(x_1)) = x_1 6.96/2.71 POL(a__nats) = 0 6.96/2.71 POL(a__tail(x_1)) = x_1 6.96/2.71 POL(a__zeros) = 0 6.96/2.71 POL(adx(x_1)) = 1 + x_1 6.96/2.71 POL(cons(x_1, x_2)) = x_1 + x_2 6.96/2.71 POL(head(x_1)) = 2*x_1 6.96/2.71 POL(incr(x_1)) = x_1 6.96/2.71 POL(mark(x_1)) = x_1 6.96/2.71 POL(nats) = 0 6.96/2.71 POL(nil) = 0 6.96/2.71 POL(s(x_1)) = x_1 6.96/2.71 POL(tail(x_1)) = x_1 6.96/2.71 POL(zeros) = 0 6.96/2.71 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.96/2.71 6.96/2.71 a__adx(nil) -> nil 6.96/2.71 6.96/2.71 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (6) 6.96/2.71 Obligation: 6.96/2.71 Q restricted rewrite system: 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 a__tail(cons(X, L)) -> mark(L) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.71 mark(nats) -> a__nats 6.96/2.71 mark(zeros) -> a__zeros 6.96/2.71 mark(head(X)) -> a__head(mark(X)) 6.96/2.71 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.71 mark(nil) -> nil 6.96/2.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.71 mark(s(X)) -> s(mark(X)) 6.96/2.71 mark(0) -> 0 6.96/2.71 a__incr(X) -> incr(X) 6.96/2.71 a__adx(X) -> adx(X) 6.96/2.71 a__nats -> nats 6.96/2.71 a__zeros -> zeros 6.96/2.71 a__head(X) -> head(X) 6.96/2.71 a__tail(X) -> tail(X) 6.96/2.71 6.96/2.71 The set Q consists of the following terms: 6.96/2.71 6.96/2.71 a__nats 6.96/2.71 a__zeros 6.96/2.71 mark(incr(x0)) 6.96/2.71 mark(adx(x0)) 6.96/2.71 mark(nats) 6.96/2.71 mark(zeros) 6.96/2.71 mark(head(x0)) 6.96/2.71 mark(tail(x0)) 6.96/2.71 mark(nil) 6.96/2.71 mark(cons(x0, x1)) 6.96/2.71 mark(s(x0)) 6.96/2.71 mark(0) 6.96/2.71 a__incr(x0) 6.96/2.71 a__adx(x0) 6.96/2.71 a__head(x0) 6.96/2.71 a__tail(x0) 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (7) QTRSRRRProof (EQUIVALENT) 6.96/2.71 Used ordering: 6.96/2.71 Polynomial interpretation [POLO]: 6.96/2.71 6.96/2.71 POL(0) = 0 6.96/2.71 POL(a__adx(x_1)) = x_1 6.96/2.71 POL(a__head(x_1)) = x_1 6.96/2.71 POL(a__incr(x_1)) = x_1 6.96/2.71 POL(a__nats) = 0 6.96/2.71 POL(a__tail(x_1)) = 1 + 2*x_1 6.96/2.71 POL(a__zeros) = 0 6.96/2.71 POL(adx(x_1)) = x_1 6.96/2.71 POL(cons(x_1, x_2)) = x_1 + 2*x_2 6.96/2.71 POL(head(x_1)) = x_1 6.96/2.71 POL(incr(x_1)) = x_1 6.96/2.71 POL(mark(x_1)) = x_1 6.96/2.71 POL(nats) = 0 6.96/2.71 POL(nil) = 0 6.96/2.71 POL(s(x_1)) = x_1 6.96/2.71 POL(tail(x_1)) = 1 + 2*x_1 6.96/2.71 POL(zeros) = 0 6.96/2.71 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.96/2.71 6.96/2.71 a__tail(cons(X, L)) -> mark(L) 6.96/2.71 6.96/2.71 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (8) 6.96/2.71 Obligation: 6.96/2.71 Q restricted rewrite system: 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.71 mark(nats) -> a__nats 6.96/2.71 mark(zeros) -> a__zeros 6.96/2.71 mark(head(X)) -> a__head(mark(X)) 6.96/2.71 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.71 mark(nil) -> nil 6.96/2.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.71 mark(s(X)) -> s(mark(X)) 6.96/2.71 mark(0) -> 0 6.96/2.71 a__incr(X) -> incr(X) 6.96/2.71 a__adx(X) -> adx(X) 6.96/2.71 a__nats -> nats 6.96/2.71 a__zeros -> zeros 6.96/2.71 a__head(X) -> head(X) 6.96/2.71 a__tail(X) -> tail(X) 6.96/2.71 6.96/2.71 The set Q consists of the following terms: 6.96/2.71 6.96/2.71 a__nats 6.96/2.71 a__zeros 6.96/2.71 mark(incr(x0)) 6.96/2.71 mark(adx(x0)) 6.96/2.71 mark(nats) 6.96/2.71 mark(zeros) 6.96/2.71 mark(head(x0)) 6.96/2.71 mark(tail(x0)) 6.96/2.71 mark(nil) 6.96/2.71 mark(cons(x0, x1)) 6.96/2.71 mark(s(x0)) 6.96/2.71 mark(0) 6.96/2.71 a__incr(x0) 6.96/2.71 a__adx(x0) 6.96/2.71 a__head(x0) 6.96/2.71 a__tail(x0) 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (9) DependencyPairsProof (EQUIVALENT) 6.96/2.71 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (10) 6.96/2.71 Obligation: 6.96/2.71 Q DP problem: 6.96/2.71 The TRS P consists of the following rules: 6.96/2.71 6.96/2.71 A__INCR(cons(X, L)) -> MARK(X) 6.96/2.71 A__ADX(cons(X, L)) -> A__INCR(cons(mark(X), adx(L))) 6.96/2.71 A__ADX(cons(X, L)) -> MARK(X) 6.96/2.71 MARK(incr(X)) -> A__INCR(mark(X)) 6.96/2.71 MARK(incr(X)) -> MARK(X) 6.96/2.71 MARK(adx(X)) -> A__ADX(mark(X)) 6.96/2.71 MARK(adx(X)) -> MARK(X) 6.96/2.71 MARK(nats) -> A__NATS 6.96/2.71 MARK(zeros) -> A__ZEROS 6.96/2.71 MARK(head(X)) -> A__HEAD(mark(X)) 6.96/2.71 MARK(head(X)) -> MARK(X) 6.96/2.71 MARK(tail(X)) -> A__TAIL(mark(X)) 6.96/2.71 MARK(tail(X)) -> MARK(X) 6.96/2.71 MARK(cons(X1, X2)) -> MARK(X1) 6.96/2.71 MARK(s(X)) -> MARK(X) 6.96/2.71 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.71 mark(nats) -> a__nats 6.96/2.71 mark(zeros) -> a__zeros 6.96/2.71 mark(head(X)) -> a__head(mark(X)) 6.96/2.71 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.71 mark(nil) -> nil 6.96/2.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.71 mark(s(X)) -> s(mark(X)) 6.96/2.71 mark(0) -> 0 6.96/2.71 a__incr(X) -> incr(X) 6.96/2.71 a__adx(X) -> adx(X) 6.96/2.71 a__nats -> nats 6.96/2.71 a__zeros -> zeros 6.96/2.71 a__head(X) -> head(X) 6.96/2.71 a__tail(X) -> tail(X) 6.96/2.71 6.96/2.71 The set Q consists of the following terms: 6.96/2.71 6.96/2.71 a__nats 6.96/2.71 a__zeros 6.96/2.71 mark(incr(x0)) 6.96/2.71 mark(adx(x0)) 6.96/2.71 mark(nats) 6.96/2.71 mark(zeros) 6.96/2.71 mark(head(x0)) 6.96/2.71 mark(tail(x0)) 6.96/2.71 mark(nil) 6.96/2.71 mark(cons(x0, x1)) 6.96/2.71 mark(s(x0)) 6.96/2.71 mark(0) 6.96/2.71 a__incr(x0) 6.96/2.71 a__adx(x0) 6.96/2.71 a__head(x0) 6.96/2.71 a__tail(x0) 6.96/2.71 6.96/2.71 We have to consider all minimal (P,Q,R)-chains. 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (11) DependencyGraphProof (EQUIVALENT) 6.96/2.71 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (12) 6.96/2.71 Obligation: 6.96/2.71 Q DP problem: 6.96/2.71 The TRS P consists of the following rules: 6.96/2.71 6.96/2.71 MARK(incr(X)) -> A__INCR(mark(X)) 6.96/2.71 A__INCR(cons(X, L)) -> MARK(X) 6.96/2.71 MARK(incr(X)) -> MARK(X) 6.96/2.71 MARK(adx(X)) -> A__ADX(mark(X)) 6.96/2.71 A__ADX(cons(X, L)) -> A__INCR(cons(mark(X), adx(L))) 6.96/2.71 A__ADX(cons(X, L)) -> MARK(X) 6.96/2.71 MARK(adx(X)) -> MARK(X) 6.96/2.71 MARK(head(X)) -> MARK(X) 6.96/2.71 MARK(tail(X)) -> MARK(X) 6.96/2.71 MARK(cons(X1, X2)) -> MARK(X1) 6.96/2.71 MARK(s(X)) -> MARK(X) 6.96/2.71 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.71 mark(nats) -> a__nats 6.96/2.71 mark(zeros) -> a__zeros 6.96/2.71 mark(head(X)) -> a__head(mark(X)) 6.96/2.71 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.71 mark(nil) -> nil 6.96/2.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.71 mark(s(X)) -> s(mark(X)) 6.96/2.71 mark(0) -> 0 6.96/2.71 a__incr(X) -> incr(X) 6.96/2.71 a__adx(X) -> adx(X) 6.96/2.71 a__nats -> nats 6.96/2.71 a__zeros -> zeros 6.96/2.71 a__head(X) -> head(X) 6.96/2.71 a__tail(X) -> tail(X) 6.96/2.71 6.96/2.71 The set Q consists of the following terms: 6.96/2.71 6.96/2.71 a__nats 6.96/2.71 a__zeros 6.96/2.71 mark(incr(x0)) 6.96/2.71 mark(adx(x0)) 6.96/2.71 mark(nats) 6.96/2.71 mark(zeros) 6.96/2.71 mark(head(x0)) 6.96/2.71 mark(tail(x0)) 6.96/2.71 mark(nil) 6.96/2.71 mark(cons(x0, x1)) 6.96/2.71 mark(s(x0)) 6.96/2.71 mark(0) 6.96/2.71 a__incr(x0) 6.96/2.71 a__adx(x0) 6.96/2.71 a__head(x0) 6.96/2.71 a__tail(x0) 6.96/2.71 6.96/2.71 We have to consider all minimal (P,Q,R)-chains. 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (13) MRRProof (EQUIVALENT) 6.96/2.71 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 6.96/2.71 6.96/2.71 Strictly oriented dependency pairs: 6.96/2.71 6.96/2.71 MARK(tail(X)) -> MARK(X) 6.96/2.71 6.96/2.71 6.96/2.71 Used ordering: Polynomial interpretation [POLO]: 6.96/2.71 6.96/2.71 POL(0) = 0 6.96/2.71 POL(A__ADX(x_1)) = x_1 6.96/2.71 POL(A__INCR(x_1)) = x_1 6.96/2.71 POL(MARK(x_1)) = x_1 6.96/2.71 POL(a__adx(x_1)) = x_1 6.96/2.71 POL(a__head(x_1)) = x_1 6.96/2.71 POL(a__incr(x_1)) = x_1 6.96/2.71 POL(a__nats) = 0 6.96/2.71 POL(a__tail(x_1)) = 1 + 2*x_1 6.96/2.71 POL(a__zeros) = 0 6.96/2.71 POL(adx(x_1)) = x_1 6.96/2.71 POL(cons(x_1, x_2)) = x_1 + 2*x_2 6.96/2.71 POL(head(x_1)) = x_1 6.96/2.71 POL(incr(x_1)) = x_1 6.96/2.71 POL(mark(x_1)) = x_1 6.96/2.71 POL(nats) = 0 6.96/2.71 POL(nil) = 0 6.96/2.71 POL(s(x_1)) = x_1 6.96/2.71 POL(tail(x_1)) = 1 + 2*x_1 6.96/2.71 POL(zeros) = 0 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (14) 6.96/2.71 Obligation: 6.96/2.71 Q DP problem: 6.96/2.71 The TRS P consists of the following rules: 6.96/2.71 6.96/2.71 MARK(incr(X)) -> A__INCR(mark(X)) 6.96/2.71 A__INCR(cons(X, L)) -> MARK(X) 6.96/2.71 MARK(incr(X)) -> MARK(X) 6.96/2.71 MARK(adx(X)) -> A__ADX(mark(X)) 6.96/2.71 A__ADX(cons(X, L)) -> A__INCR(cons(mark(X), adx(L))) 6.96/2.71 A__ADX(cons(X, L)) -> MARK(X) 6.96/2.71 MARK(adx(X)) -> MARK(X) 6.96/2.71 MARK(head(X)) -> MARK(X) 6.96/2.71 MARK(cons(X1, X2)) -> MARK(X1) 6.96/2.71 MARK(s(X)) -> MARK(X) 6.96/2.71 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.71 mark(nats) -> a__nats 6.96/2.71 mark(zeros) -> a__zeros 6.96/2.71 mark(head(X)) -> a__head(mark(X)) 6.96/2.71 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.71 mark(nil) -> nil 6.96/2.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.71 mark(s(X)) -> s(mark(X)) 6.96/2.71 mark(0) -> 0 6.96/2.71 a__incr(X) -> incr(X) 6.96/2.71 a__adx(X) -> adx(X) 6.96/2.71 a__nats -> nats 6.96/2.71 a__zeros -> zeros 6.96/2.71 a__head(X) -> head(X) 6.96/2.71 a__tail(X) -> tail(X) 6.96/2.71 6.96/2.71 The set Q consists of the following terms: 6.96/2.71 6.96/2.71 a__nats 6.96/2.71 a__zeros 6.96/2.71 mark(incr(x0)) 6.96/2.71 mark(adx(x0)) 6.96/2.71 mark(nats) 6.96/2.71 mark(zeros) 6.96/2.71 mark(head(x0)) 6.96/2.71 mark(tail(x0)) 6.96/2.71 mark(nil) 6.96/2.71 mark(cons(x0, x1)) 6.96/2.71 mark(s(x0)) 6.96/2.71 mark(0) 6.96/2.71 a__incr(x0) 6.96/2.71 a__adx(x0) 6.96/2.71 a__head(x0) 6.96/2.71 a__tail(x0) 6.96/2.71 6.96/2.71 We have to consider all minimal (P,Q,R)-chains. 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (15) MRRProof (EQUIVALENT) 6.96/2.71 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 6.96/2.71 6.96/2.71 Strictly oriented dependency pairs: 6.96/2.71 6.96/2.71 MARK(head(X)) -> MARK(X) 6.96/2.71 6.96/2.71 6.96/2.71 Used ordering: Polynomial interpretation [POLO]: 6.96/2.71 6.96/2.71 POL(0) = 0 6.96/2.71 POL(A__ADX(x_1)) = 2*x_1 6.96/2.71 POL(A__INCR(x_1)) = 2*x_1 6.96/2.71 POL(MARK(x_1)) = 2*x_1 6.96/2.71 POL(a__adx(x_1)) = x_1 6.96/2.71 POL(a__head(x_1)) = 1 + x_1 6.96/2.71 POL(a__incr(x_1)) = x_1 6.96/2.71 POL(a__nats) = 0 6.96/2.71 POL(a__tail(x_1)) = x_1 6.96/2.71 POL(a__zeros) = 0 6.96/2.71 POL(adx(x_1)) = x_1 6.96/2.71 POL(cons(x_1, x_2)) = x_1 + x_2 6.96/2.71 POL(head(x_1)) = 1 + x_1 6.96/2.71 POL(incr(x_1)) = x_1 6.96/2.71 POL(mark(x_1)) = x_1 6.96/2.71 POL(nats) = 0 6.96/2.71 POL(nil) = 0 6.96/2.71 POL(s(x_1)) = x_1 6.96/2.71 POL(tail(x_1)) = x_1 6.96/2.71 POL(zeros) = 0 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (16) 6.96/2.71 Obligation: 6.96/2.71 Q DP problem: 6.96/2.71 The TRS P consists of the following rules: 6.96/2.71 6.96/2.71 MARK(incr(X)) -> A__INCR(mark(X)) 6.96/2.71 A__INCR(cons(X, L)) -> MARK(X) 6.96/2.71 MARK(incr(X)) -> MARK(X) 6.96/2.71 MARK(adx(X)) -> A__ADX(mark(X)) 6.96/2.71 A__ADX(cons(X, L)) -> A__INCR(cons(mark(X), adx(L))) 6.96/2.71 A__ADX(cons(X, L)) -> MARK(X) 6.96/2.71 MARK(adx(X)) -> MARK(X) 6.96/2.71 MARK(cons(X1, X2)) -> MARK(X1) 6.96/2.71 MARK(s(X)) -> MARK(X) 6.96/2.71 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.71 mark(nats) -> a__nats 6.96/2.71 mark(zeros) -> a__zeros 6.96/2.71 mark(head(X)) -> a__head(mark(X)) 6.96/2.71 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.71 mark(nil) -> nil 6.96/2.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.71 mark(s(X)) -> s(mark(X)) 6.96/2.71 mark(0) -> 0 6.96/2.71 a__incr(X) -> incr(X) 6.96/2.71 a__adx(X) -> adx(X) 6.96/2.71 a__nats -> nats 6.96/2.71 a__zeros -> zeros 6.96/2.71 a__head(X) -> head(X) 6.96/2.71 a__tail(X) -> tail(X) 6.96/2.71 6.96/2.71 The set Q consists of the following terms: 6.96/2.71 6.96/2.71 a__nats 6.96/2.71 a__zeros 6.96/2.71 mark(incr(x0)) 6.96/2.71 mark(adx(x0)) 6.96/2.71 mark(nats) 6.96/2.71 mark(zeros) 6.96/2.71 mark(head(x0)) 6.96/2.71 mark(tail(x0)) 6.96/2.71 mark(nil) 6.96/2.71 mark(cons(x0, x1)) 6.96/2.71 mark(s(x0)) 6.96/2.71 mark(0) 6.96/2.71 a__incr(x0) 6.96/2.71 a__adx(x0) 6.96/2.71 a__head(x0) 6.96/2.71 a__tail(x0) 6.96/2.71 6.96/2.71 We have to consider all minimal (P,Q,R)-chains. 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (17) MRRProof (EQUIVALENT) 6.96/2.71 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 6.96/2.71 6.96/2.71 Strictly oriented dependency pairs: 6.96/2.71 6.96/2.71 MARK(adx(X)) -> A__ADX(mark(X)) 6.96/2.71 A__ADX(cons(X, L)) -> MARK(X) 6.96/2.71 MARK(adx(X)) -> MARK(X) 6.96/2.71 6.96/2.71 6.96/2.71 Used ordering: Polynomial interpretation [POLO]: 6.96/2.71 6.96/2.71 POL(0) = 0 6.96/2.71 POL(A__ADX(x_1)) = 1 + 2*x_1 6.96/2.71 POL(A__INCR(x_1)) = x_1 6.96/2.71 POL(MARK(x_1)) = 2*x_1 6.96/2.71 POL(a__adx(x_1)) = 1 + x_1 6.96/2.71 POL(a__head(x_1)) = x_1 6.96/2.71 POL(a__incr(x_1)) = x_1 6.96/2.71 POL(a__nats) = 0 6.96/2.71 POL(a__tail(x_1)) = 2*x_1 6.96/2.71 POL(a__zeros) = 0 6.96/2.71 POL(adx(x_1)) = 1 + x_1 6.96/2.71 POL(cons(x_1, x_2)) = 2*x_1 + x_2 6.96/2.71 POL(head(x_1)) = x_1 6.96/2.71 POL(incr(x_1)) = x_1 6.96/2.71 POL(mark(x_1)) = x_1 6.96/2.71 POL(nats) = 0 6.96/2.71 POL(nil) = 0 6.96/2.71 POL(s(x_1)) = x_1 6.96/2.71 POL(tail(x_1)) = 2*x_1 6.96/2.71 POL(zeros) = 0 6.96/2.71 6.96/2.71 6.96/2.71 ---------------------------------------- 6.96/2.71 6.96/2.71 (18) 6.96/2.71 Obligation: 6.96/2.71 Q DP problem: 6.96/2.71 The TRS P consists of the following rules: 6.96/2.71 6.96/2.71 MARK(incr(X)) -> A__INCR(mark(X)) 6.96/2.71 A__INCR(cons(X, L)) -> MARK(X) 6.96/2.71 MARK(incr(X)) -> MARK(X) 6.96/2.71 A__ADX(cons(X, L)) -> A__INCR(cons(mark(X), adx(L))) 6.96/2.71 MARK(cons(X1, X2)) -> MARK(X1) 6.96/2.71 MARK(s(X)) -> MARK(X) 6.96/2.71 6.96/2.71 The TRS R consists of the following rules: 6.96/2.71 6.96/2.71 a__incr(nil) -> nil 6.96/2.71 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.71 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.71 a__zeros -> cons(0, zeros) 6.96/2.71 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.71 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.72 mark(nats) -> a__nats 6.96/2.72 mark(zeros) -> a__zeros 6.96/2.72 mark(head(X)) -> a__head(mark(X)) 6.96/2.72 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.72 mark(nil) -> nil 6.96/2.72 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.72 mark(s(X)) -> s(mark(X)) 6.96/2.72 mark(0) -> 0 6.96/2.72 a__incr(X) -> incr(X) 6.96/2.72 a__adx(X) -> adx(X) 6.96/2.72 a__nats -> nats 6.96/2.72 a__zeros -> zeros 6.96/2.72 a__head(X) -> head(X) 6.96/2.72 a__tail(X) -> tail(X) 6.96/2.72 6.96/2.72 The set Q consists of the following terms: 6.96/2.72 6.96/2.72 a__nats 6.96/2.72 a__zeros 6.96/2.72 mark(incr(x0)) 6.96/2.72 mark(adx(x0)) 6.96/2.72 mark(nats) 6.96/2.72 mark(zeros) 6.96/2.72 mark(head(x0)) 6.96/2.72 mark(tail(x0)) 6.96/2.72 mark(nil) 6.96/2.72 mark(cons(x0, x1)) 6.96/2.72 mark(s(x0)) 6.96/2.72 mark(0) 6.96/2.72 a__incr(x0) 6.96/2.72 a__adx(x0) 6.96/2.72 a__head(x0) 6.96/2.72 a__tail(x0) 6.96/2.72 6.96/2.72 We have to consider all minimal (P,Q,R)-chains. 6.96/2.72 ---------------------------------------- 6.96/2.72 6.96/2.72 (19) DependencyGraphProof (EQUIVALENT) 6.96/2.72 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 6.96/2.72 ---------------------------------------- 6.96/2.72 6.96/2.72 (20) 6.96/2.72 Obligation: 6.96/2.72 Q DP problem: 6.96/2.72 The TRS P consists of the following rules: 6.96/2.72 6.96/2.72 A__INCR(cons(X, L)) -> MARK(X) 6.96/2.72 MARK(incr(X)) -> A__INCR(mark(X)) 6.96/2.72 MARK(incr(X)) -> MARK(X) 6.96/2.72 MARK(cons(X1, X2)) -> MARK(X1) 6.96/2.72 MARK(s(X)) -> MARK(X) 6.96/2.72 6.96/2.72 The TRS R consists of the following rules: 6.96/2.72 6.96/2.72 a__incr(nil) -> nil 6.96/2.72 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.72 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.72 a__zeros -> cons(0, zeros) 6.96/2.72 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.72 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.72 mark(nats) -> a__nats 6.96/2.72 mark(zeros) -> a__zeros 6.96/2.72 mark(head(X)) -> a__head(mark(X)) 6.96/2.72 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.72 mark(nil) -> nil 6.96/2.72 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.72 mark(s(X)) -> s(mark(X)) 6.96/2.72 mark(0) -> 0 6.96/2.72 a__incr(X) -> incr(X) 6.96/2.72 a__adx(X) -> adx(X) 6.96/2.72 a__nats -> nats 6.96/2.72 a__zeros -> zeros 6.96/2.72 a__head(X) -> head(X) 6.96/2.72 a__tail(X) -> tail(X) 6.96/2.72 6.96/2.72 The set Q consists of the following terms: 6.96/2.72 6.96/2.72 a__nats 6.96/2.72 a__zeros 6.96/2.72 mark(incr(x0)) 6.96/2.72 mark(adx(x0)) 6.96/2.72 mark(nats) 6.96/2.72 mark(zeros) 6.96/2.72 mark(head(x0)) 6.96/2.72 mark(tail(x0)) 6.96/2.72 mark(nil) 6.96/2.72 mark(cons(x0, x1)) 6.96/2.72 mark(s(x0)) 6.96/2.72 mark(0) 6.96/2.72 a__incr(x0) 6.96/2.72 a__adx(x0) 6.96/2.72 a__head(x0) 6.96/2.72 a__tail(x0) 6.96/2.72 6.96/2.72 We have to consider all minimal (P,Q,R)-chains. 6.96/2.72 ---------------------------------------- 6.96/2.72 6.96/2.72 (21) QDPOrderProof (EQUIVALENT) 6.96/2.72 We use the reduction pair processor [LPAR04,JAR06]. 6.96/2.72 6.96/2.72 6.96/2.72 The following pairs can be oriented strictly and are deleted. 6.96/2.72 6.96/2.72 A__INCR(cons(X, L)) -> MARK(X) 6.96/2.72 MARK(incr(X)) -> A__INCR(mark(X)) 6.96/2.72 MARK(incr(X)) -> MARK(X) 6.96/2.72 MARK(cons(X1, X2)) -> MARK(X1) 6.96/2.72 MARK(s(X)) -> MARK(X) 6.96/2.72 The remaining pairs can at least be oriented weakly. 6.96/2.72 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 6.96/2.72 6.96/2.72 POL( A__INCR_1(x_1) ) = 2x_1 + 1 6.96/2.72 POL( mark_1(x_1) ) = x_1 6.96/2.72 POL( incr_1(x_1) ) = 2x_1 + 2 6.96/2.72 POL( a__incr_1(x_1) ) = 2x_1 + 2 6.96/2.72 POL( adx_1(x_1) ) = 2x_1 + 2 6.96/2.72 POL( a__adx_1(x_1) ) = 2x_1 + 2 6.96/2.72 POL( nats ) = 2 6.96/2.72 POL( a__nats ) = 2 6.96/2.72 POL( zeros ) = 1 6.96/2.72 POL( a__zeros ) = 1 6.96/2.72 POL( head_1(x_1) ) = 0 6.96/2.72 POL( a__head_1(x_1) ) = max{0, -2} 6.96/2.72 POL( tail_1(x_1) ) = 0 6.96/2.72 POL( a__tail_1(x_1) ) = 0 6.96/2.72 POL( nil ) = 0 6.96/2.72 POL( cons_2(x_1, x_2) ) = x_1 + 1 6.96/2.72 POL( s_1(x_1) ) = 2x_1 + 1 6.96/2.72 POL( 0 ) = 0 6.96/2.72 POL( MARK_1(x_1) ) = x_1 + 2 6.96/2.72 6.96/2.72 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 6.96/2.72 6.96/2.72 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.72 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.72 mark(nats) -> a__nats 6.96/2.72 mark(zeros) -> a__zeros 6.96/2.72 mark(head(X)) -> a__head(mark(X)) 6.96/2.72 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.72 mark(nil) -> nil 6.96/2.72 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.72 mark(s(X)) -> s(mark(X)) 6.96/2.72 mark(0) -> 0 6.96/2.72 a__adx(X) -> adx(X) 6.96/2.72 a__incr(nil) -> nil 6.96/2.72 a__incr(X) -> incr(X) 6.96/2.72 a__head(X) -> head(X) 6.96/2.72 a__tail(X) -> tail(X) 6.96/2.72 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.72 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.72 a__zeros -> cons(0, zeros) 6.96/2.72 a__zeros -> zeros 6.96/2.72 a__nats -> nats 6.96/2.72 6.96/2.72 6.96/2.72 ---------------------------------------- 6.96/2.72 6.96/2.72 (22) 6.96/2.72 Obligation: 6.96/2.72 Q DP problem: 6.96/2.72 P is empty. 6.96/2.72 The TRS R consists of the following rules: 6.96/2.72 6.96/2.72 a__incr(nil) -> nil 6.96/2.72 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 6.96/2.72 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 6.96/2.72 a__zeros -> cons(0, zeros) 6.96/2.72 mark(incr(X)) -> a__incr(mark(X)) 6.96/2.72 mark(adx(X)) -> a__adx(mark(X)) 6.96/2.72 mark(nats) -> a__nats 6.96/2.72 mark(zeros) -> a__zeros 6.96/2.72 mark(head(X)) -> a__head(mark(X)) 6.96/2.72 mark(tail(X)) -> a__tail(mark(X)) 6.96/2.72 mark(nil) -> nil 6.96/2.72 mark(cons(X1, X2)) -> cons(mark(X1), X2) 6.96/2.72 mark(s(X)) -> s(mark(X)) 6.96/2.72 mark(0) -> 0 6.96/2.72 a__incr(X) -> incr(X) 6.96/2.72 a__adx(X) -> adx(X) 6.96/2.72 a__nats -> nats 6.96/2.72 a__zeros -> zeros 6.96/2.72 a__head(X) -> head(X) 6.96/2.72 a__tail(X) -> tail(X) 6.96/2.72 6.96/2.72 The set Q consists of the following terms: 6.96/2.72 6.96/2.72 a__nats 6.96/2.72 a__zeros 6.96/2.72 mark(incr(x0)) 6.96/2.72 mark(adx(x0)) 6.96/2.72 mark(nats) 6.96/2.72 mark(zeros) 6.96/2.72 mark(head(x0)) 6.96/2.72 mark(tail(x0)) 6.96/2.72 mark(nil) 6.96/2.72 mark(cons(x0, x1)) 6.96/2.72 mark(s(x0)) 6.96/2.72 mark(0) 6.96/2.72 a__incr(x0) 6.96/2.72 a__adx(x0) 6.96/2.72 a__head(x0) 6.96/2.72 a__tail(x0) 6.96/2.72 6.96/2.72 We have to consider all minimal (P,Q,R)-chains. 6.96/2.72 ---------------------------------------- 6.96/2.72 6.96/2.72 (23) PisEmptyProof (EQUIVALENT) 6.96/2.72 The TRS P is empty. Hence, there is no (P,Q,R) chain. 6.96/2.72 ---------------------------------------- 6.96/2.72 6.96/2.72 (24) 6.96/2.72 YES 7.01/2.77 EOF