/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^1), ?)
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).

(0) CpxTRS
(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxTRS
(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) typed CpxTrs
(5) OrderProof [LOWER BOUND(ID), 0 ms]
(6) typed CpxTrs
(7) RewriteLemmaProof [LOWER BOUND(ID), 635 ms]
(8) BEST
    (9) proven lower bound
        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
        (11) BOUNDS(n^1, INF)
    (12) typed CpxTrs


----------------------------------------

(0)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   a__incr(nil) -> nil
   a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L))
   a__adx(nil) -> nil
   a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L)))
   a__nats -> a__adx(a__zeros)
   a__zeros -> cons(0, zeros)
   a__head(cons(X, L)) -> mark(X)
   a__tail(cons(X, L)) -> mark(L)
   mark(incr(X)) -> a__incr(mark(X))
   mark(adx(X)) -> a__adx(mark(X))
   mark(nats) -> a__nats
   mark(zeros) -> a__zeros
   mark(head(X)) -> a__head(mark(X))
   mark(tail(X)) -> a__tail(mark(X))
   mark(nil) -> nil
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(s(X)) -> s(mark(X))
   mark(0) -> 0
   a__incr(X) -> incr(X)
   a__adx(X) -> adx(X)
   a__nats -> nats
   a__zeros -> zeros
   a__head(X) -> head(X)
   a__tail(X) -> tail(X)

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(1) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(2)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   a__incr(nil) -> nil
   a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L))
   a__adx(nil) -> nil
   a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L)))
   a__nats -> a__adx(a__zeros)
   a__zeros -> cons(0', zeros)
   a__head(cons(X, L)) -> mark(X)
   a__tail(cons(X, L)) -> mark(L)
   mark(incr(X)) -> a__incr(mark(X))
   mark(adx(X)) -> a__adx(mark(X))
   mark(nats) -> a__nats
   mark(zeros) -> a__zeros
   mark(head(X)) -> a__head(mark(X))
   mark(tail(X)) -> a__tail(mark(X))
   mark(nil) -> nil
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(s(X)) -> s(mark(X))
   mark(0') -> 0'
   a__incr(X) -> incr(X)
   a__adx(X) -> adx(X)
   a__nats -> nats
   a__zeros -> zeros
   a__head(X) -> head(X)
   a__tail(X) -> tail(X)

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(4)
Obligation:
TRS:
Rules:
a__incr(nil) -> nil
a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L))
a__adx(nil) -> nil
a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L)))
a__nats -> a__adx(a__zeros)
a__zeros -> cons(0', zeros)
a__head(cons(X, L)) -> mark(X)
a__tail(cons(X, L)) -> mark(L)
mark(incr(X)) -> a__incr(mark(X))
mark(adx(X)) -> a__adx(mark(X))
mark(nats) -> a__nats
mark(zeros) -> a__zeros
mark(head(X)) -> a__head(mark(X))
mark(tail(X)) -> a__tail(mark(X))
mark(nil) -> nil
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(0') -> 0'
a__incr(X) -> incr(X)
a__adx(X) -> adx(X)
a__nats -> nats
a__zeros -> zeros
a__head(X) -> head(X)
a__tail(X) -> tail(X)

Types:
a__incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
nil :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
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
s :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
mark :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
0' :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
hole_nil:cons:s:incr:adx:0':zeros:nats:head:tail1_0 :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0 :: Nat -> nil:cons:s:incr:adx:0':zeros:nats:head:tail

----------------------------------------

(5) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
a__incr, mark, a__adx, a__nats, a__head, a__tail

They will be analysed ascendingly in the following order:
a__incr = mark
a__incr = a__adx
a__incr = a__nats
a__incr = a__head
a__incr = a__tail
mark = a__adx
mark = a__nats
mark = a__head
mark = a__tail
a__adx = a__nats
a__adx = a__head
a__adx = a__tail
a__nats = a__head
a__nats = a__tail
a__head = a__tail

----------------------------------------

(6)
Obligation:
TRS:
Rules:
a__incr(nil) -> nil
a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L))
a__adx(nil) -> nil
a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L)))
a__nats -> a__adx(a__zeros)
a__zeros -> cons(0', zeros)
a__head(cons(X, L)) -> mark(X)
a__tail(cons(X, L)) -> mark(L)
mark(incr(X)) -> a__incr(mark(X))
mark(adx(X)) -> a__adx(mark(X))
mark(nats) -> a__nats
mark(zeros) -> a__zeros
mark(head(X)) -> a__head(mark(X))
mark(tail(X)) -> a__tail(mark(X))
mark(nil) -> nil
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(0') -> 0'
a__incr(X) -> incr(X)
a__adx(X) -> adx(X)
a__nats -> nats
a__zeros -> zeros
a__head(X) -> head(X)
a__tail(X) -> tail(X)

Types:
a__incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
nil :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
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
s :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
mark :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
0' :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
hole_nil:cons:s:incr:adx:0':zeros:nats:head:tail1_0 :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0 :: Nat -> nil:cons:s:incr:adx:0':zeros:nats:head:tail


Generator Equations:
gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(0) <=> nil
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)


The following defined symbols remain to be analysed:
mark, a__incr, a__adx, a__nats, a__head, a__tail

They will be analysed ascendingly in the following order:
a__incr = mark
a__incr = a__adx
a__incr = a__nats
a__incr = a__head
a__incr = a__tail
mark = a__adx
mark = a__nats
mark = a__head
mark = a__tail
a__adx = a__nats
a__adx = a__head
a__adx = a__tail
a__nats = a__head
a__nats = a__tail
a__head = a__tail

----------------------------------------

(7) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
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)

Induction Base:
mark(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(0)) ->_R^Omega(1)
nil

Induction Step:
mark(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(+(n4_0, 1))) ->_R^Omega(1)
cons(mark(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(n4_0)), nil) ->_IH
cons(gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(c5_0), nil)

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(8)
Complex Obligation (BEST)

----------------------------------------

(9)
Obligation:
Proved the lower bound n^1 for the following obligation:

TRS:
Rules:
a__incr(nil) -> nil
a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L))
a__adx(nil) -> nil
a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L)))
a__nats -> a__adx(a__zeros)
a__zeros -> cons(0', zeros)
a__head(cons(X, L)) -> mark(X)
a__tail(cons(X, L)) -> mark(L)
mark(incr(X)) -> a__incr(mark(X))
mark(adx(X)) -> a__adx(mark(X))
mark(nats) -> a__nats
mark(zeros) -> a__zeros
mark(head(X)) -> a__head(mark(X))
mark(tail(X)) -> a__tail(mark(X))
mark(nil) -> nil
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(0') -> 0'
a__incr(X) -> incr(X)
a__adx(X) -> adx(X)
a__nats -> nats
a__zeros -> zeros
a__head(X) -> head(X)
a__tail(X) -> tail(X)

Types:
a__incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
nil :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
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
s :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
mark :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
0' :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
hole_nil:cons:s:incr:adx:0':zeros:nats:head:tail1_0 :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0 :: Nat -> nil:cons:s:incr:adx:0':zeros:nats:head:tail


Generator Equations:
gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(0) <=> nil
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)


The following defined symbols remain to be analysed:
mark, a__incr, a__adx, a__nats, a__head, a__tail

They will be analysed ascendingly in the following order:
a__incr = mark
a__incr = a__adx
a__incr = a__nats
a__incr = a__head
a__incr = a__tail
mark = a__adx
mark = a__nats
mark = a__head
mark = a__tail
a__adx = a__nats
a__adx = a__head
a__adx = a__tail
a__nats = a__head
a__nats = a__tail
a__head = a__tail

----------------------------------------

(10) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(11)
BOUNDS(n^1, INF)

----------------------------------------

(12)
Obligation:
TRS:
Rules:
a__incr(nil) -> nil
a__incr(cons(X, L)) -> cons(s(mark(X)), incr(L))
a__adx(nil) -> nil
a__adx(cons(X, L)) -> a__incr(cons(mark(X), adx(L)))
a__nats -> a__adx(a__zeros)
a__zeros -> cons(0', zeros)
a__head(cons(X, L)) -> mark(X)
a__tail(cons(X, L)) -> mark(L)
mark(incr(X)) -> a__incr(mark(X))
mark(adx(X)) -> a__adx(mark(X))
mark(nats) -> a__nats
mark(zeros) -> a__zeros
mark(head(X)) -> a__head(mark(X))
mark(tail(X)) -> a__tail(mark(X))
mark(nil) -> nil
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(0') -> 0'
a__incr(X) -> incr(X)
a__adx(X) -> adx(X)
a__nats -> nats
a__zeros -> zeros
a__head(X) -> head(X)
a__tail(X) -> tail(X)

Types:
a__incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
nil :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
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
s :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
mark :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
incr :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
adx :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
0' :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
zeros :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
a__tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
nats :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
head :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
tail :: nil:cons:s:incr:adx:0':zeros:nats:head:tail -> nil:cons:s:incr:adx:0':zeros:nats:head:tail
hole_nil:cons:s:incr:adx:0':zeros:nats:head:tail1_0 :: nil:cons:s:incr:adx:0':zeros:nats:head:tail
gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0 :: Nat -> nil:cons:s:incr:adx:0':zeros:nats:head:tail


Lemmas:
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)


Generator Equations:
gen_nil:cons:s:incr:adx:0':zeros:nats:head:tail2_0(0) <=> nil
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)


The following defined symbols remain to be analysed:
a__incr, a__adx, a__nats, a__head, a__tail

They will be analysed ascendingly in the following order:
a__incr = mark
a__incr = a__adx
a__incr = a__nats
a__incr = a__head
a__incr = a__tail
mark = a__adx
mark = a__nats
mark = a__head
mark = a__tail
a__adx = a__nats
a__adx = a__head
a__adx = a__tail
a__nats = a__head
a__nats = a__tail
a__head = a__tail