/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /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 Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, INF).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 556 ms]
(4) CpxRelTRS
(5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxRelTRS
(7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 10 ms]
(8) typed CpxTrs
(9) OrderProof [LOWER BOUND(ID), 0 ms]
(10) typed CpxTrs
(11) RewriteLemmaProof [LOWER BOUND(ID), 265 ms]
(12) BEST
    (13) proven lower bound
        (14) LowerBoundPropagationProof [FINISHED, 0 ms]
        (15) BOUNDS(n^1, INF)
    (16) typed CpxTrs
        (17) RewriteLemmaProof [LOWER BOUND(ID), 73 ms]
        (18) typed CpxTrs
        (19) RewriteLemmaProof [LOWER BOUND(ID), 105 ms]
        (20) typed CpxTrs
        (21) RewriteLemmaProof [LOWER BOUND(ID), 10.0 s]
        (22) BOUNDS(1, INF)


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

(0)
Obligation:
The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   plus(x, y) -> ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
   ifPlus(false, x, y, z) -> plus(x, z)
   ifPlus(true, x, y, z) -> y
   minus(s(x), s(y)) -> minus(x, y)
   minus(0, x) -> 0
   minus(x, 0) -> x
   minus(x, x) -> 0
   eq(s(x), s(y)) -> eq(x, y)
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(0, 0) -> true
   eq(x, x) -> true
   times(x, y) -> timesIter(x, y, 0)
   timesIter(x, y, z) -> ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
   ifTimes(true, x, y, z, u) -> z
   ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
   f -> g
   f -> h

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

(1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID))
The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(false) -> false
   encArg(true) -> true
   encArg(g) -> g
   encArg(h) -> h
   encArg(cons_inc(x_1)) -> inc(encArg(x_1))
   encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
   encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
   encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
   encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
   encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
   encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
   encArg(cons_f) -> f
   encode_inc(x_1) -> inc(encArg(x_1))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0
   encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
   encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
   encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
   encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true
   encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
   encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
   encode_f -> f
   encode_g -> g
   encode_h -> h


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

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


The TRS R consists of the following rules:

   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   plus(x, y) -> ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
   ifPlus(false, x, y, z) -> plus(x, z)
   ifPlus(true, x, y, z) -> y
   minus(s(x), s(y)) -> minus(x, y)
   minus(0, x) -> 0
   minus(x, 0) -> x
   minus(x, x) -> 0
   eq(s(x), s(y)) -> eq(x, y)
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(0, 0) -> true
   eq(x, x) -> true
   times(x, y) -> timesIter(x, y, 0)
   timesIter(x, y, z) -> ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
   ifTimes(true, x, y, z, u) -> z
   ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
   f -> g
   f -> h

The (relative) TRS S consists of the following rules:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(false) -> false
   encArg(true) -> true
   encArg(g) -> g
   encArg(h) -> h
   encArg(cons_inc(x_1)) -> inc(encArg(x_1))
   encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
   encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
   encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
   encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
   encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
   encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
   encArg(cons_f) -> f
   encode_inc(x_1) -> inc(encArg(x_1))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0
   encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
   encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
   encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
   encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true
   encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
   encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
   encode_f -> f
   encode_g -> g
   encode_h -> h

Rewrite Strategy: INNERMOST
----------------------------------------

(3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

(4)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   inc(s(x)) -> s(inc(x))
   inc(0) -> s(0)
   plus(x, y) -> ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
   ifPlus(false, x, y, z) -> plus(x, z)
   ifPlus(true, x, y, z) -> y
   minus(s(x), s(y)) -> minus(x, y)
   minus(0, x) -> 0
   minus(x, 0) -> x
   minus(x, x) -> 0
   eq(s(x), s(y)) -> eq(x, y)
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(0, 0) -> true
   eq(x, x) -> true
   times(x, y) -> timesIter(x, y, 0)
   timesIter(x, y, z) -> ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
   ifTimes(true, x, y, z, u) -> z
   ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
   f -> g
   f -> h

The (relative) TRS S consists of the following rules:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(false) -> false
   encArg(true) -> true
   encArg(g) -> g
   encArg(h) -> h
   encArg(cons_inc(x_1)) -> inc(encArg(x_1))
   encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
   encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
   encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
   encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
   encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
   encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
   encArg(cons_f) -> f
   encode_inc(x_1) -> inc(encArg(x_1))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0
   encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
   encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
   encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
   encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true
   encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
   encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
   encode_f -> f
   encode_g -> g
   encode_h -> h

Rewrite Strategy: INNERMOST
----------------------------------------

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

(6)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   inc(s(x)) -> s(inc(x))
   inc(0') -> s(0')
   plus(x, y) -> ifPlus(eq(x, 0'), minus(x, s(0')), x, inc(x))
   ifPlus(false, x, y, z) -> plus(x, z)
   ifPlus(true, x, y, z) -> y
   minus(s(x), s(y)) -> minus(x, y)
   minus(0', x) -> 0'
   minus(x, 0') -> x
   minus(x, x) -> 0'
   eq(s(x), s(y)) -> eq(x, y)
   eq(0', s(x)) -> false
   eq(s(x), 0') -> false
   eq(0', 0') -> true
   eq(x, x) -> true
   times(x, y) -> timesIter(x, y, 0')
   timesIter(x, y, z) -> ifTimes(eq(x, 0'), minus(x, s(0')), y, z, plus(y, z))
   ifTimes(true, x, y, z, u) -> z
   ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
   f -> g
   f -> h

The (relative) TRS S consists of the following rules:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0') -> 0'
   encArg(false) -> false
   encArg(true) -> true
   encArg(g) -> g
   encArg(h) -> h
   encArg(cons_inc(x_1)) -> inc(encArg(x_1))
   encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
   encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
   encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
   encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
   encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
   encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
   encArg(cons_f) -> f
   encode_inc(x_1) -> inc(encArg(x_1))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0'
   encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
   encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
   encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
   encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true
   encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
   encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
   encode_f -> f
   encode_g -> g
   encode_h -> h

Rewrite Strategy: INNERMOST
----------------------------------------

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

(8)
Obligation:
Innermost TRS:
Rules:
inc(s(x)) -> s(inc(x))
inc(0') -> s(0')
plus(x, y) -> ifPlus(eq(x, 0'), minus(x, s(0')), x, inc(x))
ifPlus(false, x, y, z) -> plus(x, z)
ifPlus(true, x, y, z) -> y
minus(s(x), s(y)) -> minus(x, y)
minus(0', x) -> 0'
minus(x, 0') -> x
minus(x, x) -> 0'
eq(s(x), s(y)) -> eq(x, y)
eq(0', s(x)) -> false
eq(s(x), 0') -> false
eq(0', 0') -> true
eq(x, x) -> true
times(x, y) -> timesIter(x, y, 0')
timesIter(x, y, z) -> ifTimes(eq(x, 0'), minus(x, s(0')), y, z, plus(y, z))
ifTimes(true, x, y, z, u) -> z
ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
f -> g
f -> h
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(false) -> false
encArg(true) -> true
encArg(g) -> g
encArg(h) -> h
encArg(cons_inc(x_1)) -> inc(encArg(x_1))
encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encArg(cons_f) -> f
encode_inc(x_1) -> inc(encArg(x_1))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'
encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
encode_false -> false
encode_true -> true
encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encode_f -> f
encode_g -> g
encode_h -> h

Types:
inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
0' :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encArg :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_0 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
hole_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f1_6 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6 :: Nat -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f

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

(9) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
inc, plus, ifPlus, eq, minus, timesIter, ifTimes, encArg

They will be analysed ascendingly in the following order:
inc < plus
inc < encArg
plus = ifPlus
eq < plus
minus < plus
plus < timesIter
plus < encArg
ifPlus < encArg
eq < timesIter
eq < encArg
minus < timesIter
minus < encArg
timesIter = ifTimes
timesIter < encArg
ifTimes < encArg

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

(10)
Obligation:
Innermost TRS:
Rules:
inc(s(x)) -> s(inc(x))
inc(0') -> s(0')
plus(x, y) -> ifPlus(eq(x, 0'), minus(x, s(0')), x, inc(x))
ifPlus(false, x, y, z) -> plus(x, z)
ifPlus(true, x, y, z) -> y
minus(s(x), s(y)) -> minus(x, y)
minus(0', x) -> 0'
minus(x, 0') -> x
minus(x, x) -> 0'
eq(s(x), s(y)) -> eq(x, y)
eq(0', s(x)) -> false
eq(s(x), 0') -> false
eq(0', 0') -> true
eq(x, x) -> true
times(x, y) -> timesIter(x, y, 0')
timesIter(x, y, z) -> ifTimes(eq(x, 0'), minus(x, s(0')), y, z, plus(y, z))
ifTimes(true, x, y, z, u) -> z
ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
f -> g
f -> h
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(false) -> false
encArg(true) -> true
encArg(g) -> g
encArg(h) -> h
encArg(cons_inc(x_1)) -> inc(encArg(x_1))
encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encArg(cons_f) -> f
encode_inc(x_1) -> inc(encArg(x_1))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'
encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
encode_false -> false
encode_true -> true
encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encode_f -> f
encode_g -> g
encode_h -> h

Types:
inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
0' :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encArg :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_0 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
hole_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f1_6 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6 :: Nat -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f


Generator Equations:
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0) <=> 0'
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(x, 1)) <=> s(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(x))


The following defined symbols remain to be analysed:
inc, plus, ifPlus, eq, minus, timesIter, ifTimes, encArg

They will be analysed ascendingly in the following order:
inc < plus
inc < encArg
plus = ifPlus
eq < plus
minus < plus
plus < timesIter
plus < encArg
ifPlus < encArg
eq < timesIter
eq < encArg
minus < timesIter
minus < encArg
timesIter = ifTimes
timesIter < encArg
ifTimes < encArg

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

(11) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
inc(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n4_6)) -> gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, n4_6)), rt in Omega(1 + n4_6)

Induction Base:
inc(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0)) ->_R^Omega(1)
s(0')

Induction Step:
inc(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(n4_6, 1))) ->_R^Omega(1)
s(inc(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n4_6))) ->_IH
s(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, c5_6)))

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

(12)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
inc(s(x)) -> s(inc(x))
inc(0') -> s(0')
plus(x, y) -> ifPlus(eq(x, 0'), minus(x, s(0')), x, inc(x))
ifPlus(false, x, y, z) -> plus(x, z)
ifPlus(true, x, y, z) -> y
minus(s(x), s(y)) -> minus(x, y)
minus(0', x) -> 0'
minus(x, 0') -> x
minus(x, x) -> 0'
eq(s(x), s(y)) -> eq(x, y)
eq(0', s(x)) -> false
eq(s(x), 0') -> false
eq(0', 0') -> true
eq(x, x) -> true
times(x, y) -> timesIter(x, y, 0')
timesIter(x, y, z) -> ifTimes(eq(x, 0'), minus(x, s(0')), y, z, plus(y, z))
ifTimes(true, x, y, z, u) -> z
ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
f -> g
f -> h
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(false) -> false
encArg(true) -> true
encArg(g) -> g
encArg(h) -> h
encArg(cons_inc(x_1)) -> inc(encArg(x_1))
encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encArg(cons_f) -> f
encode_inc(x_1) -> inc(encArg(x_1))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'
encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
encode_false -> false
encode_true -> true
encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encode_f -> f
encode_g -> g
encode_h -> h

Types:
inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
0' :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encArg :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_0 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
hole_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f1_6 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6 :: Nat -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f


Generator Equations:
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0) <=> 0'
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(x, 1)) <=> s(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(x))


The following defined symbols remain to be analysed:
inc, plus, ifPlus, eq, minus, timesIter, ifTimes, encArg

They will be analysed ascendingly in the following order:
inc < plus
inc < encArg
plus = ifPlus
eq < plus
minus < plus
plus < timesIter
plus < encArg
ifPlus < encArg
eq < timesIter
eq < encArg
minus < timesIter
minus < encArg
timesIter = ifTimes
timesIter < encArg
ifTimes < encArg

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

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

(15)
BOUNDS(n^1, INF)

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

(16)
Obligation:
Innermost TRS:
Rules:
inc(s(x)) -> s(inc(x))
inc(0') -> s(0')
plus(x, y) -> ifPlus(eq(x, 0'), minus(x, s(0')), x, inc(x))
ifPlus(false, x, y, z) -> plus(x, z)
ifPlus(true, x, y, z) -> y
minus(s(x), s(y)) -> minus(x, y)
minus(0', x) -> 0'
minus(x, 0') -> x
minus(x, x) -> 0'
eq(s(x), s(y)) -> eq(x, y)
eq(0', s(x)) -> false
eq(s(x), 0') -> false
eq(0', 0') -> true
eq(x, x) -> true
times(x, y) -> timesIter(x, y, 0')
timesIter(x, y, z) -> ifTimes(eq(x, 0'), minus(x, s(0')), y, z, plus(y, z))
ifTimes(true, x, y, z, u) -> z
ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
f -> g
f -> h
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(false) -> false
encArg(true) -> true
encArg(g) -> g
encArg(h) -> h
encArg(cons_inc(x_1)) -> inc(encArg(x_1))
encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encArg(cons_f) -> f
encode_inc(x_1) -> inc(encArg(x_1))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'
encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
encode_false -> false
encode_true -> true
encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encode_f -> f
encode_g -> g
encode_h -> h

Types:
inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
0' :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encArg :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_0 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
hole_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f1_6 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6 :: Nat -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f


Lemmas:
inc(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n4_6)) -> gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, n4_6)), rt in Omega(1 + n4_6)


Generator Equations:
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0) <=> 0'
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(x, 1)) <=> s(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(x))


The following defined symbols remain to be analysed:
eq, plus, ifPlus, minus, timesIter, ifTimes, encArg

They will be analysed ascendingly in the following order:
plus = ifPlus
eq < plus
minus < plus
plus < timesIter
plus < encArg
ifPlus < encArg
eq < timesIter
eq < encArg
minus < timesIter
minus < encArg
timesIter = ifTimes
timesIter < encArg
ifTimes < encArg

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
eq(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n557_6), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, n557_6))) -> false, rt in Omega(1 + n557_6)

Induction Base:
eq(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, 0))) ->_R^Omega(1)
false

Induction Step:
eq(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(n557_6, 1)), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, +(n557_6, 1)))) ->_R^Omega(1)
eq(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n557_6), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, n557_6))) ->_IH
false

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

(18)
Obligation:
Innermost TRS:
Rules:
inc(s(x)) -> s(inc(x))
inc(0') -> s(0')
plus(x, y) -> ifPlus(eq(x, 0'), minus(x, s(0')), x, inc(x))
ifPlus(false, x, y, z) -> plus(x, z)
ifPlus(true, x, y, z) -> y
minus(s(x), s(y)) -> minus(x, y)
minus(0', x) -> 0'
minus(x, 0') -> x
minus(x, x) -> 0'
eq(s(x), s(y)) -> eq(x, y)
eq(0', s(x)) -> false
eq(s(x), 0') -> false
eq(0', 0') -> true
eq(x, x) -> true
times(x, y) -> timesIter(x, y, 0')
timesIter(x, y, z) -> ifTimes(eq(x, 0'), minus(x, s(0')), y, z, plus(y, z))
ifTimes(true, x, y, z, u) -> z
ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
f -> g
f -> h
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(false) -> false
encArg(true) -> true
encArg(g) -> g
encArg(h) -> h
encArg(cons_inc(x_1)) -> inc(encArg(x_1))
encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encArg(cons_f) -> f
encode_inc(x_1) -> inc(encArg(x_1))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'
encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
encode_false -> false
encode_true -> true
encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encode_f -> f
encode_g -> g
encode_h -> h

Types:
inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
0' :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encArg :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_0 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
hole_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f1_6 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6 :: Nat -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f


Lemmas:
inc(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n4_6)) -> gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, n4_6)), rt in Omega(1 + n4_6)
eq(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n557_6), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, n557_6))) -> false, rt in Omega(1 + n557_6)


Generator Equations:
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0) <=> 0'
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(x, 1)) <=> s(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(x))


The following defined symbols remain to be analysed:
minus, plus, ifPlus, timesIter, ifTimes, encArg

They will be analysed ascendingly in the following order:
plus = ifPlus
minus < plus
plus < timesIter
plus < encArg
ifPlus < encArg
minus < timesIter
minus < encArg
timesIter = ifTimes
timesIter < encArg
ifTimes < encArg

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

(19) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
minus(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n1528_6), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n1528_6)) -> gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0), rt in Omega(1 + n1528_6)

Induction Base:
minus(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0)) ->_R^Omega(1)
0'

Induction Step:
minus(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(n1528_6, 1)), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(n1528_6, 1))) ->_R^Omega(1)
minus(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n1528_6), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n1528_6)) ->_IH
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0)

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

(20)
Obligation:
Innermost TRS:
Rules:
inc(s(x)) -> s(inc(x))
inc(0') -> s(0')
plus(x, y) -> ifPlus(eq(x, 0'), minus(x, s(0')), x, inc(x))
ifPlus(false, x, y, z) -> plus(x, z)
ifPlus(true, x, y, z) -> y
minus(s(x), s(y)) -> minus(x, y)
minus(0', x) -> 0'
minus(x, 0') -> x
minus(x, x) -> 0'
eq(s(x), s(y)) -> eq(x, y)
eq(0', s(x)) -> false
eq(s(x), 0') -> false
eq(0', 0') -> true
eq(x, x) -> true
times(x, y) -> timesIter(x, y, 0')
timesIter(x, y, z) -> ifTimes(eq(x, 0'), minus(x, s(0')), y, z, plus(y, z))
ifTimes(true, x, y, z, u) -> z
ifTimes(false, x, y, z, u) -> timesIter(x, y, u)
f -> g
f -> h
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(false) -> false
encArg(true) -> true
encArg(g) -> g
encArg(h) -> h
encArg(cons_inc(x_1)) -> inc(encArg(x_1))
encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2))
encArg(cons_ifPlus(x_1, x_2, x_3, x_4)) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2))
encArg(cons_timesIter(x_1, x_2, x_3)) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_ifTimes(x_1, x_2, x_3, x_4, x_5)) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encArg(cons_f) -> f
encode_inc(x_1) -> inc(encArg(x_1))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'
encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2))
encode_ifPlus(x_1, x_2, x_3, x_4) -> ifPlus(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2))
encode_false -> false
encode_true -> true
encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2))
encode_timesIter(x_1, x_2, x_3) -> timesIter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_ifTimes(x_1, x_2, x_3, x_4, x_5) -> ifTimes(encArg(x_1), encArg(x_2), encArg(x_3), encArg(x_4), encArg(x_5))
encode_f -> f
encode_g -> g
encode_h -> h

Types:
inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
0' :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encArg :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
cons_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_inc :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_s :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_0 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_plus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifPlus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_eq :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_minus :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_false :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_true :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_times :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_timesIter :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_ifTimes :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_f :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_g :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
encode_h :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
hole_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f1_6 :: s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6 :: Nat -> s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f


Lemmas:
inc(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n4_6)) -> gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, n4_6)), rt in Omega(1 + n4_6)
eq(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n557_6), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(1, n557_6))) -> false, rt in Omega(1 + n557_6)
minus(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n1528_6), gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n1528_6)) -> gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0), rt in Omega(1 + n1528_6)


Generator Equations:
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0) <=> 0'
gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(x, 1)) <=> s(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(x))


The following defined symbols remain to be analysed:
ifPlus, plus, timesIter, ifTimes, encArg

They will be analysed ascendingly in the following order:
plus = ifPlus
plus < timesIter
plus < encArg
ifPlus < encArg
timesIter = ifTimes
timesIter < encArg
ifTimes < encArg

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

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n5467_6)) -> gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n5467_6), rt in Omega(0)

Induction Base:
encArg(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(0)) ->_R^Omega(0)
0'

Induction Step:
encArg(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(+(n5467_6, 1))) ->_R^Omega(0)
s(encArg(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(n5467_6))) ->_IH
s(gen_s:0':false:true:g:h:cons_inc:cons_plus:cons_ifPlus:cons_minus:cons_eq:cons_times:cons_timesIter:cons_ifTimes:cons_f2_6(c5468_6))

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

(22)
BOUNDS(1, INF)