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


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


WORST_CASE(Omega(n^1), ?)
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) CpxTRS
(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(2) TRS for Loop Detection
(3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
(4) BEST
    (5) proven lower bound
        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
        (7) BOUNDS(n^1, INF)
    (8) TRS for Loop Detection


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

(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:

   active(and(tt, T)) -> mark(T)
   active(isNatIList(IL)) -> mark(isNatList(IL))
   active(isNat(0)) -> mark(tt)
   active(isNat(s(N))) -> mark(isNat(N))
   active(isNat(length(L))) -> mark(isNatList(L))
   active(isNatIList(zeros)) -> mark(tt)
   active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL)))
   active(isNatList(nil)) -> mark(tt)
   active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L)))
   active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL)))
   active(zeros) -> mark(cons(0, zeros))
   active(take(0, IL)) -> mark(uTake1(isNatIList(IL)))
   active(uTake1(tt)) -> mark(nil)
   active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL))
   active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL)))
   active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L))
   active(uLength(tt, L)) -> mark(s(length(L)))
   active(and(X1, X2)) -> and(active(X1), X2)
   active(and(X1, X2)) -> and(X1, active(X2))
   active(s(X)) -> s(active(X))
   active(length(X)) -> length(active(X))
   active(cons(X1, X2)) -> cons(active(X1), X2)
   active(take(X1, X2)) -> take(active(X1), X2)
   active(take(X1, X2)) -> take(X1, active(X2))
   active(uTake1(X)) -> uTake1(active(X))
   active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4)
   active(uLength(X1, X2)) -> uLength(active(X1), X2)
   and(mark(X1), X2) -> mark(and(X1, X2))
   and(X1, mark(X2)) -> mark(and(X1, X2))
   s(mark(X)) -> mark(s(X))
   length(mark(X)) -> mark(length(X))
   cons(mark(X1), X2) -> mark(cons(X1, X2))
   take(mark(X1), X2) -> mark(take(X1, X2))
   take(X1, mark(X2)) -> mark(take(X1, X2))
   uTake1(mark(X)) -> mark(uTake1(X))
   uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4))
   uLength(mark(X1), X2) -> mark(uLength(X1, X2))
   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
   proper(tt) -> ok(tt)
   proper(isNatIList(X)) -> isNatIList(proper(X))
   proper(isNatList(X)) -> isNatList(proper(X))
   proper(isNat(X)) -> isNat(proper(X))
   proper(0) -> ok(0)
   proper(s(X)) -> s(proper(X))
   proper(length(X)) -> length(proper(X))
   proper(zeros) -> ok(zeros)
   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
   proper(nil) -> ok(nil)
   proper(take(X1, X2)) -> take(proper(X1), proper(X2))
   proper(uTake1(X)) -> uTake1(proper(X))
   proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4))
   proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2))
   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
   isNatIList(ok(X)) -> ok(isNatIList(X))
   isNatList(ok(X)) -> ok(isNatList(X))
   isNat(ok(X)) -> ok(isNat(X))
   s(ok(X)) -> ok(s(X))
   length(ok(X)) -> ok(length(X))
   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
   take(ok(X1), ok(X2)) -> ok(take(X1, X2))
   uTake1(ok(X)) -> ok(uTake1(X))
   uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4))
   uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2))
   top(mark(X)) -> top(proper(X))
   top(ok(X)) -> top(active(X))

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

(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

(2)
Obligation:
Analyzing the following TRS for decreasing loops:

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:

   active(and(tt, T)) -> mark(T)
   active(isNatIList(IL)) -> mark(isNatList(IL))
   active(isNat(0)) -> mark(tt)
   active(isNat(s(N))) -> mark(isNat(N))
   active(isNat(length(L))) -> mark(isNatList(L))
   active(isNatIList(zeros)) -> mark(tt)
   active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL)))
   active(isNatList(nil)) -> mark(tt)
   active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L)))
   active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL)))
   active(zeros) -> mark(cons(0, zeros))
   active(take(0, IL)) -> mark(uTake1(isNatIList(IL)))
   active(uTake1(tt)) -> mark(nil)
   active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL))
   active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL)))
   active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L))
   active(uLength(tt, L)) -> mark(s(length(L)))
   active(and(X1, X2)) -> and(active(X1), X2)
   active(and(X1, X2)) -> and(X1, active(X2))
   active(s(X)) -> s(active(X))
   active(length(X)) -> length(active(X))
   active(cons(X1, X2)) -> cons(active(X1), X2)
   active(take(X1, X2)) -> take(active(X1), X2)
   active(take(X1, X2)) -> take(X1, active(X2))
   active(uTake1(X)) -> uTake1(active(X))
   active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4)
   active(uLength(X1, X2)) -> uLength(active(X1), X2)
   and(mark(X1), X2) -> mark(and(X1, X2))
   and(X1, mark(X2)) -> mark(and(X1, X2))
   s(mark(X)) -> mark(s(X))
   length(mark(X)) -> mark(length(X))
   cons(mark(X1), X2) -> mark(cons(X1, X2))
   take(mark(X1), X2) -> mark(take(X1, X2))
   take(X1, mark(X2)) -> mark(take(X1, X2))
   uTake1(mark(X)) -> mark(uTake1(X))
   uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4))
   uLength(mark(X1), X2) -> mark(uLength(X1, X2))
   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
   proper(tt) -> ok(tt)
   proper(isNatIList(X)) -> isNatIList(proper(X))
   proper(isNatList(X)) -> isNatList(proper(X))
   proper(isNat(X)) -> isNat(proper(X))
   proper(0) -> ok(0)
   proper(s(X)) -> s(proper(X))
   proper(length(X)) -> length(proper(X))
   proper(zeros) -> ok(zeros)
   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
   proper(nil) -> ok(nil)
   proper(take(X1, X2)) -> take(proper(X1), proper(X2))
   proper(uTake1(X)) -> uTake1(proper(X))
   proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4))
   proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2))
   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
   isNatIList(ok(X)) -> ok(isNatIList(X))
   isNatList(ok(X)) -> ok(isNatList(X))
   isNat(ok(X)) -> ok(isNat(X))
   s(ok(X)) -> ok(s(X))
   length(ok(X)) -> ok(length(X))
   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
   take(ok(X1), ok(X2)) -> ok(take(X1, X2))
   uTake1(ok(X)) -> ok(uTake1(X))
   uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4))
   uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2))
   top(mark(X)) -> top(proper(X))
   top(ok(X)) -> top(active(X))

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

(3) DecreasingLoopProof (LOWER BOUND(ID))
The following loop(s) give(s) rise to the lower bound Omega(n^1):

The rewrite sequence

uTake2(mark(X1), X2, X3, X4) ->^+ mark(uTake2(X1, X2, X3, X4))

gives rise to a decreasing loop by considering the right hand sides subterm at position [0].

The pumping substitution is [X1 / mark(X1)].

The result substitution is [ ].




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

(4)
Complex Obligation (BEST)

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

(5)
Obligation:
Proved the lower bound n^1 for the following 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:

   active(and(tt, T)) -> mark(T)
   active(isNatIList(IL)) -> mark(isNatList(IL))
   active(isNat(0)) -> mark(tt)
   active(isNat(s(N))) -> mark(isNat(N))
   active(isNat(length(L))) -> mark(isNatList(L))
   active(isNatIList(zeros)) -> mark(tt)
   active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL)))
   active(isNatList(nil)) -> mark(tt)
   active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L)))
   active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL)))
   active(zeros) -> mark(cons(0, zeros))
   active(take(0, IL)) -> mark(uTake1(isNatIList(IL)))
   active(uTake1(tt)) -> mark(nil)
   active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL))
   active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL)))
   active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L))
   active(uLength(tt, L)) -> mark(s(length(L)))
   active(and(X1, X2)) -> and(active(X1), X2)
   active(and(X1, X2)) -> and(X1, active(X2))
   active(s(X)) -> s(active(X))
   active(length(X)) -> length(active(X))
   active(cons(X1, X2)) -> cons(active(X1), X2)
   active(take(X1, X2)) -> take(active(X1), X2)
   active(take(X1, X2)) -> take(X1, active(X2))
   active(uTake1(X)) -> uTake1(active(X))
   active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4)
   active(uLength(X1, X2)) -> uLength(active(X1), X2)
   and(mark(X1), X2) -> mark(and(X1, X2))
   and(X1, mark(X2)) -> mark(and(X1, X2))
   s(mark(X)) -> mark(s(X))
   length(mark(X)) -> mark(length(X))
   cons(mark(X1), X2) -> mark(cons(X1, X2))
   take(mark(X1), X2) -> mark(take(X1, X2))
   take(X1, mark(X2)) -> mark(take(X1, X2))
   uTake1(mark(X)) -> mark(uTake1(X))
   uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4))
   uLength(mark(X1), X2) -> mark(uLength(X1, X2))
   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
   proper(tt) -> ok(tt)
   proper(isNatIList(X)) -> isNatIList(proper(X))
   proper(isNatList(X)) -> isNatList(proper(X))
   proper(isNat(X)) -> isNat(proper(X))
   proper(0) -> ok(0)
   proper(s(X)) -> s(proper(X))
   proper(length(X)) -> length(proper(X))
   proper(zeros) -> ok(zeros)
   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
   proper(nil) -> ok(nil)
   proper(take(X1, X2)) -> take(proper(X1), proper(X2))
   proper(uTake1(X)) -> uTake1(proper(X))
   proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4))
   proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2))
   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
   isNatIList(ok(X)) -> ok(isNatIList(X))
   isNatList(ok(X)) -> ok(isNatList(X))
   isNat(ok(X)) -> ok(isNat(X))
   s(ok(X)) -> ok(s(X))
   length(ok(X)) -> ok(length(X))
   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
   take(ok(X1), ok(X2)) -> ok(take(X1, X2))
   uTake1(ok(X)) -> ok(uTake1(X))
   uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4))
   uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2))
   top(mark(X)) -> top(proper(X))
   top(ok(X)) -> top(active(X))

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

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

(7)
BOUNDS(n^1, INF)

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

(8)
Obligation:
Analyzing the following TRS for decreasing loops:

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:

   active(and(tt, T)) -> mark(T)
   active(isNatIList(IL)) -> mark(isNatList(IL))
   active(isNat(0)) -> mark(tt)
   active(isNat(s(N))) -> mark(isNat(N))
   active(isNat(length(L))) -> mark(isNatList(L))
   active(isNatIList(zeros)) -> mark(tt)
   active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL)))
   active(isNatList(nil)) -> mark(tt)
   active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L)))
   active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL)))
   active(zeros) -> mark(cons(0, zeros))
   active(take(0, IL)) -> mark(uTake1(isNatIList(IL)))
   active(uTake1(tt)) -> mark(nil)
   active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL))
   active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL)))
   active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L))
   active(uLength(tt, L)) -> mark(s(length(L)))
   active(and(X1, X2)) -> and(active(X1), X2)
   active(and(X1, X2)) -> and(X1, active(X2))
   active(s(X)) -> s(active(X))
   active(length(X)) -> length(active(X))
   active(cons(X1, X2)) -> cons(active(X1), X2)
   active(take(X1, X2)) -> take(active(X1), X2)
   active(take(X1, X2)) -> take(X1, active(X2))
   active(uTake1(X)) -> uTake1(active(X))
   active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4)
   active(uLength(X1, X2)) -> uLength(active(X1), X2)
   and(mark(X1), X2) -> mark(and(X1, X2))
   and(X1, mark(X2)) -> mark(and(X1, X2))
   s(mark(X)) -> mark(s(X))
   length(mark(X)) -> mark(length(X))
   cons(mark(X1), X2) -> mark(cons(X1, X2))
   take(mark(X1), X2) -> mark(take(X1, X2))
   take(X1, mark(X2)) -> mark(take(X1, X2))
   uTake1(mark(X)) -> mark(uTake1(X))
   uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4))
   uLength(mark(X1), X2) -> mark(uLength(X1, X2))
   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
   proper(tt) -> ok(tt)
   proper(isNatIList(X)) -> isNatIList(proper(X))
   proper(isNatList(X)) -> isNatList(proper(X))
   proper(isNat(X)) -> isNat(proper(X))
   proper(0) -> ok(0)
   proper(s(X)) -> s(proper(X))
   proper(length(X)) -> length(proper(X))
   proper(zeros) -> ok(zeros)
   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
   proper(nil) -> ok(nil)
   proper(take(X1, X2)) -> take(proper(X1), proper(X2))
   proper(uTake1(X)) -> uTake1(proper(X))
   proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4))
   proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2))
   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
   isNatIList(ok(X)) -> ok(isNatIList(X))
   isNatList(ok(X)) -> ok(isNatList(X))
   isNat(ok(X)) -> ok(isNat(X))
   s(ok(X)) -> ok(s(X))
   length(ok(X)) -> ok(length(X))
   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
   take(ok(X1), ok(X2)) -> ok(take(X1, X2))
   uTake1(ok(X)) -> ok(uTake1(X))
   uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4))
   uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2))
   top(mark(X)) -> top(proper(X))
   top(ok(X)) -> top(active(X))

S is empty.
Rewrite Strategy: FULL