1081.63/291.56 WORST_CASE(Omega(n^1), ?) 1081.63/291.56 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1081.63/291.56 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1081.63/291.56 1081.63/291.56 1081.63/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1081.63/291.56 1081.63/291.56 (0) CpxTRS 1081.63/291.56 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1081.63/291.56 (2) CpxTRS 1081.63/291.56 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1081.63/291.56 (4) typed CpxTrs 1081.63/291.56 (5) OrderProof [LOWER BOUND(ID), 4 ms] 1081.63/291.56 (6) typed CpxTrs 1081.63/291.56 (7) RewriteLemmaProof [LOWER BOUND(ID), 550 ms] 1081.63/291.56 (8) BEST 1081.63/291.56 (9) proven lower bound 1081.63/291.56 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1081.63/291.56 (11) BOUNDS(n^1, INF) 1081.63/291.56 (12) typed CpxTrs 1081.63/291.56 1081.63/291.56 1081.63/291.56 ---------------------------------------- 1081.63/291.56 1081.63/291.56 (0) 1081.63/291.56 Obligation: 1081.63/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1081.63/291.56 1081.63/291.56 1081.63/291.56 The TRS R consists of the following rules: 1081.63/291.56 1081.63/291.56 a__incr(nil) -> nil 1081.63/291.56 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 1081.63/291.56 a__adx(nil) -> nil 1081.63/291.56 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 1081.63/291.56 a__nats -> a__adx(a__zeros) 1081.63/291.56 a__zeros -> cons(0, zeros) 1081.63/291.57 a__head(cons(X, L)) -> mark(X) 1081.63/291.57 a__tail(cons(X, L)) -> mark(L) 1081.63/291.57 mark(incr(X)) -> a__incr(mark(X)) 1081.63/291.57 mark(adx(X)) -> a__adx(mark(X)) 1081.63/291.57 mark(nats) -> a__nats 1081.63/291.57 mark(zeros) -> a__zeros 1081.63/291.57 mark(head(X)) -> a__head(mark(X)) 1081.63/291.57 mark(tail(X)) -> a__tail(mark(X)) 1081.63/291.57 mark(nil) -> nil 1081.63/291.57 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1081.63/291.57 mark(s(X)) -> s(mark(X)) 1081.63/291.57 mark(0) -> 0 1081.63/291.57 a__incr(X) -> incr(X) 1081.63/291.57 a__adx(X) -> adx(X) 1081.63/291.57 a__nats -> nats 1081.63/291.57 a__zeros -> zeros 1081.63/291.57 a__head(X) -> head(X) 1081.63/291.57 a__tail(X) -> tail(X) 1081.63/291.57 1081.63/291.57 S is empty. 1081.63/291.57 Rewrite Strategy: FULL 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1081.63/291.57 Renamed function symbols to avoid clashes with predefined symbol. 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (2) 1081.63/291.57 Obligation: 1081.63/291.57 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1081.63/291.57 1081.63/291.57 1081.63/291.57 The TRS R consists of the following rules: 1081.63/291.57 1081.63/291.57 a__incr(nil) -> nil 1081.63/291.57 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 1081.63/291.57 a__adx(nil) -> nil 1081.63/291.57 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 1081.63/291.57 a__nats -> a__adx(a__zeros) 1081.63/291.57 a__zeros -> cons(0', zeros) 1081.63/291.57 a__head(cons(X, L)) -> mark(X) 1081.63/291.57 a__tail(cons(X, L)) -> mark(L) 1081.63/291.57 mark(incr(X)) -> a__incr(mark(X)) 1081.63/291.57 mark(adx(X)) -> a__adx(mark(X)) 1081.63/291.57 mark(nats) -> a__nats 1081.63/291.57 mark(zeros) -> a__zeros 1081.63/291.57 mark(head(X)) -> a__head(mark(X)) 1081.63/291.57 mark(tail(X)) -> a__tail(mark(X)) 1081.63/291.57 mark(nil) -> nil 1081.63/291.57 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1081.63/291.57 mark(s(X)) -> s(mark(X)) 1081.63/291.57 mark(0') -> 0' 1081.63/291.57 a__incr(X) -> incr(X) 1081.63/291.57 a__adx(X) -> adx(X) 1081.63/291.57 a__nats -> nats 1081.63/291.57 a__zeros -> zeros 1081.63/291.57 a__head(X) -> head(X) 1081.63/291.57 a__tail(X) -> tail(X) 1081.63/291.57 1081.63/291.57 S is empty. 1081.63/291.57 Rewrite Strategy: FULL 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1081.63/291.57 Infered types. 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (4) 1081.63/291.57 Obligation: 1081.63/291.57 TRS: 1081.63/291.57 Rules: 1081.63/291.57 a__incr(nil) -> nil 1081.63/291.57 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 1081.63/291.57 a__adx(nil) -> nil 1081.63/291.57 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 1081.63/291.57 a__nats -> a__adx(a__zeros) 1081.63/291.57 a__zeros -> cons(0', zeros) 1081.63/291.57 a__head(cons(X, L)) -> mark(X) 1081.63/291.57 a__tail(cons(X, L)) -> mark(L) 1081.63/291.57 mark(incr(X)) -> a__incr(mark(X)) 1081.63/291.57 mark(adx(X)) -> a__adx(mark(X)) 1081.63/291.57 mark(nats) -> a__nats 1081.63/291.57 mark(zeros) -> a__zeros 1081.63/291.57 mark(head(X)) -> a__head(mark(X)) 1081.63/291.57 mark(tail(X)) -> a__tail(mark(X)) 1081.63/291.57 mark(nil) -> nil 1081.63/291.57 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1081.63/291.57 mark(s(X)) -> s(mark(X)) 1081.63/291.57 mark(0') -> 0' 1081.63/291.57 a__incr(X) -> incr(X) 1081.63/291.57 a__adx(X) -> adx(X) 1081.63/291.57 a__nats -> nats 1081.63/291.57 a__zeros -> zeros 1081.63/291.57 a__head(X) -> head(X) 1081.63/291.57 a__tail(X) -> tail(X) 1081.63/291.57 1081.63/291.57 Types: 1081.63/291.57 a__incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 nil :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 cons :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 s :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 mark :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 0' :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 hole_nil:cons:s:incr:adx:0':zeros:nats:head:tail1_0 :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0 :: Nat -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (5) OrderProof (LOWER BOUND(ID)) 1081.63/291.57 Heuristically decided to analyse the following defined symbols: 1081.63/291.57 a__incr, mark, a__adx, a__nats, a__head, a__tail 1081.63/291.57 1081.63/291.57 They will be analysed ascendingly in the following order: 1081.63/291.57 a__incr = mark 1081.63/291.57 a__incr = a__adx 1081.63/291.57 a__incr = a__nats 1081.63/291.57 a__incr = a__head 1081.63/291.57 a__incr = a__tail 1081.63/291.57 mark = a__adx 1081.63/291.57 mark = a__nats 1081.63/291.57 mark = a__head 1081.63/291.57 mark = a__tail 1081.63/291.57 a__adx = a__nats 1081.63/291.57 a__adx = a__head 1081.63/291.57 a__adx = a__tail 1081.63/291.57 a__nats = a__head 1081.63/291.57 a__nats = a__tail 1081.63/291.57 a__head = a__tail 1081.63/291.57 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (6) 1081.63/291.57 Obligation: 1081.63/291.57 TRS: 1081.63/291.57 Rules: 1081.63/291.57 a__incr(nil) -> nil 1081.63/291.57 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 1081.63/291.57 a__adx(nil) -> nil 1081.63/291.57 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 1081.63/291.57 a__nats -> a__adx(a__zeros) 1081.63/291.57 a__zeros -> cons(0', zeros) 1081.63/291.57 a__head(cons(X, L)) -> mark(X) 1081.63/291.57 a__tail(cons(X, L)) -> mark(L) 1081.63/291.57 mark(incr(X)) -> a__incr(mark(X)) 1081.63/291.57 mark(adx(X)) -> a__adx(mark(X)) 1081.63/291.57 mark(nats) -> a__nats 1081.63/291.57 mark(zeros) -> a__zeros 1081.63/291.57 mark(head(X)) -> a__head(mark(X)) 1081.63/291.57 mark(tail(X)) -> a__tail(mark(X)) 1081.63/291.57 mark(nil) -> nil 1081.63/291.57 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1081.63/291.57 mark(s(X)) -> s(mark(X)) 1081.63/291.57 mark(0') -> 0' 1081.63/291.57 a__incr(X) -> incr(X) 1081.63/291.57 a__adx(X) -> adx(X) 1081.63/291.57 a__nats -> nats 1081.63/291.57 a__zeros -> zeros 1081.63/291.57 a__head(X) -> head(X) 1081.63/291.57 a__tail(X) -> tail(X) 1081.63/291.57 1081.63/291.57 Types: 1081.63/291.57 a__incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 nil :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 cons :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 s :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 mark :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 0' :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 hole_nil:cons:s:incr:adx:0':zeros:nats:head:tail1_0 :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0 :: Nat -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 1081.63/291.57 1081.63/291.57 Generator Equations: 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(0) <=> nil 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(+(x, 1)) <=> cons(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(x), nil) 1081.63/291.57 1081.63/291.57 1081.63/291.57 The following defined symbols remain to be analysed: 1081.63/291.57 mark, a__incr, a__adx, a__nats, a__head, a__tail 1081.63/291.57 1081.63/291.57 They will be analysed ascendingly in the following order: 1081.63/291.57 a__incr = mark 1081.63/291.57 a__incr = a__adx 1081.63/291.57 a__incr = a__nats 1081.63/291.57 a__incr = a__head 1081.63/291.57 a__incr = a__tail 1081.63/291.57 mark = a__adx 1081.63/291.57 mark = a__nats 1081.63/291.57 mark = a__head 1081.63/291.57 mark = a__tail 1081.63/291.57 a__adx = a__nats 1081.63/291.57 a__adx = a__head 1081.63/291.57 a__adx = a__tail 1081.63/291.57 a__nats = a__head 1081.63/291.57 a__nats = a__tail 1081.63/291.57 a__head = a__tail 1081.63/291.57 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1081.63/291.57 Proved the following rewrite lemma: 1081.63/291.57 mark(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(n4_0)) -> gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(n4_0), rt in Omega(1 + n4_0) 1081.63/291.57 1081.63/291.57 Induction Base: 1081.63/291.57 mark(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(0)) ->_R^Omega(1) 1081.63/291.57 nil 1081.63/291.57 1081.63/291.57 Induction Step: 1081.63/291.57 mark(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(+(n4_0, 1))) ->_R^Omega(1) 1081.63/291.57 cons(mark(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(n4_0)), nil) ->_IH 1081.63/291.57 cons(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(c5_0), nil) 1081.63/291.57 1081.63/291.57 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (8) 1081.63/291.57 Complex Obligation (BEST) 1081.63/291.57 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (9) 1081.63/291.57 Obligation: 1081.63/291.57 Proved the lower bound n^1 for the following obligation: 1081.63/291.57 1081.63/291.57 TRS: 1081.63/291.57 Rules: 1081.63/291.57 a__incr(nil) -> nil 1081.63/291.57 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 1081.63/291.57 a__adx(nil) -> nil 1081.63/291.57 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 1081.63/291.57 a__nats -> a__adx(a__zeros) 1081.63/291.57 a__zeros -> cons(0', zeros) 1081.63/291.57 a__head(cons(X, L)) -> mark(X) 1081.63/291.57 a__tail(cons(X, L)) -> mark(L) 1081.63/291.57 mark(incr(X)) -> a__incr(mark(X)) 1081.63/291.57 mark(adx(X)) -> a__adx(mark(X)) 1081.63/291.57 mark(nats) -> a__nats 1081.63/291.57 mark(zeros) -> a__zeros 1081.63/291.57 mark(head(X)) -> a__head(mark(X)) 1081.63/291.57 mark(tail(X)) -> a__tail(mark(X)) 1081.63/291.57 mark(nil) -> nil 1081.63/291.57 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1081.63/291.57 mark(s(X)) -> s(mark(X)) 1081.63/291.57 mark(0') -> 0' 1081.63/291.57 a__incr(X) -> incr(X) 1081.63/291.57 a__adx(X) -> adx(X) 1081.63/291.57 a__nats -> nats 1081.63/291.57 a__zeros -> zeros 1081.63/291.57 a__head(X) -> head(X) 1081.63/291.57 a__tail(X) -> tail(X) 1081.63/291.57 1081.63/291.57 Types: 1081.63/291.57 a__incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 nil :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 cons :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 s :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 mark :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 0' :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 hole_nil:cons:s:incr:adx:0':zeros:nats:head:tail1_0 :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0 :: Nat -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 1081.63/291.57 1081.63/291.57 Generator Equations: 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(0) <=> nil 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(+(x, 1)) <=> cons(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(x), nil) 1081.63/291.57 1081.63/291.57 1081.63/291.57 The following defined symbols remain to be analysed: 1081.63/291.57 mark, a__incr, a__adx, a__nats, a__head, a__tail 1081.63/291.57 1081.63/291.57 They will be analysed ascendingly in the following order: 1081.63/291.57 a__incr = mark 1081.63/291.57 a__incr = a__adx 1081.63/291.57 a__incr = a__nats 1081.63/291.57 a__incr = a__head 1081.63/291.57 a__incr = a__tail 1081.63/291.57 mark = a__adx 1081.63/291.57 mark = a__nats 1081.63/291.57 mark = a__head 1081.63/291.57 mark = a__tail 1081.63/291.57 a__adx = a__nats 1081.63/291.57 a__adx = a__head 1081.63/291.57 a__adx = a__tail 1081.63/291.57 a__nats = a__head 1081.63/291.57 a__nats = a__tail 1081.63/291.57 a__head = a__tail 1081.63/291.57 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (10) LowerBoundPropagationProof (FINISHED) 1081.63/291.57 Propagated lower bound. 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (11) 1081.63/291.57 BOUNDS(n^1, INF) 1081.63/291.57 1081.63/291.57 ---------------------------------------- 1081.63/291.57 1081.63/291.57 (12) 1081.63/291.57 Obligation: 1081.63/291.57 TRS: 1081.63/291.57 Rules: 1081.63/291.57 a__incr(nil) -> nil 1081.63/291.57 a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L)) 1081.63/291.57 a__adx(nil) -> nil 1081.63/291.57 a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L))) 1081.63/291.57 a__nats -> a__adx(a__zeros) 1081.63/291.57 a__zeros -> cons(0', zeros) 1081.63/291.57 a__head(cons(X, L)) -> mark(X) 1081.63/291.57 a__tail(cons(X, L)) -> mark(L) 1081.63/291.57 mark(incr(X)) -> a__incr(mark(X)) 1081.63/291.57 mark(adx(X)) -> a__adx(mark(X)) 1081.63/291.57 mark(nats) -> a__nats 1081.63/291.57 mark(zeros) -> a__zeros 1081.63/291.57 mark(head(X)) -> a__head(mark(X)) 1081.63/291.57 mark(tail(X)) -> a__tail(mark(X)) 1081.63/291.57 mark(nil) -> nil 1081.63/291.57 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1081.63/291.57 mark(s(X)) -> s(mark(X)) 1081.63/291.57 mark(0') -> 0' 1081.63/291.57 a__incr(X) -> incr(X) 1081.63/291.57 a__adx(X) -> adx(X) 1081.63/291.57 a__nats -> nats 1081.63/291.57 a__zeros -> zeros 1081.63/291.57 a__head(X) -> head(X) 1081.63/291.57 a__tail(X) -> tail(X) 1081.63/291.57 1081.63/291.57 Types: 1081.63/291.57 a__incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 nil :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 cons :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 s :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 mark :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 0' :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 a__tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 hole_nil:cons:s:incr:adx:0':zeros:nats:head:tail1_0 :: nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0 :: Nat -> nil:cons:s:incr:adx:0':zeros:nats:head:tail 1081.63/291.57 1081.63/291.57 1081.63/291.57 Lemmas: 1081.63/291.57 mark(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(n4_0)) -> gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(n4_0), rt in Omega(1 + n4_0) 1081.63/291.57 1081.63/291.57 1081.63/291.57 Generator Equations: 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(0) <=> nil 1081.63/291.57 gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(+(x, 1)) <=> cons(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(x), nil) 1081.63/291.57 1081.63/291.57 1081.63/291.57 The following defined symbols remain to be analysed: 1081.63/291.57 a__incr, a__adx, a__nats, a__head, a__tail 1081.63/291.57 1081.63/291.57 They will be analysed ascendingly in the following order: 1081.63/291.57 a__incr = mark 1081.63/291.57 a__incr = a__adx 1081.63/291.57 a__incr = a__nats 1081.63/291.57 a__incr = a__head 1081.63/291.57 a__incr = a__tail 1081.63/291.57 mark = a__adx 1081.63/291.57 mark = a__nats 1081.63/291.57 mark = a__head 1081.63/291.57 mark = a__tail 1081.63/291.57 a__adx = a__nats 1081.63/291.57 a__adx = a__head 1081.63/291.57 a__adx = a__tail 1081.63/291.57 a__nats = a__head 1081.63/291.57 a__nats = a__tail 1081.63/291.57 a__head = a__tail 1081.75/291.65 EOF