/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^1))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


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

(0) CpxTRS
(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxTRS
    (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CpxWeightedTrs
    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxTypedWeightedTrs
    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
    (8) CpxTypedWeightedCompleteTrs
    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (10) CpxRNTS
    (11) CompleteCoflocoProof [FINISHED, 181 ms]
    (12) BOUNDS(1, n^1)
(13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(14) TRS for Loop Detection
    (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (16) BEST
        (17) proven lower bound
            (18) LowerBoundPropagationProof [FINISHED, 0 ms]
            (19) BOUNDS(n^1, INF)
        (20) TRS for Loop Detection


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

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


The TRS R consists of the following rules:

   a__f(X, g(X), Y) -> a__f(Y, Y, Y)
   a__g(b) -> c
   a__b -> c
   mark(f(X1, X2, X3)) -> a__f(X1, X2, X3)
   mark(g(X)) -> a__g(mark(X))
   mark(b) -> a__b
   mark(c) -> c
   a__f(X1, X2, X3) -> f(X1, X2, X3)
   a__g(X) -> g(X)
   a__b -> b

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

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

The duplicating contexts are:
a__f(X, g(X), [])


The defined contexts are:
a__g([])


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

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


The TRS R consists of the following rules:

   a__f(X, g(X), Y) -> a__f(Y, Y, Y)
   a__g(b) -> c
   a__b -> c
   mark(f(X1, X2, X3)) -> a__f(X1, X2, X3)
   mark(g(X)) -> a__g(mark(X))
   mark(b) -> a__b
   mark(c) -> c
   a__f(X1, X2, X3) -> f(X1, X2, X3)
   a__g(X) -> g(X)
   a__b -> b

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

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

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


The TRS R consists of the following rules:

   a__f(X, g(X), Y) -> a__f(Y, Y, Y) [1]
   a__g(b) -> c [1]
   a__b -> c [1]
   mark(f(X1, X2, X3)) -> a__f(X1, X2, X3) [1]
   mark(g(X)) -> a__g(mark(X)) [1]
   mark(b) -> a__b [1]
   mark(c) -> c [1]
   a__f(X1, X2, X3) -> f(X1, X2, X3) [1]
   a__g(X) -> g(X) [1]
   a__b -> b [1]

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

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

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

   a__f(X, g(X), Y) -> a__f(Y, Y, Y) [1]
   a__g(b) -> c [1]
   a__b -> c [1]
   mark(f(X1, X2, X3)) -> a__f(X1, X2, X3) [1]
   mark(g(X)) -> a__g(mark(X)) [1]
   mark(b) -> a__b [1]
   mark(c) -> c [1]
   a__f(X1, X2, X3) -> f(X1, X2, X3) [1]
   a__g(X) -> g(X) [1]
   a__b -> b [1]

The TRS has the following type information:
a__f :: g:b:c:f -> g:b:c:f -> g:b:c:f -> g:b:c:f
g :: g:b:c:f -> g:b:c:f
a__g :: g:b:c:f -> g:b:c:f
b :: g:b:c:f
c :: g:b:c:f
a__b :: g:b:c:f
mark :: g:b:c:f -> g:b:c:f
f :: g:b:c:f -> g:b:c:f -> g:b:c:f -> g:b:c:f

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

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

And the following fresh constants: none

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

(8)
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__f(X, g(X), Y) -> a__f(Y, Y, Y) [1]
   a__g(b) -> c [1]
   a__b -> c [1]
   mark(f(X1, X2, X3)) -> a__f(X1, X2, X3) [1]
   mark(g(X)) -> a__g(mark(X)) [1]
   mark(b) -> a__b [1]
   mark(c) -> c [1]
   a__f(X1, X2, X3) -> f(X1, X2, X3) [1]
   a__g(X) -> g(X) [1]
   a__b -> b [1]

The TRS has the following type information:
a__f :: g:b:c:f -> g:b:c:f -> g:b:c:f -> g:b:c:f
g :: g:b:c:f -> g:b:c:f
a__g :: g:b:c:f -> g:b:c:f
b :: g:b:c:f
c :: g:b:c:f
a__b :: g:b:c:f
mark :: g:b:c:f -> g:b:c:f
f :: g:b:c:f -> g:b:c:f -> g:b:c:f -> g:b:c:f

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

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

   b => 0
   c => 1

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

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

   a__b -{ 1 }-> 1 :|: 
   a__b -{ 1 }-> 0 :|: 
   a__f(z, z', z'') -{ 1 }-> a__f(Y, Y, Y) :|: Y >= 0, z'' = Y, z' = 1 + X, X >= 0, z = X
   a__f(z, z', z'') -{ 1 }-> 1 + X1 + X2 + X3 :|: X1 >= 0, X3 >= 0, X2 >= 0, z = X1, z' = X2, z'' = X3
   a__g(z) -{ 1 }-> 1 :|: z = 0
   a__g(z) -{ 1 }-> 1 + X :|: X >= 0, z = X
   mark(z) -{ 1 }-> a__g(mark(X)) :|: z = 1 + X, X >= 0
   mark(z) -{ 1 }-> a__f(X1, X2, X3) :|: X1 >= 0, X3 >= 0, z = 1 + X1 + X2 + X3, X2 >= 0
   mark(z) -{ 1 }-> a__b :|: z = 0
   mark(z) -{ 1 }-> 1 :|: z = 1

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V1, V, V2),0,[fun(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]).
eq(start(V1, V, V2),0,[fun1(V1, Out)],[V1 >= 0]).
eq(start(V1, V, V2),0,[fun2(Out)],[]).
eq(start(V1, V, V2),0,[mark(V1, Out)],[V1 >= 0]).
eq(fun(V1, V, V2, Out),1,[fun(Y1, Y1, Y1, Ret)],[Out = Ret,Y1 >= 0,V2 = Y1,V = 1 + X4,X4 >= 0,V1 = X4]).
eq(fun1(V1, Out),1,[],[Out = 1,V1 = 0]).
eq(fun2(Out),1,[],[Out = 1]).
eq(mark(V1, Out),1,[fun(X11, X21, X31, Ret1)],[Out = Ret1,X11 >= 0,X31 >= 0,V1 = 1 + X11 + X21 + X31,X21 >= 0]).
eq(mark(V1, Out),1,[mark(X5, Ret0),fun1(Ret0, Ret2)],[Out = Ret2,V1 = 1 + X5,X5 >= 0]).
eq(mark(V1, Out),1,[fun2(Ret3)],[Out = Ret3,V1 = 0]).
eq(mark(V1, Out),1,[],[Out = 1,V1 = 1]).
eq(fun(V1, V, V2, Out),1,[],[Out = 1 + X12 + X22 + X32,X12 >= 0,X32 >= 0,X22 >= 0,V1 = X12,V = X22,V2 = X32]).
eq(fun1(V1, Out),1,[],[Out = 1 + X6,X6 >= 0,V1 = X6]).
eq(fun2(Out),1,[],[Out = 0]).
input_output_vars(fun(V1,V,V2,Out),[V1,V,V2],[Out]).
input_output_vars(fun1(V1,Out),[V1],[Out]).
input_output_vars(fun2(Out),[],[Out]).
input_output_vars(mark(V1,Out),[V1],[Out]).


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

#### Computed strongly connected components 
0. recursive  : [fun/4]
1. non_recursive  : [fun1/2]
2. non_recursive  : [fun2/1]
3. recursive [non_tail] : [mark/2]
4. non_recursive  : [start/3]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into fun/4
1. SCC is partially evaluated into fun1/2
2. SCC is partially evaluated into fun2/1
3. SCC is partially evaluated into mark/2
4. SCC is partially evaluated into start/3

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

### Specialization of cost equations fun/4 
* CE 6 is refined into CE [14] 
* CE 5 is refined into CE [15] 


### Cost equations --> "Loop" of fun/4 
* CEs [15] --> Loop 10 
* CEs [14] --> Loop 11 

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

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


### Specialization of cost equations fun1/2 
* CE 7 is refined into CE [16] 


### Cost equations --> "Loop" of fun1/2 
* CEs [16] --> Loop 12 

### Ranking functions of CR fun1(V1,Out) 

#### Partial ranking functions of CR fun1(V1,Out) 


### Specialization of cost equations fun2/1 
* CE 8 is refined into CE [17] 
* CE 9 is refined into CE [18] 


### Cost equations --> "Loop" of fun2/1 
* CEs [17] --> Loop 13 
* CEs [18] --> Loop 14 

### Ranking functions of CR fun2(Out) 

#### Partial ranking functions of CR fun2(Out) 


### Specialization of cost equations mark/2 
* CE 10 is refined into CE [19,20] 
* CE 13 is refined into CE [21] 
* CE 12 is refined into CE [22,23] 
* CE 11 is refined into CE [24] 


### Cost equations --> "Loop" of mark/2 
* CEs [24] --> Loop 15 
* CEs [19] --> Loop 16 
* CEs [20,21] --> Loop 17 
* CEs [23] --> Loop 18 
* CEs [22] --> Loop 19 

### Ranking functions of CR mark(V1,Out) 
* RF of phase [15]: [V1]

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


### Specialization of cost equations start/3 
* CE 1 is refined into CE [25,26] 
* CE 2 is refined into CE [27] 
* CE 3 is refined into CE [28,29] 
* CE 4 is refined into CE [30,31,32,33,34] 


### Cost equations --> "Loop" of start/3 
* CEs [25,26,27,28,29,30,31,32,33,34] --> Loop 20 

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

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


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

#### Cost of chains of fun(V1,V,V2,Out):
* Chain [11]: 1
  with precondition: [V+V1+V2+1=Out,V1>=0,V>=0,V2>=0] 

* Chain [10,11]: 2
  with precondition: [V=V1+1,3*V2+1=Out,V>=1,V2>=0] 


#### Cost of chains of fun1(V1,Out):
* Chain [12]: 1
  with precondition: [V1+1=Out,V1>=0] 


#### Cost of chains of fun2(Out):
* Chain [14]: 1
  with precondition: [Out=0] 

* Chain [13]: 1
  with precondition: [Out=1] 


#### Cost of chains of mark(V1,Out):
* Chain [[15],19]: 2*it(15)+2
  Such that:it(15) =< Out

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

* Chain [[15],18]: 2*it(15)+2
  Such that:it(15) =< Out

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

* Chain [[15],17]: 2*it(15)+2
  Such that:it(15) =< Out

  with precondition: [V1=Out,V1>=2] 

* Chain [[15],16]: 2*it(15)+3
  Such that:it(15) =< 3/2*V1-Out/2

  with precondition: [Out>=2,3*V1>=Out+7] 

* Chain [19]: 2
  with precondition: [V1=0,Out=0] 

* Chain [18]: 2
  with precondition: [V1=0,Out=1] 

* Chain [17]: 2
  with precondition: [V1=Out,V1>=1] 

* Chain [16]: 3
  with precondition: [Out>=1,3*V1>=Out+5] 


#### Cost of chains of start(V1,V,V2):
* Chain [20]: 2*s(4)+4*s(6)+2*s(7)+3
  Such that:s(5) =< V1
s(4) =< V1+1
s(7) =< 3/2*V1
s(6) =< s(5)

  with precondition: [] 


Closed-form bounds of start(V1,V,V2): 
-------------------------------------
* Chain [20] with precondition: [] 
    - Upper bound: nat(V1)*4+3+nat(3/2*V1)*2+nat(V1+1)*2 
    - Complexity: n 

### Maximum cost of start(V1,V,V2): nat(V1)*4+3+nat(3/2*V1)*2+nat(V1+1)*2 
Asymptotic class: n 
* Total analysis performed in 113 ms.


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

(12)
BOUNDS(1, n^1)

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

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

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

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


The TRS R consists of the following rules:

   a__f(X, g(X), Y) -> a__f(Y, Y, Y)
   a__g(b) -> c
   a__b -> c
   mark(f(X1, X2, X3)) -> a__f(X1, X2, X3)
   mark(g(X)) -> a__g(mark(X))
   mark(b) -> a__b
   mark(c) -> c
   a__f(X1, X2, X3) -> f(X1, X2, X3)
   a__g(X) -> g(X)
   a__b -> b

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

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

The rewrite sequence

mark(g(X)) ->^+ a__g(mark(X))

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

The pumping substitution is [X / g(X)].

The result substitution is [ ].




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

(16)
Complex Obligation (BEST)

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

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

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


The TRS R consists of the following rules:

   a__f(X, g(X), Y) -> a__f(Y, Y, Y)
   a__g(b) -> c
   a__b -> c
   mark(f(X1, X2, X3)) -> a__f(X1, X2, X3)
   mark(g(X)) -> a__g(mark(X))
   mark(b) -> a__b
   mark(c) -> c
   a__f(X1, X2, X3) -> f(X1, X2, X3)
   a__g(X) -> g(X)
   a__b -> b

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

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

(19)
BOUNDS(n^1, INF)

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

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

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


The TRS R consists of the following rules:

   a__f(X, g(X), Y) -> a__f(Y, Y, Y)
   a__g(b) -> c
   a__b -> c
   mark(f(X1, X2, X3)) -> a__f(X1, X2, X3)
   mark(g(X)) -> a__g(mark(X))
   mark(b) -> a__b
   mark(c) -> c
   a__f(X1, X2, X3) -> f(X1, X2, X3)
   a__g(X) -> g(X)
   a__b -> b

S is empty.
Rewrite Strategy: FULL