/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: 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), 313 ms]
(8) BEST
    (9) proven lower bound
        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
        (11) BOUNDS(n^1, INF)
    (12) typed CpxTrs
        (13) RewriteLemmaProof [LOWER BOUND(ID), 4619 ms]
        (14) typed CpxTrs
        (15) RewriteLemmaProof [LOWER BOUND(ID), 37 ms]
        (16) typed CpxTrs
        (17) RewriteLemmaProof [LOWER BOUND(ID), 0 ms]
        (18) 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:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

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:

   p(s(N)) -> N
   +'(N, 0') -> N
   +'(s(N), s(M)) -> s(s(+'(N, M)))
   *'(N, 0') -> 0'
   *'(s(N), s(M)) -> s(+'(N, +'(M, *'(N, M))))
   gt(0', M) -> False
   gt(NzN, 0') -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0') -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0', N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0')
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0'
   gcd(0', N) -> 0'
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

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

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

(4)
Obligation:
TRS:
Rules:
p(s(N)) -> N
+'(N, 0') -> N
+'(s(N), s(M)) -> s(s(+'(N, M)))
*'(N, 0') -> 0'
*'(s(N), s(M)) -> s(+'(N, +'(M, *'(N, M))))
gt(0', M) -> False
gt(NzN, 0') -> u_4(is_NzNat(NzN))
u_4(True) -> True
is_NzNat(0') -> False
is_NzNat(s(N)) -> True
gt(s(N), s(M)) -> gt(N, M)
lt(N, M) -> gt(M, N)
d(0', N) -> N
d(s(N), s(M)) -> d(N, M)
quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
quot(NzM, NzM) -> u_01(is_NzNat(NzM))
u_01(True) -> s(0')
quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
u_21(True, NzM, N) -> u_2(gt(NzM, N))
u_2(True) -> 0'
gcd(0', N) -> 0'
gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
u_02(True, NzM) -> NzM
gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

Types:
p :: s:0' -> s:0'
s :: s:0' -> s:0'
+' :: s:0' -> s:0' -> s:0'
0' :: s:0'
*' :: s:0' -> s:0' -> s:0'
gt :: s:0' -> s:0' -> False:True
False :: False:True
u_4 :: False:True -> False:True
is_NzNat :: s:0' -> False:True
True :: False:True
lt :: s:0' -> s:0' -> False:True
d :: s:0' -> s:0' -> s:0'
quot :: s:0' -> s:0' -> s:0'
u_11 :: False:True -> s:0' -> s:0' -> s:0'
u_1 :: False:True -> s:0' -> s:0' -> s:0'
u_01 :: False:True -> s:0'
u_21 :: False:True -> s:0' -> s:0' -> s:0'
u_2 :: False:True -> s:0'
gcd :: s:0' -> s:0' -> s:0'
u_02 :: False:True -> s:0' -> s:0'
u_31 :: False:True -> False:True -> s:0' -> s:0' -> s:0'
u_3 :: False:True -> s:0' -> s:0' -> s:0'
hole_s:0'1_0 :: s:0'
hole_False:True2_0 :: False:True
gen_s:0'3_0 :: Nat -> s:0'

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

(5) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
+', *', gt, d, quot, gcd

They will be analysed ascendingly in the following order:
+' < *'
gt < quot
gt < gcd
d < quot
d < gcd

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

(6)
Obligation:
TRS:
Rules:
p(s(N)) -> N
+'(N, 0') -> N
+'(s(N), s(M)) -> s(s(+'(N, M)))
*'(N, 0') -> 0'
*'(s(N), s(M)) -> s(+'(N, +'(M, *'(N, M))))
gt(0', M) -> False
gt(NzN, 0') -> u_4(is_NzNat(NzN))
u_4(True) -> True
is_NzNat(0') -> False
is_NzNat(s(N)) -> True
gt(s(N), s(M)) -> gt(N, M)
lt(N, M) -> gt(M, N)
d(0', N) -> N
d(s(N), s(M)) -> d(N, M)
quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
quot(NzM, NzM) -> u_01(is_NzNat(NzM))
u_01(True) -> s(0')
quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
u_21(True, NzM, N) -> u_2(gt(NzM, N))
u_2(True) -> 0'
gcd(0', N) -> 0'
gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
u_02(True, NzM) -> NzM
gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

Types:
p :: s:0' -> s:0'
s :: s:0' -> s:0'
+' :: s:0' -> s:0' -> s:0'
0' :: s:0'
*' :: s:0' -> s:0' -> s:0'
gt :: s:0' -> s:0' -> False:True
False :: False:True
u_4 :: False:True -> False:True
is_NzNat :: s:0' -> False:True
True :: False:True
lt :: s:0' -> s:0' -> False:True
d :: s:0' -> s:0' -> s:0'
quot :: s:0' -> s:0' -> s:0'
u_11 :: False:True -> s:0' -> s:0' -> s:0'
u_1 :: False:True -> s:0' -> s:0' -> s:0'
u_01 :: False:True -> s:0'
u_21 :: False:True -> s:0' -> s:0' -> s:0'
u_2 :: False:True -> s:0'
gcd :: s:0' -> s:0' -> s:0'
u_02 :: False:True -> s:0' -> s:0'
u_31 :: False:True -> False:True -> s:0' -> s:0' -> s:0'
u_3 :: False:True -> s:0' -> s:0' -> s:0'
hole_s:0'1_0 :: s:0'
hole_False:True2_0 :: False:True
gen_s:0'3_0 :: Nat -> s:0'


Generator Equations:
gen_s:0'3_0(0) <=> 0'
gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x))


The following defined symbols remain to be analysed:
+', *', gt, d, quot, gcd

They will be analysed ascendingly in the following order:
+' < *'
gt < quot
gt < gcd
d < quot
d < gcd

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

(7) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
+'(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> gen_s:0'3_0(*(2, n5_0)), rt in Omega(1 + n5_0)

Induction Base:
+'(gen_s:0'3_0(0), gen_s:0'3_0(0)) ->_R^Omega(1)
gen_s:0'3_0(0)

Induction Step:
+'(gen_s:0'3_0(+(n5_0, 1)), gen_s:0'3_0(+(n5_0, 1))) ->_R^Omega(1)
s(s(+'(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)))) ->_IH
s(s(gen_s:0'3_0(*(2, c6_0))))

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:
p(s(N)) -> N
+'(N, 0') -> N
+'(s(N), s(M)) -> s(s(+'(N, M)))
*'(N, 0') -> 0'
*'(s(N), s(M)) -> s(+'(N, +'(M, *'(N, M))))
gt(0', M) -> False
gt(NzN, 0') -> u_4(is_NzNat(NzN))
u_4(True) -> True
is_NzNat(0') -> False
is_NzNat(s(N)) -> True
gt(s(N), s(M)) -> gt(N, M)
lt(N, M) -> gt(M, N)
d(0', N) -> N
d(s(N), s(M)) -> d(N, M)
quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
quot(NzM, NzM) -> u_01(is_NzNat(NzM))
u_01(True) -> s(0')
quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
u_21(True, NzM, N) -> u_2(gt(NzM, N))
u_2(True) -> 0'
gcd(0', N) -> 0'
gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
u_02(True, NzM) -> NzM
gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

Types:
p :: s:0' -> s:0'
s :: s:0' -> s:0'
+' :: s:0' -> s:0' -> s:0'
0' :: s:0'
*' :: s:0' -> s:0' -> s:0'
gt :: s:0' -> s:0' -> False:True
False :: False:True
u_4 :: False:True -> False:True
is_NzNat :: s:0' -> False:True
True :: False:True
lt :: s:0' -> s:0' -> False:True
d :: s:0' -> s:0' -> s:0'
quot :: s:0' -> s:0' -> s:0'
u_11 :: False:True -> s:0' -> s:0' -> s:0'
u_1 :: False:True -> s:0' -> s:0' -> s:0'
u_01 :: False:True -> s:0'
u_21 :: False:True -> s:0' -> s:0' -> s:0'
u_2 :: False:True -> s:0'
gcd :: s:0' -> s:0' -> s:0'
u_02 :: False:True -> s:0' -> s:0'
u_31 :: False:True -> False:True -> s:0' -> s:0' -> s:0'
u_3 :: False:True -> s:0' -> s:0' -> s:0'
hole_s:0'1_0 :: s:0'
hole_False:True2_0 :: False:True
gen_s:0'3_0 :: Nat -> s:0'


Generator Equations:
gen_s:0'3_0(0) <=> 0'
gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x))


The following defined symbols remain to be analysed:
+', *', gt, d, quot, gcd

They will be analysed ascendingly in the following order:
+' < *'
gt < quot
gt < gcd
d < quot
d < gcd

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

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

(11)
BOUNDS(n^1, INF)

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

(12)
Obligation:
TRS:
Rules:
p(s(N)) -> N
+'(N, 0') -> N
+'(s(N), s(M)) -> s(s(+'(N, M)))
*'(N, 0') -> 0'
*'(s(N), s(M)) -> s(+'(N, +'(M, *'(N, M))))
gt(0', M) -> False
gt(NzN, 0') -> u_4(is_NzNat(NzN))
u_4(True) -> True
is_NzNat(0') -> False
is_NzNat(s(N)) -> True
gt(s(N), s(M)) -> gt(N, M)
lt(N, M) -> gt(M, N)
d(0', N) -> N
d(s(N), s(M)) -> d(N, M)
quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
quot(NzM, NzM) -> u_01(is_NzNat(NzM))
u_01(True) -> s(0')
quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
u_21(True, NzM, N) -> u_2(gt(NzM, N))
u_2(True) -> 0'
gcd(0', N) -> 0'
gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
u_02(True, NzM) -> NzM
gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

Types:
p :: s:0' -> s:0'
s :: s:0' -> s:0'
+' :: s:0' -> s:0' -> s:0'
0' :: s:0'
*' :: s:0' -> s:0' -> s:0'
gt :: s:0' -> s:0' -> False:True
False :: False:True
u_4 :: False:True -> False:True
is_NzNat :: s:0' -> False:True
True :: False:True
lt :: s:0' -> s:0' -> False:True
d :: s:0' -> s:0' -> s:0'
quot :: s:0' -> s:0' -> s:0'
u_11 :: False:True -> s:0' -> s:0' -> s:0'
u_1 :: False:True -> s:0' -> s:0' -> s:0'
u_01 :: False:True -> s:0'
u_21 :: False:True -> s:0' -> s:0' -> s:0'
u_2 :: False:True -> s:0'
gcd :: s:0' -> s:0' -> s:0'
u_02 :: False:True -> s:0' -> s:0'
u_31 :: False:True -> False:True -> s:0' -> s:0' -> s:0'
u_3 :: False:True -> s:0' -> s:0' -> s:0'
hole_s:0'1_0 :: s:0'
hole_False:True2_0 :: False:True
gen_s:0'3_0 :: Nat -> s:0'


Lemmas:
+'(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> gen_s:0'3_0(*(2, n5_0)), rt in Omega(1 + n5_0)


Generator Equations:
gen_s:0'3_0(0) <=> 0'
gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x))


The following defined symbols remain to be analysed:
*', gt, d, quot, gcd

They will be analysed ascendingly in the following order:
gt < quot
gt < gcd
d < quot
d < gcd

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

(13) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
*'(gen_s:0'3_0(+(1, n525_0)), gen_s:0'3_0(+(1, n525_0))) -> *4_0, rt in Omega(n525_0)

Induction Base:
*'(gen_s:0'3_0(+(1, 0)), gen_s:0'3_0(+(1, 0)))

Induction Step:
*'(gen_s:0'3_0(+(1, +(n525_0, 1))), gen_s:0'3_0(+(1, +(n525_0, 1)))) ->_R^Omega(1)
s(+'(gen_s:0'3_0(+(1, n525_0)), +'(gen_s:0'3_0(+(1, n525_0)), *'(gen_s:0'3_0(+(1, n525_0)), gen_s:0'3_0(+(1, n525_0)))))) ->_IH
s(+'(gen_s:0'3_0(+(1, n525_0)), +'(gen_s:0'3_0(+(1, n525_0)), *4_0)))

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

(14)
Obligation:
TRS:
Rules:
p(s(N)) -> N
+'(N, 0') -> N
+'(s(N), s(M)) -> s(s(+'(N, M)))
*'(N, 0') -> 0'
*'(s(N), s(M)) -> s(+'(N, +'(M, *'(N, M))))
gt(0', M) -> False
gt(NzN, 0') -> u_4(is_NzNat(NzN))
u_4(True) -> True
is_NzNat(0') -> False
is_NzNat(s(N)) -> True
gt(s(N), s(M)) -> gt(N, M)
lt(N, M) -> gt(M, N)
d(0', N) -> N
d(s(N), s(M)) -> d(N, M)
quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
quot(NzM, NzM) -> u_01(is_NzNat(NzM))
u_01(True) -> s(0')
quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
u_21(True, NzM, N) -> u_2(gt(NzM, N))
u_2(True) -> 0'
gcd(0', N) -> 0'
gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
u_02(True, NzM) -> NzM
gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

Types:
p :: s:0' -> s:0'
s :: s:0' -> s:0'
+' :: s:0' -> s:0' -> s:0'
0' :: s:0'
*' :: s:0' -> s:0' -> s:0'
gt :: s:0' -> s:0' -> False:True
False :: False:True
u_4 :: False:True -> False:True
is_NzNat :: s:0' -> False:True
True :: False:True
lt :: s:0' -> s:0' -> False:True
d :: s:0' -> s:0' -> s:0'
quot :: s:0' -> s:0' -> s:0'
u_11 :: False:True -> s:0' -> s:0' -> s:0'
u_1 :: False:True -> s:0' -> s:0' -> s:0'
u_01 :: False:True -> s:0'
u_21 :: False:True -> s:0' -> s:0' -> s:0'
u_2 :: False:True -> s:0'
gcd :: s:0' -> s:0' -> s:0'
u_02 :: False:True -> s:0' -> s:0'
u_31 :: False:True -> False:True -> s:0' -> s:0' -> s:0'
u_3 :: False:True -> s:0' -> s:0' -> s:0'
hole_s:0'1_0 :: s:0'
hole_False:True2_0 :: False:True
gen_s:0'3_0 :: Nat -> s:0'


Lemmas:
+'(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> gen_s:0'3_0(*(2, n5_0)), rt in Omega(1 + n5_0)
*'(gen_s:0'3_0(+(1, n525_0)), gen_s:0'3_0(+(1, n525_0))) -> *4_0, rt in Omega(n525_0)


Generator Equations:
gen_s:0'3_0(0) <=> 0'
gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x))


The following defined symbols remain to be analysed:
gt, d, quot, gcd

They will be analysed ascendingly in the following order:
gt < quot
gt < gcd
d < quot
d < gcd

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

(15) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
gt(gen_s:0'3_0(n34982_0), gen_s:0'3_0(n34982_0)) -> False, rt in Omega(1 + n34982_0)

Induction Base:
gt(gen_s:0'3_0(0), gen_s:0'3_0(0)) ->_R^Omega(1)
False

Induction Step:
gt(gen_s:0'3_0(+(n34982_0, 1)), gen_s:0'3_0(+(n34982_0, 1))) ->_R^Omega(1)
gt(gen_s:0'3_0(n34982_0), gen_s:0'3_0(n34982_0)) ->_IH
False

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

(16)
Obligation:
TRS:
Rules:
p(s(N)) -> N
+'(N, 0') -> N
+'(s(N), s(M)) -> s(s(+'(N, M)))
*'(N, 0') -> 0'
*'(s(N), s(M)) -> s(+'(N, +'(M, *'(N, M))))
gt(0', M) -> False
gt(NzN, 0') -> u_4(is_NzNat(NzN))
u_4(True) -> True
is_NzNat(0') -> False
is_NzNat(s(N)) -> True
gt(s(N), s(M)) -> gt(N, M)
lt(N, M) -> gt(M, N)
d(0', N) -> N
d(s(N), s(M)) -> d(N, M)
quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
quot(NzM, NzM) -> u_01(is_NzNat(NzM))
u_01(True) -> s(0')
quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
u_21(True, NzM, N) -> u_2(gt(NzM, N))
u_2(True) -> 0'
gcd(0', N) -> 0'
gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
u_02(True, NzM) -> NzM
gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

Types:
p :: s:0' -> s:0'
s :: s:0' -> s:0'
+' :: s:0' -> s:0' -> s:0'
0' :: s:0'
*' :: s:0' -> s:0' -> s:0'
gt :: s:0' -> s:0' -> False:True
False :: False:True
u_4 :: False:True -> False:True
is_NzNat :: s:0' -> False:True
True :: False:True
lt :: s:0' -> s:0' -> False:True
d :: s:0' -> s:0' -> s:0'
quot :: s:0' -> s:0' -> s:0'
u_11 :: False:True -> s:0' -> s:0' -> s:0'
u_1 :: False:True -> s:0' -> s:0' -> s:0'
u_01 :: False:True -> s:0'
u_21 :: False:True -> s:0' -> s:0' -> s:0'
u_2 :: False:True -> s:0'
gcd :: s:0' -> s:0' -> s:0'
u_02 :: False:True -> s:0' -> s:0'
u_31 :: False:True -> False:True -> s:0' -> s:0' -> s:0'
u_3 :: False:True -> s:0' -> s:0' -> s:0'
hole_s:0'1_0 :: s:0'
hole_False:True2_0 :: False:True
gen_s:0'3_0 :: Nat -> s:0'


Lemmas:
+'(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> gen_s:0'3_0(*(2, n5_0)), rt in Omega(1 + n5_0)
*'(gen_s:0'3_0(+(1, n525_0)), gen_s:0'3_0(+(1, n525_0))) -> *4_0, rt in Omega(n525_0)
gt(gen_s:0'3_0(n34982_0), gen_s:0'3_0(n34982_0)) -> False, rt in Omega(1 + n34982_0)


Generator Equations:
gen_s:0'3_0(0) <=> 0'
gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x))


The following defined symbols remain to be analysed:
d, quot, gcd

They will be analysed ascendingly in the following order:
d < quot
d < gcd

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
d(gen_s:0'3_0(n35359_0), gen_s:0'3_0(n35359_0)) -> gen_s:0'3_0(0), rt in Omega(1 + n35359_0)

Induction Base:
d(gen_s:0'3_0(0), gen_s:0'3_0(0)) ->_R^Omega(1)
gen_s:0'3_0(0)

Induction Step:
d(gen_s:0'3_0(+(n35359_0, 1)), gen_s:0'3_0(+(n35359_0, 1))) ->_R^Omega(1)
d(gen_s:0'3_0(n35359_0), gen_s:0'3_0(n35359_0)) ->_IH
gen_s:0'3_0(0)

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

(18)
Obligation:
TRS:
Rules:
p(s(N)) -> N
+'(N, 0') -> N
+'(s(N), s(M)) -> s(s(+'(N, M)))
*'(N, 0') -> 0'
*'(s(N), s(M)) -> s(+'(N, +'(M, *'(N, M))))
gt(0', M) -> False
gt(NzN, 0') -> u_4(is_NzNat(NzN))
u_4(True) -> True
is_NzNat(0') -> False
is_NzNat(s(N)) -> True
gt(s(N), s(M)) -> gt(N, M)
lt(N, M) -> gt(M, N)
d(0', N) -> N
d(s(N), s(M)) -> d(N, M)
quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
quot(NzM, NzM) -> u_01(is_NzNat(NzM))
u_01(True) -> s(0')
quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
u_21(True, NzM, N) -> u_2(gt(NzM, N))
u_2(True) -> 0'
gcd(0', N) -> 0'
gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
u_02(True, NzM) -> NzM
gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

Types:
p :: s:0' -> s:0'
s :: s:0' -> s:0'
+' :: s:0' -> s:0' -> s:0'
0' :: s:0'
*' :: s:0' -> s:0' -> s:0'
gt :: s:0' -> s:0' -> False:True
False :: False:True
u_4 :: False:True -> False:True
is_NzNat :: s:0' -> False:True
True :: False:True
lt :: s:0' -> s:0' -> False:True
d :: s:0' -> s:0' -> s:0'
quot :: s:0' -> s:0' -> s:0'
u_11 :: False:True -> s:0' -> s:0' -> s:0'
u_1 :: False:True -> s:0' -> s:0' -> s:0'
u_01 :: False:True -> s:0'
u_21 :: False:True -> s:0' -> s:0' -> s:0'
u_2 :: False:True -> s:0'
gcd :: s:0' -> s:0' -> s:0'
u_02 :: False:True -> s:0' -> s:0'
u_31 :: False:True -> False:True -> s:0' -> s:0' -> s:0'
u_3 :: False:True -> s:0' -> s:0' -> s:0'
hole_s:0'1_0 :: s:0'
hole_False:True2_0 :: False:True
gen_s:0'3_0 :: Nat -> s:0'


Lemmas:
+'(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> gen_s:0'3_0(*(2, n5_0)), rt in Omega(1 + n5_0)
*'(gen_s:0'3_0(+(1, n525_0)), gen_s:0'3_0(+(1, n525_0))) -> *4_0, rt in Omega(n525_0)
gt(gen_s:0'3_0(n34982_0), gen_s:0'3_0(n34982_0)) -> False, rt in Omega(1 + n34982_0)
d(gen_s:0'3_0(n35359_0), gen_s:0'3_0(n35359_0)) -> gen_s:0'3_0(0), rt in Omega(1 + n35359_0)


Generator Equations:
gen_s:0'3_0(0) <=> 0'
gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x))


The following defined symbols remain to be analysed:
quot, gcd