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


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


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


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

(0) CpxTRS
(1) DependencyGraphProof [UPPER BOUND(ID), 0 ms]
(2) CpxTRS
    (3) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
    (4) CpxTRS
    (5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
    (6) CpxRelTRS
    (7) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxRelTRS
    (9) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CpxWeightedTrs
    (11) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) CpxWeightedTrs
    (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) CpxTypedWeightedTrs
    (15) CompletionProof [UPPER BOUND(ID), 0 ms]
    (16) CpxTypedWeightedCompleteTrs
    (17) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 2 ms]
    (18) CpxRNTS
    (19) CompleteCoflocoProof [FINISHED, 425 ms]
    (20) BOUNDS(1, n^2)
(21) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(22) CpxTRS
    (23) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (24) typed CpxTrs
    (25) OrderProof [LOWER BOUND(ID), 0 ms]
    (26) typed CpxTrs
    (27) RewriteLemmaProof [LOWER BOUND(ID), 280 ms]
    (28) BEST
        (29) proven lower bound
            (30) LowerBoundPropagationProof [FINISHED, 0 ms]
            (31) BOUNDS(n^1, INF)
        (32) typed CpxTrs


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

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


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, x, s(y), h) -> a(l, x, y, s(h))
   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +(x, h) -> x
   +(h, x) -> x
   +(s(x), s(y)) -> s(s(+(x, y)))
   +(+(x, y), z) -> +(x, +(y, z))
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

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

(1) DependencyGraphProof (UPPER BOUND(ID))
The following rules are not reachable from basic terms in the dependency graph and can be removed:

+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))

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

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


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, x, s(y), h) -> a(l, x, y, s(h))
   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +(x, h) -> x
   +(h, x) -> x
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

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

(3) NestedDefinedSymbolProof (UPPER BOUND(ID))
The following defined symbols can occur below the 0th argument of sum: s, a
The following defined symbols can occur below the 0th argument of a: s, a
The following defined symbols can occur below the 1th argument of a: s, a

Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
a(l, x, s(y), h) -> a(l, x, y, s(h))
a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))

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

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


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +(x, h) -> x
   +(h, x) -> x
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

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

(5) NonCtorToCtorProof (UPPER BOUND(ID))
transformed non-ctor to ctor-system
----------------------------------------

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


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   +(x, h) -> x
   +(h, x) -> x
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
   a(c_s(l), h, h, z) -> a(l, z, h, z)
   a(l, c_s(x), h, z) -> a(l, x, z, z)

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

   s(x0) -> c_s(x0)

Rewrite Strategy: FULL
----------------------------------------

(7) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

The duplicating contexts are:
a(c_s(l), h, h, [])
a(l, c_s(x), h, [])


The defined contexts are:
sum(cons([], x1))
a([], x1, h, h)
a([], x1, h, x2)
a([], x1, x2, x3)


[] just represents basic- or constructor-terms in the following defined contexts:
sum(cons([], x1))


As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
----------------------------------------

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


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   +(x, h) -> x
   +(h, x) -> x
   s(h) -> 1
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))
   a(c_s(l), h, h, z) -> a(l, z, h, z)
   a(l, c_s(x), h, z) -> a(l, x, z, z)

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

   s(x0) -> c_s(x0)

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

(9) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
Transformed relative TRS to weighted TRS
----------------------------------------

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


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x) [1]
   +(x, h) -> x [1]
   +(h, x) -> x [1]
   s(h) -> 1 [1]
   app(nil, k) -> k [1]
   app(l, nil) -> l [1]
   app(cons(x, l), k) -> cons(x, app(l, k)) [1]
   sum(cons(x, nil)) -> cons(x, nil) [1]
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l)) [1]
   a(c_s(l), h, h, z) -> a(l, z, h, z) [1]
   a(l, c_s(x), h, z) -> a(l, x, z, z) [1]
   s(x0) -> c_s(x0) [0]

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

(11) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
Renamed defined symbols to avoid conflicts with arithmetic symbols:

+ => plus

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

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


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x) [1]
   plus(x, h) -> x [1]
   plus(h, x) -> x [1]
   s(h) -> 1 [1]
   app(nil, k) -> k [1]
   app(l, nil) -> l [1]
   app(cons(x, l), k) -> cons(x, app(l, k)) [1]
   sum(cons(x, nil)) -> cons(x, nil) [1]
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l)) [1]
   a(c_s(l), h, h, z) -> a(l, z, h, z) [1]
   a(l, c_s(x), h, z) -> a(l, x, z, z) [1]
   s(x0) -> c_s(x0) [0]

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

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

(14)
Obligation:
Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x) [1]
   plus(x, h) -> x [1]
   plus(h, x) -> x [1]
   s(h) -> 1 [1]
   app(nil, k) -> k [1]
   app(l, nil) -> l [1]
   app(cons(x, l), k) -> cons(x, app(l, k)) [1]
   sum(cons(x, nil)) -> cons(x, nil) [1]
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l)) [1]
   a(c_s(l), h, h, z) -> a(l, z, h, z) [1]
   a(l, c_s(x), h, z) -> a(l, x, z, z) [1]
   s(x0) -> c_s(x0) [0]

The TRS has the following type information:
a :: h:1:c_s -> h:1:c_s -> h:1:c_s -> h:1:c_s -> h:1:c_s
h :: h:1:c_s
s :: h:1:c_s -> h:1:c_s
plus :: h:1:c_s -> h:1:c_s -> h:1:c_s
1 :: h:1:c_s
app :: nil:cons -> nil:cons -> nil:cons
nil :: nil:cons
cons :: h:1:c_s -> nil:cons -> nil:cons
sum :: nil:cons -> nil:cons
c_s :: h:1:c_s -> h:1:c_s

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

(15) CompletionProof (UPPER BOUND(ID))
The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:

   s(v0) -> null_s [0]
   a(v0, v1, v2, v3) -> null_a [0]
   plus(v0, v1) -> null_plus [0]
   sum(v0) -> null_sum [0]
   app(v0, v1) -> null_app [0]

And the following fresh constants:    null_s, null_a, null_plus, null_sum, null_app

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

(16)
Obligation:
Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x) [1]
   plus(x, h) -> x [1]
   plus(h, x) -> x [1]
   s(h) -> 1 [1]
   app(nil, k) -> k [1]
   app(l, nil) -> l [1]
   app(cons(x, l), k) -> cons(x, app(l, k)) [1]
   sum(cons(x, nil)) -> cons(x, nil) [1]
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l)) [1]
   a(c_s(l), h, h, z) -> a(l, z, h, z) [1]
   a(l, c_s(x), h, z) -> a(l, x, z, z) [1]
   s(x0) -> c_s(x0) [0]
   s(v0) -> null_s [0]
   a(v0, v1, v2, v3) -> null_a [0]
   plus(v0, v1) -> null_plus [0]
   sum(v0) -> null_sum [0]
   app(v0, v1) -> null_app [0]

The TRS has the following type information:
a :: h:1:c_s:null_s:null_a:null_plus -> h:1:c_s:null_s:null_a:null_plus -> h:1:c_s:null_s:null_a:null_plus -> h:1:c_s:null_s:null_a:null_plus -> h:1:c_s:null_s:null_a:null_plus
h :: h:1:c_s:null_s:null_a:null_plus
s :: h:1:c_s:null_s:null_a:null_plus -> h:1:c_s:null_s:null_a:null_plus
plus :: h:1:c_s:null_s:null_a:null_plus -> h:1:c_s:null_s:null_a:null_plus -> h:1:c_s:null_s:null_a:null_plus
1 :: h:1:c_s:null_s:null_a:null_plus
app :: nil:cons:null_sum:null_app -> nil:cons:null_sum:null_app -> nil:cons:null_sum:null_app
nil :: nil:cons:null_sum:null_app
cons :: h:1:c_s:null_s:null_a:null_plus -> nil:cons:null_sum:null_app -> nil:cons:null_sum:null_app
sum :: nil:cons:null_sum:null_app -> nil:cons:null_sum:null_app
c_s :: h:1:c_s:null_s:null_a:null_plus -> h:1:c_s:null_s:null_a:null_plus
null_s :: h:1:c_s:null_s:null_a:null_plus
null_a :: h:1:c_s:null_s:null_a:null_plus
null_plus :: h:1:c_s:null_s:null_a:null_plus
null_sum :: nil:cons:null_sum:null_app
null_app :: nil:cons:null_sum:null_app

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

(17) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
The constant constructors are abstracted as follows:

   h => 1
   1 => 0
   nil => 0
   null_s => 0
   null_a => 0
   null_plus => 0
   null_sum => 0
   null_app => 0

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

(18)
Obligation:
Complexity RNTS consisting of the following rules:

   a(z', z'', z1, z2) -{ 1 }-> s(x) :|: z2 = x, x >= 0, z1 = 1, z' = 1, z'' = 1
   a(z', z'', z1, z2) -{ 1 }-> a(l, x, z, z) :|: z' = l, z >= 0, z2 = z, x >= 0, z1 = 1, l >= 0, z'' = 1 + x
   a(z', z'', z1, z2) -{ 1 }-> a(l, z, 1, z) :|: z >= 0, z2 = z, z1 = 1, l >= 0, z'' = 1, z' = 1 + l
   a(z', z'', z1, z2) -{ 0 }-> 0 :|: z2 = v3, v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, v3 >= 0, z' = v0
   app(z', z'') -{ 1 }-> k :|: k >= 0, z'' = k, z' = 0
   app(z', z'') -{ 1 }-> l :|: z' = l, z'' = 0, l >= 0
   app(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   app(z', z'') -{ 1 }-> 1 + x + app(l, k) :|: x >= 0, z' = 1 + x + l, l >= 0, k >= 0, z'' = k
   plus(z', z'') -{ 1 }-> x :|: z' = x, x >= 0, z'' = 1
   plus(z', z'') -{ 1 }-> x :|: x >= 0, z'' = x, z' = 1
   plus(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   s(z') -{ 1 }-> 0 :|: z' = 1
   s(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   s(z') -{ 0 }-> 1 + x0 :|: x0 >= 0, z' = x0
   sum(z') -{ 1 }-> sum(1 + a(x, y, 1, 1) + l) :|: z' = 1 + x + (1 + y + l), x >= 0, y >= 0, l >= 0
   sum(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   sum(z') -{ 1 }-> 1 + x + 0 :|: x >= 0, z' = 1 + x + 0

Only complete derivations are relevant for the runtime complexity.

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

(19) CompleteCoflocoProof (FINISHED)
Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:

eq(start(V, V1, V4, V2),0,[a(V, V1, V4, V2, Out)],[V >= 0,V1 >= 0,V4 >= 0,V2 >= 0]).
eq(start(V, V1, V4, V2),0,[plus(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1, V4, V2),0,[s(V, Out)],[V >= 0]).
eq(start(V, V1, V4, V2),0,[app(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1, V4, V2),0,[sum(V, Out)],[V >= 0]).
eq(a(V, V1, V4, V2, Out),1,[s(V3, Ret)],[Out = Ret,V2 = V3,V3 >= 0,V4 = 1,V = 1,V1 = 1]).
eq(plus(V, V1, Out),1,[],[Out = V5,V = V5,V5 >= 0,V1 = 1]).
eq(plus(V, V1, Out),1,[],[Out = V6,V6 >= 0,V1 = V6,V = 1]).
eq(s(V, Out),1,[],[Out = 0,V = 1]).
eq(app(V, V1, Out),1,[],[Out = V7,V7 >= 0,V1 = V7,V = 0]).
eq(app(V, V1, Out),1,[],[Out = V8,V = V8,V1 = 0,V8 >= 0]).
eq(app(V, V1, Out),1,[app(V10, V11, Ret1)],[Out = 1 + Ret1 + V9,V9 >= 0,V = 1 + V10 + V9,V10 >= 0,V11 >= 0,V1 = V11]).
eq(sum(V, Out),1,[],[Out = 1 + V12,V12 >= 0,V = 1 + V12]).
eq(sum(V, Out),1,[a(V13, V14, 1, 1, Ret001),sum(1 + Ret001 + V15, Ret2)],[Out = Ret2,V = 2 + V13 + V14 + V15,V13 >= 0,V14 >= 0,V15 >= 0]).
eq(a(V, V1, V4, V2, Out),1,[a(V16, V17, 1, V17, Ret3)],[Out = Ret3,V17 >= 0,V2 = V17,V4 = 1,V16 >= 0,V1 = 1,V = 1 + V16]).
eq(a(V, V1, V4, V2, Out),1,[a(V20, V19, V18, V18, Ret4)],[Out = Ret4,V = V20,V18 >= 0,V2 = V18,V19 >= 0,V4 = 1,V20 >= 0,V1 = 1 + V19]).
eq(s(V, Out),0,[],[Out = 1 + V21,V21 >= 0,V = V21]).
eq(s(V, Out),0,[],[Out = 0,V22 >= 0,V = V22]).
eq(a(V, V1, V4, V2, Out),0,[],[Out = 0,V2 = V25,V24 >= 0,V4 = V26,V23 >= 0,V1 = V23,V26 >= 0,V25 >= 0,V = V24]).
eq(plus(V, V1, Out),0,[],[Out = 0,V28 >= 0,V27 >= 0,V1 = V27,V = V28]).
eq(sum(V, Out),0,[],[Out = 0,V29 >= 0,V = V29]).
eq(app(V, V1, Out),0,[],[Out = 0,V30 >= 0,V31 >= 0,V1 = V31,V = V30]).
input_output_vars(a(V,V1,V4,V2,Out),[V,V1,V4,V2],[Out]).
input_output_vars(plus(V,V1,Out),[V,V1],[Out]).
input_output_vars(s(V,Out),[V],[Out]).
input_output_vars(app(V,V1,Out),[V,V1],[Out]).
input_output_vars(sum(V,Out),[V],[Out]).


CoFloCo proof output:
Preprocessing Cost Relations
=====================================

#### Computed strongly connected components 
0. non_recursive  : [s/2]
1. recursive  : [a/5]
2. recursive  : [app/3]
3. non_recursive  : [plus/3]
4. recursive  : [sum/2]
5. non_recursive  : [start/4]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into s/2
1. SCC is partially evaluated into a/5
2. SCC is partially evaluated into app/3
3. SCC is partially evaluated into plus/3
4. SCC is partially evaluated into sum/2
5. SCC is partially evaluated into start/4

Control-Flow Refinement of Cost Relations
=====================================

### Specialization of cost equations s/2 
* CE 14 is refined into CE [23] 
* CE 13 is refined into CE [24] 
* CE 15 is refined into CE [25] 


### Cost equations --> "Loop" of s/2 
* CEs [23] --> Loop 18 
* CEs [24,25] --> Loop 19 

### Ranking functions of CR s(V,Out) 

#### Partial ranking functions of CR s(V,Out) 


### Specialization of cost equations a/5 
* CE 9 is refined into CE [26] 
* CE 6 is refined into CE [27,28] 
* CE 8 is refined into CE [29] 
* CE 7 is refined into CE [30] 


### Cost equations --> "Loop" of a/5 
* CEs [29] --> Loop 20 
* CEs [30] --> Loop 21 
* CEs [28] --> Loop 22 
* CEs [26,27] --> Loop 23 

### Ranking functions of CR a(V,V1,V4,V2,Out) 

#### Partial ranking functions of CR a(V,V1,V4,V2,Out) 
* Partial RF of phase [20,21]:
  - RF of loop [20:1]:
    V1 depends on loops [21:1] 
  - RF of loop [21:1]:
    V


### Specialization of cost equations app/3 
* CE 19 is refined into CE [31] 
* CE 17 is refined into CE [32] 
* CE 16 is refined into CE [33] 
* CE 18 is refined into CE [34] 


### Cost equations --> "Loop" of app/3 
* CEs [34] --> Loop 24 
* CEs [31] --> Loop 25 
* CEs [32] --> Loop 26 
* CEs [33] --> Loop 27 

### Ranking functions of CR app(V,V1,Out) 
* RF of phase [24]: [V]

#### Partial ranking functions of CR app(V,V1,Out) 
* Partial RF of phase [24]:
  - RF of loop [24:1]:
    V


### Specialization of cost equations plus/3 
* CE 12 is refined into CE [35] 
* CE 10 is refined into CE [36] 
* CE 11 is refined into CE [37] 


### Cost equations --> "Loop" of plus/3 
* CEs [35] --> Loop 28 
* CEs [36] --> Loop 29 
* CEs [37] --> Loop 30 

### Ranking functions of CR plus(V,V1,Out) 

#### Partial ranking functions of CR plus(V,V1,Out) 


### Specialization of cost equations sum/2 
* CE 20 is refined into CE [38] 
* CE 22 is refined into CE [39] 
* CE 21 is refined into CE [40,41,42] 


### Cost equations --> "Loop" of sum/2 
* CEs [40,41,42] --> Loop 31 
* CEs [38] --> Loop 32 
* CEs [39] --> Loop 33 

### Ranking functions of CR sum(V,Out) 
* RF of phase [31]: [V-1]

#### Partial ranking functions of CR sum(V,Out) 
* Partial RF of phase [31]:
  - RF of loop [31:1]:
    V-1


### Specialization of cost equations start/4 
* CE 1 is refined into CE [43,44,45] 
* CE 2 is refined into CE [46,47,48] 
* CE 3 is refined into CE [49,50] 
* CE 4 is refined into CE [51,52,53,54,55] 
* CE 5 is refined into CE [56,57,58] 


### Cost equations --> "Loop" of start/4 
* CEs [44] --> Loop 34 
* CEs [47] --> Loop 35 
* CEs [52] --> Loop 36 
* CEs [43,46] --> Loop 37 
* CEs [45,48,49,50,51,53,54,55,56,57,58] --> Loop 38 

### Ranking functions of CR start(V,V1,V4,V2) 

#### Partial ranking functions of CR start(V,V1,V4,V2) 


Computing Bounds
=====================================

#### Cost of chains of s(V,Out):
* Chain [19]: 1
  with precondition: [Out=0,V>=0] 

* Chain [18]: 0
  with precondition: [V+1=Out,V>=0] 


#### Cost of chains of a(V,V1,V4,V2,Out):
* Chain [[20,21],23]: 1*it(20)+1*it(21)+2
  Such that:it(21) =< V
aux(7) =< V2
aux(9) =< V1
aux(1) =< it(21)*aux(7)
it(20) =< aux(1)+aux(9)

  with precondition: [V4=1,Out=0,V>=0,V1>=1,V2>=0] 

* Chain [[20,21],22]: 1*it(20)+1*it(21)+1
  Such that:it(21) =< V
aux(7) =< Out
aux(10) =< V1
aux(1) =< it(21)*aux(7)
it(20) =< aux(1)+aux(10)

  with precondition: [V4=1,V2=1,Out=2,V>=1,V1>=1,V+V1>=3] 

* Chain [23]: 2
  with precondition: [Out=0,V>=0,V1>=0,V4>=0,V2>=0] 

* Chain [22]: 1
  with precondition: [V=1,V1=1,V4=1,V2+1=Out,V2>=0] 


#### Cost of chains of app(V,V1,Out):
* Chain [[24],27]: 1*it(24)+1
  Such that:it(24) =< -V1+Out

  with precondition: [V+V1=Out,V>=1,V1>=0] 

* Chain [[24],26]: 1*it(24)+1
  Such that:it(24) =< Out

  with precondition: [V1=0,V=Out,V>=1] 

* Chain [[24],25]: 1*it(24)+0
  Such that:it(24) =< Out

  with precondition: [V1>=0,Out>=1,V>=Out] 

* Chain [27]: 1
  with precondition: [V=0,V1=Out,V1>=0] 

* Chain [26]: 1
  with precondition: [V1=0,V=Out,V>=0] 

* Chain [25]: 0
  with precondition: [Out=0,V>=0,V1>=0] 


#### Cost of chains of plus(V,V1,Out):
* Chain [30]: 1
  with precondition: [V=1,V1=Out,V1>=0] 

* Chain [29]: 1
  with precondition: [V1=1,V=Out,V>=0] 

* Chain [28]: 0
  with precondition: [Out=0,V>=0,V1>=0] 


#### Cost of chains of sum(V,Out):
* Chain [[31],33]: 4*it(31)+1*s(27)+1*s(28)+1*s(30)+0
  Such that:s(17) =< 1
s(18) =< 2
s(31) =< 2*V
aux(15) =< V
it(31) =< aux(15)
s(34) =< it(31)*s(17)
s(30) =< s(34)+aux(15)
s(27) =< s(31)
s(32) =< s(27)*s(18)
s(28) =< s(32)+s(31)

  with precondition: [Out=0,V>=2] 

* Chain [[31],32]: 3*it(31)+1*s(27)+1*s(28)+1*s(29)+1*s(30)+1
  Such that:s(17) =< 1
s(18) =< 2
aux(13) =< V
aux(14) =< V-Out
s(31) =< 2*V-2*Out
it(31) =< aux(13)
s(33) =< aux(13)
it(31) =< aux(14)
s(33) =< aux(14)
s(29) =< s(33)
s(34) =< s(29)*s(17)
s(30) =< s(34)+s(33)
s(27) =< s(31)
s(32) =< s(27)*s(18)
s(28) =< s(32)+s(31)

  with precondition: [Out>=1,V>=Out+1] 

* Chain [33]: 0
  with precondition: [Out=0,V>=0] 

* Chain [32]: 1
  with precondition: [V=Out,V>=1] 


#### Cost of chains of start(V,V1,V4,V2):
* Chain [38]: 11*s(45)+1*s(49)+2*s(58)+2*s(59)+2*s(61)+2
  Such that:s(46) =< V1
s(47) =< V2
aux(17) =< 1
aux(18) =< 2
aux(19) =< V
aux(20) =< 2*V
s(45) =< aux(19)
s(57) =< s(45)*aux(17)
s(58) =< s(57)+aux(19)
s(59) =< aux(20)
s(60) =< s(59)*aux(18)
s(61) =< s(60)+aux(20)
s(48) =< s(45)*s(47)
s(49) =< s(48)+s(46)

  with precondition: [V>=0] 

* Chain [37]: 1
  with precondition: [V=1,V1>=0] 

* Chain [36]: 1*s(75)+1
  Such that:s(75) =< V

  with precondition: [V1=0,V>=0] 

* Chain [35]: 1
  with precondition: [V1=1,V>=0] 

* Chain [34]: 1*s(76)+1*s(80)+1
  Such that:s(77) =< 2
s(76) =< V
s(78) =< V1
s(79) =< s(76)*s(77)
s(80) =< s(79)+s(78)

  with precondition: [V4=1,V2=1,V>=1,V1>=1,V+V1>=3] 


Closed-form bounds of start(V,V1,V4,V2): 
-------------------------------------
* Chain [38] with precondition: [V>=0] 
    - Upper bound: 15*V+2+nat(V2)*V+nat(V1)+16*V 
    - Complexity: n^2 
* Chain [37] with precondition: [V=1,V1>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [36] with precondition: [V1=0,V>=0] 
    - Upper bound: V+1 
    - Complexity: n 
* Chain [35] with precondition: [V1=1,V>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [34] with precondition: [V4=1,V2=1,V>=1,V1>=1,V+V1>=3] 
    - Upper bound: 3*V+V1+1 
    - Complexity: n 

### Maximum cost of start(V,V1,V4,V2): 12*V+1+nat(V2)*V+16*V+(2*V+nat(V1))+V+1 
Asymptotic class: n^2 
* Total analysis performed in 333 ms.


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

(20)
BOUNDS(1, n^2)

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

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

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


The TRS R consists of the following rules:

   a(h, h, h, x) -> s(x)
   a(l, x, s(y), h) -> a(l, x, y, s(h))
   a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
   a(l, s(x), h, z) -> a(l, x, z, z)
   a(s(l), h, h, z) -> a(l, z, h, z)
   +'(x, h) -> x
   +'(h, x) -> x
   +'(s(x), s(y)) -> s(s(+'(x, y)))
   +'(+'(x, y), z) -> +'(x, +'(y, z))
   s(h) -> 1'
   app(nil, k) -> k
   app(l, nil) -> l
   app(cons(x, l), k) -> cons(x, app(l, k))
   sum(cons(x, nil)) -> cons(x, nil)
   sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

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

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

(24)
Obligation:
TRS:
Rules:
a(h, h, h, x) -> s(x)
a(l, x, s(y), h) -> a(l, x, y, s(h))
a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) -> a(l, x, z, z)
a(s(l), h, h, z) -> a(l, z, h, z)
+'(x, h) -> x
+'(h, x) -> x
+'(s(x), s(y)) -> s(s(+'(x, y)))
+'(+'(x, y), z) -> +'(x, +'(y, z))
s(h) -> 1'
app(nil, k) -> k
app(l, nil) -> l
app(cons(x, l), k) -> cons(x, app(l, k))
sum(cons(x, nil)) -> cons(x, nil)
sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

Types:
a :: h:1' -> h:1' -> h:1' -> h:1' -> h:1'
h :: h:1'
s :: h:1' -> h:1'
+' :: h:1' -> h:1' -> h:1'
1' :: h:1'
app :: nil:cons -> nil:cons -> nil:cons
nil :: nil:cons
cons :: h:1' -> nil:cons -> nil:cons
sum :: nil:cons -> nil:cons
hole_h:1'1_0 :: h:1'
hole_nil:cons2_0 :: nil:cons
gen_nil:cons3_0 :: Nat -> nil:cons

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

(25) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
a, +', app, sum

They will be analysed ascendingly in the following order:
a < sum

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

(26)
Obligation:
TRS:
Rules:
a(h, h, h, x) -> s(x)
a(l, x, s(y), h) -> a(l, x, y, s(h))
a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) -> a(l, x, z, z)
a(s(l), h, h, z) -> a(l, z, h, z)
+'(x, h) -> x
+'(h, x) -> x
+'(s(x), s(y)) -> s(s(+'(x, y)))
+'(+'(x, y), z) -> +'(x, +'(y, z))
s(h) -> 1'
app(nil, k) -> k
app(l, nil) -> l
app(cons(x, l), k) -> cons(x, app(l, k))
sum(cons(x, nil)) -> cons(x, nil)
sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

Types:
a :: h:1' -> h:1' -> h:1' -> h:1' -> h:1'
h :: h:1'
s :: h:1' -> h:1'
+' :: h:1' -> h:1' -> h:1'
1' :: h:1'
app :: nil:cons -> nil:cons -> nil:cons
nil :: nil:cons
cons :: h:1' -> nil:cons -> nil:cons
sum :: nil:cons -> nil:cons
hole_h:1'1_0 :: h:1'
hole_nil:cons2_0 :: nil:cons
gen_nil:cons3_0 :: Nat -> nil:cons


Generator Equations:
gen_nil:cons3_0(0) <=> nil
gen_nil:cons3_0(+(x, 1)) <=> cons(h, gen_nil:cons3_0(x))


The following defined symbols remain to be analysed:
a, +', app, sum

They will be analysed ascendingly in the following order:
a < sum

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

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
app(gen_nil:cons3_0(n170_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n170_0, b)), rt in Omega(1 + n170_0)

Induction Base:
app(gen_nil:cons3_0(0), gen_nil:cons3_0(b)) ->_R^Omega(1)
gen_nil:cons3_0(b)

Induction Step:
app(gen_nil:cons3_0(+(n170_0, 1)), gen_nil:cons3_0(b)) ->_R^Omega(1)
cons(h, app(gen_nil:cons3_0(n170_0), gen_nil:cons3_0(b))) ->_IH
cons(h, gen_nil:cons3_0(+(b, c171_0)))

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

(28)
Complex Obligation (BEST)

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

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

TRS:
Rules:
a(h, h, h, x) -> s(x)
a(l, x, s(y), h) -> a(l, x, y, s(h))
a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) -> a(l, x, z, z)
a(s(l), h, h, z) -> a(l, z, h, z)
+'(x, h) -> x
+'(h, x) -> x
+'(s(x), s(y)) -> s(s(+'(x, y)))
+'(+'(x, y), z) -> +'(x, +'(y, z))
s(h) -> 1'
app(nil, k) -> k
app(l, nil) -> l
app(cons(x, l), k) -> cons(x, app(l, k))
sum(cons(x, nil)) -> cons(x, nil)
sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

Types:
a :: h:1' -> h:1' -> h:1' -> h:1' -> h:1'
h :: h:1'
s :: h:1' -> h:1'
+' :: h:1' -> h:1' -> h:1'
1' :: h:1'
app :: nil:cons -> nil:cons -> nil:cons
nil :: nil:cons
cons :: h:1' -> nil:cons -> nil:cons
sum :: nil:cons -> nil:cons
hole_h:1'1_0 :: h:1'
hole_nil:cons2_0 :: nil:cons
gen_nil:cons3_0 :: Nat -> nil:cons


Generator Equations:
gen_nil:cons3_0(0) <=> nil
gen_nil:cons3_0(+(x, 1)) <=> cons(h, gen_nil:cons3_0(x))


The following defined symbols remain to be analysed:
app, sum
----------------------------------------

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

(31)
BOUNDS(n^1, INF)

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

(32)
Obligation:
TRS:
Rules:
a(h, h, h, x) -> s(x)
a(l, x, s(y), h) -> a(l, x, y, s(h))
a(l, x, s(y), s(z)) -> a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) -> a(l, x, z, z)
a(s(l), h, h, z) -> a(l, z, h, z)
+'(x, h) -> x
+'(h, x) -> x
+'(s(x), s(y)) -> s(s(+'(x, y)))
+'(+'(x, y), z) -> +'(x, +'(y, z))
s(h) -> 1'
app(nil, k) -> k
app(l, nil) -> l
app(cons(x, l), k) -> cons(x, app(l, k))
sum(cons(x, nil)) -> cons(x, nil)
sum(cons(x, cons(y, l))) -> sum(cons(a(x, y, h, h), l))

Types:
a :: h:1' -> h:1' -> h:1' -> h:1' -> h:1'
h :: h:1'
s :: h:1' -> h:1'
+' :: h:1' -> h:1' -> h:1'
1' :: h:1'
app :: nil:cons -> nil:cons -> nil:cons
nil :: nil:cons
cons :: h:1' -> nil:cons -> nil:cons
sum :: nil:cons -> nil:cons
hole_h:1'1_0 :: h:1'
hole_nil:cons2_0 :: nil:cons
gen_nil:cons3_0 :: Nat -> nil:cons


Lemmas:
app(gen_nil:cons3_0(n170_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n170_0, b)), rt in Omega(1 + n170_0)


Generator Equations:
gen_nil:cons3_0(0) <=> nil
gen_nil:cons3_0(+(x, 1)) <=> cons(h, gen_nil:cons3_0(x))


The following defined symbols remain to be analysed:
sum