/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), 333 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:

   U11(tt, V2) -> U12(isNat(activate(V2)))
   U12(tt) -> tt
   U21(tt) -> tt
   U31(tt, N) -> activate(N)
   U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N))
   U42(tt, M, N) -> s(plus(activate(N), activate(M)))
   isNat(n__0) -> tt
   isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2))
   isNat(n__s(V1)) -> U21(isNat(activate(V1)))
   plus(N, 0) -> U31(isNat(N), N)
   plus(N, s(M)) -> U41(isNat(M), M, N)
   0 -> n__0
   plus(X1, X2) -> n__plus(X1, X2)
   s(X) -> n__s(X)
   activate(n__0) -> 0
   activate(n__plus(X1, X2)) -> plus(X1, X2)
   activate(n__s(X)) -> s(X)
   activate(X) -> 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:

   U11(tt, V2) -> U12(isNat(activate(V2)))
   U12(tt) -> tt
   U21(tt) -> tt
   U31(tt, N) -> activate(N)
   U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N))
   U42(tt, M, N) -> s(plus(activate(N), activate(M)))
   isNat(n__0) -> tt
   isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2))
   isNat(n__s(V1)) -> U21(isNat(activate(V1)))
   plus(N, 0') -> U31(isNat(N), N)
   plus(N, s(M)) -> U41(isNat(M), M, N)
   0' -> n__0
   plus(X1, X2) -> n__plus(X1, X2)
   s(X) -> n__s(X)
   activate(n__0) -> 0'
   activate(n__plus(X1, X2)) -> plus(X1, X2)
   activate(n__s(X)) -> s(X)
   activate(X) -> X

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

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

(4)
Obligation:
TRS:
Rules:
U11(tt, V2) -> U12(isNat(activate(V2)))
U12(tt) -> tt
U21(tt) -> tt
U31(tt, N) -> activate(N)
U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N))
U42(tt, M, N) -> s(plus(activate(N), activate(M)))
isNat(n__0) -> tt
isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2))
isNat(n__s(V1)) -> U21(isNat(activate(V1)))
plus(N, 0') -> U31(isNat(N), N)
plus(N, s(M)) -> U41(isNat(M), M, N)
0' -> n__0
plus(X1, X2) -> n__plus(X1, X2)
s(X) -> n__s(X)
activate(n__0) -> 0'
activate(n__plus(X1, X2)) -> plus(X1, X2)
activate(n__s(X)) -> s(X)
activate(X) -> X

Types:
U11 :: tt -> n__0:n__plus:n__s -> tt
tt :: tt
U12 :: tt -> tt
isNat :: n__0:n__plus:n__s -> tt
activate :: n__0:n__plus:n__s -> n__0:n__plus:n__s
U21 :: tt -> tt
U31 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s
U41 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
U42 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
s :: n__0:n__plus:n__s -> n__0:n__plus:n__s
plus :: n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
n__0 :: n__0:n__plus:n__s
n__plus :: n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
n__s :: n__0:n__plus:n__s -> n__0:n__plus:n__s
0' :: n__0:n__plus:n__s
hole_tt1_3 :: tt
hole_n__0:n__plus:n__s2_3 :: n__0:n__plus:n__s
gen_n__0:n__plus:n__s3_3 :: Nat -> n__0:n__plus:n__s

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

(5) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
isNat, activate, U31, plus

They will be analysed ascendingly in the following order:
isNat = activate
isNat = U31
isNat = plus
activate = U31
activate = plus
U31 = plus

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

(6)
Obligation:
TRS:
Rules:
U11(tt, V2) -> U12(isNat(activate(V2)))
U12(tt) -> tt
U21(tt) -> tt
U31(tt, N) -> activate(N)
U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N))
U42(tt, M, N) -> s(plus(activate(N), activate(M)))
isNat(n__0) -> tt
isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2))
isNat(n__s(V1)) -> U21(isNat(activate(V1)))
plus(N, 0') -> U31(isNat(N), N)
plus(N, s(M)) -> U41(isNat(M), M, N)
0' -> n__0
plus(X1, X2) -> n__plus(X1, X2)
s(X) -> n__s(X)
activate(n__0) -> 0'
activate(n__plus(X1, X2)) -> plus(X1, X2)
activate(n__s(X)) -> s(X)
activate(X) -> X

Types:
U11 :: tt -> n__0:n__plus:n__s -> tt
tt :: tt
U12 :: tt -> tt
isNat :: n__0:n__plus:n__s -> tt
activate :: n__0:n__plus:n__s -> n__0:n__plus:n__s
U21 :: tt -> tt
U31 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s
U41 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
U42 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
s :: n__0:n__plus:n__s -> n__0:n__plus:n__s
plus :: n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
n__0 :: n__0:n__plus:n__s
n__plus :: n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
n__s :: n__0:n__plus:n__s -> n__0:n__plus:n__s
0' :: n__0:n__plus:n__s
hole_tt1_3 :: tt
hole_n__0:n__plus:n__s2_3 :: n__0:n__plus:n__s
gen_n__0:n__plus:n__s3_3 :: Nat -> n__0:n__plus:n__s


Generator Equations:
gen_n__0:n__plus:n__s3_3(0) <=> n__0
gen_n__0:n__plus:n__s3_3(+(x, 1)) <=> n__plus(gen_n__0:n__plus:n__s3_3(x), n__0)


The following defined symbols remain to be analysed:
activate, isNat, U31, plus

They will be analysed ascendingly in the following order:
isNat = activate
isNat = U31
isNat = plus
activate = U31
activate = plus
U31 = plus

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

(7) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
isNat(gen_n__0:n__plus:n__s3_3(n155_3)) -> tt, rt in Omega(1 + n155_3)

Induction Base:
isNat(gen_n__0:n__plus:n__s3_3(0)) ->_R^Omega(1)
tt

Induction Step:
isNat(gen_n__0:n__plus:n__s3_3(+(n155_3, 1))) ->_R^Omega(1)
U11(isNat(activate(gen_n__0:n__plus:n__s3_3(n155_3))), activate(n__0)) ->_R^Omega(1)
U11(isNat(gen_n__0:n__plus:n__s3_3(n155_3)), activate(n__0)) ->_IH
U11(tt, activate(n__0)) ->_R^Omega(1)
U11(tt, n__0) ->_R^Omega(1)
U12(isNat(activate(n__0))) ->_R^Omega(1)
U12(isNat(n__0)) ->_R^Omega(1)
U12(tt) ->_R^Omega(1)
tt

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:
U11(tt, V2) -> U12(isNat(activate(V2)))
U12(tt) -> tt
U21(tt) -> tt
U31(tt, N) -> activate(N)
U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N))
U42(tt, M, N) -> s(plus(activate(N), activate(M)))
isNat(n__0) -> tt
isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2))
isNat(n__s(V1)) -> U21(isNat(activate(V1)))
plus(N, 0') -> U31(isNat(N), N)
plus(N, s(M)) -> U41(isNat(M), M, N)
0' -> n__0
plus(X1, X2) -> n__plus(X1, X2)
s(X) -> n__s(X)
activate(n__0) -> 0'
activate(n__plus(X1, X2)) -> plus(X1, X2)
activate(n__s(X)) -> s(X)
activate(X) -> X

Types:
U11 :: tt -> n__0:n__plus:n__s -> tt
tt :: tt
U12 :: tt -> tt
isNat :: n__0:n__plus:n__s -> tt
activate :: n__0:n__plus:n__s -> n__0:n__plus:n__s
U21 :: tt -> tt
U31 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s
U41 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
U42 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
s :: n__0:n__plus:n__s -> n__0:n__plus:n__s
plus :: n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
n__0 :: n__0:n__plus:n__s
n__plus :: n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
n__s :: n__0:n__plus:n__s -> n__0:n__plus:n__s
0' :: n__0:n__plus:n__s
hole_tt1_3 :: tt
hole_n__0:n__plus:n__s2_3 :: n__0:n__plus:n__s
gen_n__0:n__plus:n__s3_3 :: Nat -> n__0:n__plus:n__s


Generator Equations:
gen_n__0:n__plus:n__s3_3(0) <=> n__0
gen_n__0:n__plus:n__s3_3(+(x, 1)) <=> n__plus(gen_n__0:n__plus:n__s3_3(x), n__0)


The following defined symbols remain to be analysed:
isNat

They will be analysed ascendingly in the following order:
isNat = activate
isNat = U31
isNat = plus
activate = U31
activate = plus
U31 = plus

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

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

(11)
BOUNDS(n^1, INF)

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

(12)
Obligation:
TRS:
Rules:
U11(tt, V2) -> U12(isNat(activate(V2)))
U12(tt) -> tt
U21(tt) -> tt
U31(tt, N) -> activate(N)
U41(tt, M, N) -> U42(isNat(activate(N)), activate(M), activate(N))
U42(tt, M, N) -> s(plus(activate(N), activate(M)))
isNat(n__0) -> tt
isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2))
isNat(n__s(V1)) -> U21(isNat(activate(V1)))
plus(N, 0') -> U31(isNat(N), N)
plus(N, s(M)) -> U41(isNat(M), M, N)
0' -> n__0
plus(X1, X2) -> n__plus(X1, X2)
s(X) -> n__s(X)
activate(n__0) -> 0'
activate(n__plus(X1, X2)) -> plus(X1, X2)
activate(n__s(X)) -> s(X)
activate(X) -> X

Types:
U11 :: tt -> n__0:n__plus:n__s -> tt
tt :: tt
U12 :: tt -> tt
isNat :: n__0:n__plus:n__s -> tt
activate :: n__0:n__plus:n__s -> n__0:n__plus:n__s
U21 :: tt -> tt
U31 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s
U41 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
U42 :: tt -> n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
s :: n__0:n__plus:n__s -> n__0:n__plus:n__s
plus :: n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
n__0 :: n__0:n__plus:n__s
n__plus :: n__0:n__plus:n__s -> n__0:n__plus:n__s -> n__0:n__plus:n__s
n__s :: n__0:n__plus:n__s -> n__0:n__plus:n__s
0' :: n__0:n__plus:n__s
hole_tt1_3 :: tt
hole_n__0:n__plus:n__s2_3 :: n__0:n__plus:n__s
gen_n__0:n__plus:n__s3_3 :: Nat -> n__0:n__plus:n__s


Lemmas:
isNat(gen_n__0:n__plus:n__s3_3(n155_3)) -> tt, rt in Omega(1 + n155_3)


Generator Equations:
gen_n__0:n__plus:n__s3_3(0) <=> n__0
gen_n__0:n__plus:n__s3_3(+(x, 1)) <=> n__plus(gen_n__0:n__plus:n__s3_3(x), n__0)


The following defined symbols remain to be analysed:
activate, U31, plus

They will be analysed ascendingly in the following order:
isNat = activate
isNat = U31
isNat = plus
activate = U31
activate = plus
U31 = plus