5.23/2.44	WORST_CASE(NON_POLY, ?)
5.23/2.44	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
5.23/2.44	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.23/2.44	
5.23/2.44	
5.23/2.44	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).
5.23/2.44	
5.23/2.44	(0) CpxIntTrs
5.23/2.44	(1) Loat Proof [FINISHED, 836 ms]
5.23/2.44	(2) BOUNDS(INF, INF)
5.23/2.44	
5.23/2.44	
5.23/2.44	----------------------------------------
5.23/2.44	
5.23/2.44	(0)
5.23/2.44	Obligation:
5.23/2.44	Complexity Int TRS consisting of the following rules:
5.23/2.44	f0(A, B, C, D, E, F) -> Com_1(f2(A, G, C, D, E, F)) :|: 0 >= A
5.23/2.44	f0(A, B, C, D, E, F) -> Com_1(f0(A, B, -(1) + C, G, 0, H)) :|: A >= 1 && C >= 3
5.23/2.44	f0(A, B, C, D, E, F) -> Com_1(f0(-(1) + A, B, I, G, H, F)) :|: 0 >= H + 1 && A >= 1
5.23/2.44	f0(A, B, C, D, E, F) -> Com_1(f0(-(1) + A, B, I, G, H, F)) :|: H >= 1 && A >= 1
5.23/2.44	f1(A, B, C, D, E, F) -> Com_1(f0(A, B, C, D, E, F)) :|: TRUE
5.23/2.44	
5.23/2.44	The start-symbols are:[f1_6]
5.23/2.44	
5.23/2.44	
5.23/2.44	----------------------------------------
5.23/2.44	
5.23/2.44	(1) Loat Proof (FINISHED)
5.23/2.44	
5.23/2.44	
5.23/2.44	### Pre-processing the ITS problem ###
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Initial linear ITS problem
5.23/2.44	
5.23/2.44	   Start location: f1
5.23/2.44	
5.23/2.44	      0: f0 -> f2 : B'=free, [ 0>=A ], cost: 1
5.23/2.44	
5.23/2.44	      1: f0 -> f0 : C'=-1+C, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: 1
5.23/2.44	
5.23/2.44	      2: f0 -> f0 : A'=-1+A, C'=free_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1
5.23/2.44	
5.23/2.44	      3: f0 -> f0 : A'=-1+A, C'=free_7, D'=free_8, E'=free_6, [ free_6>=1 && A>=1 ], cost: 1
5.23/2.44	
5.23/2.44	      4: f1 -> f0 : [], cost: 1
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Removed unreachable and leaf rules:
5.23/2.44	
5.23/2.44	   Start location: f1
5.23/2.44	
5.23/2.44	      1: f0 -> f0 : C'=-1+C, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: 1
5.23/2.44	
5.23/2.44	      2: f0 -> f0 : A'=-1+A, C'=free_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1
5.23/2.44	
5.23/2.44	      3: f0 -> f0 : A'=-1+A, C'=free_7, D'=free_8, E'=free_6, [ free_6>=1 && A>=1 ], cost: 1
5.23/2.44	
5.23/2.44	      4: f1 -> f0 : [], cost: 1
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	### Simplification by acceleration and chaining ###
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Accelerating simple loops of location 0.
5.23/2.44	
5.23/2.44	   Accelerating the following rules:
5.23/2.44	
5.23/2.44	      1: f0 -> f0 : C'=-1+C, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: 1
5.23/2.44	
5.23/2.44	      2: f0 -> f0 : A'=-1+A, C'=free_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1
5.23/2.44	
5.23/2.44	      3: f0 -> f0 : A'=-1+A, C'=free_7, D'=free_8, E'=free_6, [ free_6>=1 && A>=1 ], cost: 1
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	   Accelerated rule 1 with metering function -2+C, yielding the new rule 5.
5.23/2.44	
5.23/2.44	   Accelerated rule 2 with metering function A, yielding the new rule 6.
5.23/2.44	
5.23/2.44	   Accelerated rule 3 with metering function A, yielding the new rule 7.
5.23/2.44	
5.23/2.44	   Nested simple loops 2 (outer loop) and 5 (inner loop) with metering function -1+A, resulting in the new rules: 8, 9.
5.23/2.44	
5.23/2.44	   Nested simple loops 3 (outer loop) and 5 (inner loop) with metering function -1+A, resulting in the new rules: 10, 11.
5.23/2.44	
5.23/2.44	   Removing the simple loops: 1 2 3.
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Accelerated all simple loops using metering functions (where possible):
5.23/2.44	
5.23/2.44	   Start location: f1
5.23/2.44	
5.23/2.44	      5: f0 -> f0 : C'=2, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: -2+C
5.23/2.44	
5.23/2.44	      6: f0 -> f0 : A'=0, C'=free_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: A
5.23/2.44	
5.23/2.44	      7: f0 -> f0 : A'=0, C'=free_7, D'=free_8, E'=free_6, [ free_6>=1 && A>=1 ], cost: A
5.23/2.44	
5.23/2.44	      8: f0 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_4>=3 ], cost: 1+(-1+A)*free_4-A
5.23/2.44	
5.23/2.44	      9: f0 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_4>=3 ], cost: -1+(-1+A)*free_4+C-A
5.23/2.44	
5.23/2.44	     10: f0 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_7>=3 ], cost: 1+(-1+A)*free_7-A
5.23/2.44	
5.23/2.44	     11: f0 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_7>=3 ], cost: -1+C+(-1+A)*free_7-A
5.23/2.44	
5.23/2.44	      4: f1 -> f0 : [], cost: 1
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Chained accelerated rules (with incoming rules):
5.23/2.44	
5.23/2.44	   Start location: f1
5.23/2.44	
5.23/2.44	      4: f1 -> f0 : [], cost: 1
5.23/2.44	
5.23/2.44	     12: f1 -> f0 : C'=2, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: -1+C
5.23/2.44	
5.23/2.44	     13: f1 -> f0 : A'=0, C'=free_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1+A
5.23/2.44	
5.23/2.44	     14: f1 -> f0 : A'=0, C'=free_7, D'=free_8, E'=free_6, [ free_6>=1 && A>=1 ], cost: 1+A
5.23/2.44	
5.23/2.44	     15: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_4>=3 ], cost: 2+(-1+A)*free_4-A
5.23/2.44	
5.23/2.44	     16: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_4>=3 ], cost: (-1+A)*free_4+C-A
5.23/2.44	
5.23/2.44	     17: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_7>=3 ], cost: 2+(-1+A)*free_7-A
5.23/2.44	
5.23/2.44	     18: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_7>=3 ], cost: C+(-1+A)*free_7-A
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Removed unreachable locations (and leaf rules with constant cost):
5.23/2.44	
5.23/2.44	   Start location: f1
5.23/2.44	
5.23/2.44	     12: f1 -> f0 : C'=2, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: -1+C
5.23/2.44	
5.23/2.44	     13: f1 -> f0 : A'=0, C'=free_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1+A
5.23/2.44	
5.23/2.44	     14: f1 -> f0 : A'=0, C'=free_7, D'=free_8, E'=free_6, [ free_6>=1 && A>=1 ], cost: 1+A
5.23/2.44	
5.23/2.44	     15: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_4>=3 ], cost: 2+(-1+A)*free_4-A
5.23/2.44	
5.23/2.44	     16: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_4>=3 ], cost: (-1+A)*free_4+C-A
5.23/2.44	
5.23/2.44	     17: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_7>=3 ], cost: 2+(-1+A)*free_7-A
5.23/2.44	
5.23/2.44	     18: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_7>=3 ], cost: C+(-1+A)*free_7-A
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	### Computing asymptotic complexity ###
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Fully simplified ITS problem
5.23/2.44	
5.23/2.44	   Start location: f1
5.23/2.44	
5.23/2.44	     12: f1 -> f0 : C'=2, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: -1+C
5.23/2.44	
5.23/2.44	     13: f1 -> f0 : A'=0, C'=free_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1+A
5.23/2.44	
5.23/2.44	     14: f1 -> f0 : A'=0, C'=free_7, D'=free_8, E'=free_6, [ free_6>=1 && A>=1 ], cost: 1+A
5.23/2.44	
5.23/2.44	     15: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_4>=3 ], cost: 2+(-1+A)*free_4-A
5.23/2.44	
5.23/2.44	     16: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_4>=3 ], cost: (-1+A)*free_4+C-A
5.23/2.44	
5.23/2.44	     17: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_7>=3 ], cost: 2+(-1+A)*free_7-A
5.23/2.44	
5.23/2.44	     18: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_7>=3 ], cost: C+(-1+A)*free_7-A
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Computing asymptotic complexity for rule 12
5.23/2.44	
5.23/2.44	   Solved the limit problem by the following transformations:
5.23/2.44	
5.23/2.44	      Created initial limit problem:
5.23/2.44	
5.23/2.44	      -2+C (+/+!), A (+/+!), -1+C (+) [not solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	      removing all constraints (solved by SMT)
5.23/2.44	
5.23/2.44	      resulting limit problem: [solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	      applying transformation rule (C) using substitution {C==n,A==1}
5.23/2.44	
5.23/2.44	      resulting limit problem:
5.23/2.44	
5.23/2.44	      [solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	   Solution:
5.23/2.44	
5.23/2.44	      C / n
5.23/2.44	
5.23/2.44	      A / 1
5.23/2.44	
5.23/2.44	   Resulting cost -1+n has complexity: Poly(n^1)
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Found new complexity Poly(n^1).
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Computing asymptotic complexity for rule 15
5.23/2.44	
5.23/2.44	   Solved the limit problem by the following transformations:
5.23/2.44	
5.23/2.44	      Created initial limit problem:
5.23/2.44	
5.23/2.44	      2+A*free_4-A-free_4 (+), -1+A (+/+!), -2+free_4 (+/+!) [not solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	      applying transformation rule (C) using substitution {free_4==3}
5.23/2.44	
5.23/2.44	      resulting limit problem:
5.23/2.44	
5.23/2.44	      1 (+/+!), -1+A (+/+!), -1+2*A (+) [not solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	      applying transformation rule (B), deleting 1 (+/+!)
5.23/2.44	
5.23/2.44	      resulting limit problem:
5.23/2.44	
5.23/2.44	      -1+A (+/+!), -1+2*A (+) [not solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	      removing all constraints (solved by SMT)
5.23/2.44	
5.23/2.44	      resulting limit problem: [solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	      applying transformation rule (C) using substitution {A==n}
5.23/2.44	
5.23/2.44	      resulting limit problem:
5.23/2.44	
5.23/2.44	      [solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	   Solved the limit problem by the following transformations:
5.23/2.44	
5.23/2.44	      Created initial limit problem:
5.23/2.44	
5.23/2.44	      2+A*free_4-A-free_4 (+), -1+A (+/+!), -2+free_4 (+/+!) [not solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	      removing all constraints (solved by SMT)
5.23/2.44	
5.23/2.44	      resulting limit problem: [solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	      applying transformation rule (C) using substitution {A==2,free_4==3+n}
5.23/2.44	
5.23/2.44	      resulting limit problem:
5.23/2.44	
5.23/2.44	      [solved]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	   Solution:
5.23/2.44	
5.23/2.44	      A / 2
5.23/2.44	
5.23/2.44	      free_4 / 3+n
5.23/2.44	
5.23/2.44	   Resulting cost 3+n has complexity: Unbounded
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Found new complexity Unbounded.
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	Obtained the following overall complexity (w.r.t. the length of the input n):
5.23/2.44	
5.23/2.44	   Complexity:  Unbounded
5.23/2.44	
5.23/2.44	   Cpx degree:  Unbounded
5.23/2.44	
5.23/2.44	   Solved cost: 3+n
5.23/2.44	
5.23/2.44	   Rule cost:   2+(-1+A)*free_4-A
5.23/2.44	
5.23/2.44	   Rule guard:  [ -1+A>=1 && free_4>=3 ]
5.23/2.44	
5.23/2.44	
5.23/2.44	
5.23/2.44	WORST_CASE(INF,?)
5.23/2.44	
5.23/2.44	
5.23/2.44	----------------------------------------
5.23/2.44	
5.23/2.44	(2)
5.23/2.44	BOUNDS(INF, INF)
5.23/2.47	EOF