14.15/4.63 WORST_CASE(Omega(n^1), O(n^1)) 14.15/4.64 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 14.15/4.64 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.15/4.64 14.15/4.64 14.15/4.64 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 14.15/4.64 14.15/4.64 (0) CpxTRS 14.15/4.64 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 14.15/4.64 (2) CpxWeightedTrs 14.15/4.64 (3) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 3 ms] 14.15/4.64 (4) CpxWeightedTrs 14.15/4.64 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 14.15/4.64 (6) CpxTypedWeightedTrs 14.15/4.64 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 14.15/4.64 (8) CpxTypedWeightedCompleteTrs 14.15/4.64 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 14.15/4.64 (10) CpxRNTS 14.15/4.64 (11) CompleteCoflocoProof [FINISHED, 242 ms] 14.15/4.64 (12) BOUNDS(1, n^1) 14.15/4.64 (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 14.15/4.64 (14) TRS for Loop Detection 14.15/4.64 (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 14.15/4.64 (16) BEST 14.15/4.64 (17) proven lower bound 14.15/4.64 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 14.15/4.64 (19) BOUNDS(n^1, INF) 14.15/4.64 (20) TRS for Loop Detection 14.15/4.64 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (0) 14.15/4.64 Obligation: 14.15/4.64 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 14.15/4.64 14.15/4.64 14.15/4.64 The TRS R consists of the following rules: 14.15/4.64 14.15/4.64 del(.(x, .(y, z))) -> f(=(x, y), x, y, z) 14.15/4.64 f(true, x, y, z) -> del(.(y, z)) 14.15/4.64 f(false, x, y, z) -> .(x, del(.(y, z))) 14.15/4.64 =(nil, nil) -> true 14.15/4.64 =(.(x, y), nil) -> false 14.15/4.64 =(nil, .(y, z)) -> false 14.15/4.64 =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) 14.15/4.64 14.15/4.64 S is empty. 14.15/4.64 Rewrite Strategy: INNERMOST 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 14.15/4.64 Transformed relative TRS to weighted TRS 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (2) 14.15/4.64 Obligation: 14.15/4.64 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 14.15/4.64 14.15/4.64 14.15/4.64 The TRS R consists of the following rules: 14.15/4.64 14.15/4.64 del(.(x, .(y, z))) -> f(=(x, y), x, y, z) [1] 14.15/4.64 f(true, x, y, z) -> del(.(y, z)) [1] 14.15/4.64 f(false, x, y, z) -> .(x, del(.(y, z))) [1] 14.15/4.64 =(nil, nil) -> true [1] 14.15/4.64 =(.(x, y), nil) -> false [1] 14.15/4.64 =(nil, .(y, z)) -> false [1] 14.15/4.64 =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) [1] 14.15/4.64 14.15/4.64 Rewrite Strategy: INNERMOST 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (3) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) 14.15/4.64 Renamed defined symbols to avoid conflicts with arithmetic symbols: 14.15/4.64 14.15/4.64 = => eq 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (4) 14.15/4.64 Obligation: 14.15/4.64 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 14.15/4.64 14.15/4.64 14.15/4.64 The TRS R consists of the following rules: 14.15/4.64 14.15/4.64 del(.(x, .(y, z))) -> f(eq(x, y), x, y, z) [1] 14.15/4.64 f(true, x, y, z) -> del(.(y, z)) [1] 14.15/4.64 f(false, x, y, z) -> .(x, del(.(y, z))) [1] 14.15/4.64 eq(nil, nil) -> true [1] 14.15/4.64 eq(.(x, y), nil) -> false [1] 14.15/4.64 eq(nil, .(y, z)) -> false [1] 14.15/4.64 eq(.(x, y), .(u, v)) -> and(eq(x, u), eq(y, v)) [1] 14.15/4.64 14.15/4.64 Rewrite Strategy: INNERMOST 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 14.15/4.64 Infered types. 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (6) 14.15/4.64 Obligation: 14.15/4.64 Runtime Complexity Weighted TRS with Types. 14.15/4.64 The TRS R consists of the following rules: 14.15/4.64 14.15/4.64 del(.(x, .(y, z))) -> f(eq(x, y), x, y, z) [1] 14.15/4.64 f(true, x, y, z) -> del(.(y, z)) [1] 14.15/4.64 f(false, x, y, z) -> .(x, del(.(y, z))) [1] 14.15/4.64 eq(nil, nil) -> true [1] 14.15/4.64 eq(.(x, y), nil) -> false [1] 14.15/4.64 eq(nil, .(y, z)) -> false [1] 14.15/4.64 eq(.(x, y), .(u, v)) -> and(eq(x, u), eq(y, v)) [1] 14.15/4.64 14.15/4.64 The TRS has the following type information: 14.15/4.64 del :: .:nil:u:v -> .:nil:u:v 14.15/4.64 . :: .:nil:u:v -> .:nil:u:v -> .:nil:u:v 14.15/4.64 f :: true:false:and -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v 14.15/4.64 eq :: .:nil:u:v -> .:nil:u:v -> true:false:and 14.15/4.64 true :: true:false:and 14.15/4.64 false :: true:false:and 14.15/4.64 nil :: .:nil:u:v 14.15/4.64 u :: .:nil:u:v 14.15/4.64 v :: .:nil:u:v 14.15/4.64 and :: true:false:and -> true:false:and -> true:false:and 14.15/4.64 14.15/4.64 Rewrite Strategy: INNERMOST 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (7) CompletionProof (UPPER BOUND(ID)) 14.15/4.64 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 14.15/4.64 14.15/4.64 del(v0) -> null_del [0] 14.15/4.64 f(v0, v1, v2, v3) -> null_f [0] 14.15/4.64 eq(v0, v1) -> null_eq [0] 14.15/4.64 14.15/4.64 And the following fresh constants: null_del, null_f, null_eq 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (8) 14.15/4.64 Obligation: 14.15/4.64 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 14.15/4.64 14.15/4.64 Runtime Complexity Weighted TRS with Types. 14.15/4.64 The TRS R consists of the following rules: 14.15/4.64 14.15/4.64 del(.(x, .(y, z))) -> f(eq(x, y), x, y, z) [1] 14.15/4.64 f(true, x, y, z) -> del(.(y, z)) [1] 14.15/4.64 f(false, x, y, z) -> .(x, del(.(y, z))) [1] 14.15/4.64 eq(nil, nil) -> true [1] 14.15/4.64 eq(.(x, y), nil) -> false [1] 14.15/4.64 eq(nil, .(y, z)) -> false [1] 14.15/4.64 eq(.(x, y), .(u, v)) -> and(eq(x, u), eq(y, v)) [1] 14.15/4.64 del(v0) -> null_del [0] 14.15/4.64 f(v0, v1, v2, v3) -> null_f [0] 14.15/4.64 eq(v0, v1) -> null_eq [0] 14.15/4.64 14.15/4.64 The TRS has the following type information: 14.15/4.64 del :: .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f 14.15/4.64 . :: .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f 14.15/4.64 f :: true:false:and:null_eq -> .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f 14.15/4.64 eq :: .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f -> true:false:and:null_eq 14.15/4.64 true :: true:false:and:null_eq 14.15/4.64 false :: true:false:and:null_eq 14.15/4.64 nil :: .:nil:u:v:null_del:null_f 14.15/4.64 u :: .:nil:u:v:null_del:null_f 14.15/4.64 v :: .:nil:u:v:null_del:null_f 14.15/4.64 and :: true:false:and:null_eq -> true:false:and:null_eq -> true:false:and:null_eq 14.15/4.64 null_del :: .:nil:u:v:null_del:null_f 14.15/4.64 null_f :: .:nil:u:v:null_del:null_f 14.15/4.64 null_eq :: true:false:and:null_eq 14.15/4.64 14.15/4.64 Rewrite Strategy: INNERMOST 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 14.15/4.64 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 14.15/4.64 The constant constructors are abstracted as follows: 14.15/4.64 14.15/4.64 true => 1 14.15/4.64 false => 0 14.15/4.64 nil => 0 14.15/4.64 u => 1 14.15/4.64 v => 2 14.15/4.64 null_del => 0 14.15/4.64 null_f => 0 14.15/4.64 null_eq => 0 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (10) 14.15/4.64 Obligation: 14.15/4.64 Complexity RNTS consisting of the following rules: 14.15/4.64 14.15/4.64 del(z') -{ 1 }-> f(eq(x, y), x, y, z) :|: z' = 1 + x + (1 + y + z), z >= 0, x >= 0, y >= 0 14.15/4.64 del(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 14.15/4.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 14.15/4.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 1 + x + y, x >= 0, y >= 0 14.15/4.64 eq(z', z'') -{ 1 }-> 0 :|: z >= 0, y >= 0, z'' = 1 + y + z, z' = 0 14.15/4.64 eq(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 14.15/4.64 eq(z', z'') -{ 1 }-> 1 + eq(x, 1) + eq(y, 2) :|: z'' = 1 + 1 + 2, z' = 1 + x + y, x >= 0, y >= 0 14.15/4.64 f(z', z'', z1, z2) -{ 1 }-> del(1 + y + z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1 14.15/4.64 f(z', z'', z1, z2) -{ 0 }-> 0 :|: z2 = v3, v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, v3 >= 0, z' = v0 14.15/4.64 f(z', z'', z1, z2) -{ 1 }-> 1 + x + del(1 + y + z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 0 14.15/4.64 14.15/4.64 Only complete derivations are relevant for the runtime complexity. 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (11) CompleteCoflocoProof (FINISHED) 14.15/4.64 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 14.15/4.64 14.15/4.64 eq(start(V, V6, V9, V7),0,[del(V, Out)],[V >= 0]). 14.15/4.64 eq(start(V, V6, V9, V7),0,[f(V, V6, V9, V7, Out)],[V >= 0,V6 >= 0,V9 >= 0,V7 >= 0]). 14.15/4.64 eq(start(V, V6, V9, V7),0,[eq(V, V6, Out)],[V >= 0,V6 >= 0]). 14.15/4.64 eq(del(V, Out),1,[eq(V2, V1, Ret0),f(Ret0, V2, V1, V3, Ret)],[Out = Ret,V = 2 + V1 + V2 + V3,V3 >= 0,V2 >= 0,V1 >= 0]). 14.15/4.64 eq(f(V, V6, V9, V7, Out),1,[del(1 + V8 + V4, Ret1)],[Out = Ret1,V9 = V8,V4 >= 0,V7 = V4,V5 >= 0,V8 >= 0,V6 = V5,V = 1]). 14.15/4.64 eq(f(V, V6, V9, V7, Out),1,[del(1 + V10 + V12, Ret11)],[Out = 1 + Ret11 + V11,V9 = V10,V12 >= 0,V7 = V12,V11 >= 0,V10 >= 0,V6 = V11,V = 0]). 14.15/4.64 eq(eq(V, V6, Out),1,[],[Out = 1,V6 = 0,V = 0]). 14.15/4.64 eq(eq(V, V6, Out),1,[],[Out = 0,V6 = 0,V = 1 + V13 + V14,V13 >= 0,V14 >= 0]). 14.15/4.64 eq(eq(V, V6, Out),1,[],[Out = 0,V15 >= 0,V16 >= 0,V6 = 1 + V15 + V16,V = 0]). 14.15/4.64 eq(eq(V, V6, Out),1,[eq(V17, 1, Ret01),eq(V18, 2, Ret12)],[Out = 1 + Ret01 + Ret12,V6 = 4,V = 1 + V17 + V18,V17 >= 0,V18 >= 0]). 14.15/4.64 eq(del(V, Out),0,[],[Out = 0,V19 >= 0,V = V19]). 14.15/4.64 eq(f(V, V6, V9, V7, Out),0,[],[Out = 0,V7 = V22,V21 >= 0,V9 = V23,V20 >= 0,V6 = V20,V23 >= 0,V22 >= 0,V = V21]). 14.15/4.64 eq(eq(V, V6, Out),0,[],[Out = 0,V25 >= 0,V24 >= 0,V6 = V24,V = V25]). 14.15/4.64 input_output_vars(del(V,Out),[V],[Out]). 14.15/4.64 input_output_vars(f(V,V6,V9,V7,Out),[V,V6,V9,V7],[Out]). 14.15/4.64 input_output_vars(eq(V,V6,Out),[V,V6],[Out]). 14.15/4.64 14.15/4.64 14.15/4.64 CoFloCo proof output: 14.15/4.64 Preprocessing Cost Relations 14.15/4.64 ===================================== 14.15/4.64 14.15/4.64 #### Computed strongly connected components 14.15/4.64 0. recursive [multiple] : [eq/3] 14.15/4.64 1. recursive : [del/2,f/5] 14.15/4.64 2. non_recursive : [start/4] 14.15/4.64 14.15/4.64 #### Obtained direct recursion through partial evaluation 14.15/4.64 0. SCC is partially evaluated into eq/3 14.15/4.64 1. SCC is partially evaluated into del/2 14.15/4.64 2. SCC is partially evaluated into start/4 14.15/4.64 14.15/4.64 Control-Flow Refinement of Cost Relations 14.15/4.64 ===================================== 14.15/4.64 14.15/4.64 ### Specialization of cost equations eq/3 14.15/4.64 * CE 11 is refined into CE [15] 14.15/4.64 * CE 12 is refined into CE [16] 14.15/4.64 * CE 14 is refined into CE [17] 14.15/4.64 * CE 10 is refined into CE [18] 14.15/4.64 * CE 13 is refined into CE [19] 14.15/4.64 14.15/4.64 14.15/4.64 ### Cost equations --> "Loop" of eq/3 14.15/4.64 * CEs [19] --> Loop 10 14.15/4.64 * CEs [15] --> Loop 11 14.15/4.64 * CEs [16,17] --> Loop 12 14.15/4.64 * CEs [18] --> Loop 13 14.15/4.64 14.15/4.64 ### Ranking functions of CR eq(V,V6,Out) 14.15/4.64 14.15/4.64 #### Partial ranking functions of CR eq(V,V6,Out) 14.15/4.64 14.15/4.64 14.15/4.64 ### Specialization of cost equations del/2 14.15/4.64 * CE 6 is refined into CE [20,21,22] 14.15/4.64 * CE 9 is refined into CE [23] 14.15/4.64 * CE 7 is refined into CE [24] 14.15/4.64 * CE 8 is refined into CE [25,26] 14.15/4.64 14.15/4.64 14.15/4.64 ### Cost equations --> "Loop" of del/2 14.15/4.64 * CEs [24] --> Loop 14 14.15/4.64 * CEs [26] --> Loop 15 14.15/4.64 * CEs [25] --> Loop 16 14.15/4.64 * CEs [20,21,22,23] --> Loop 17 14.15/4.64 14.15/4.64 ### Ranking functions of CR del(V,Out) 14.15/4.64 * RF of phase [14,15,16]: [V-1] 14.15/4.64 14.15/4.64 #### Partial ranking functions of CR del(V,Out) 14.15/4.64 * Partial RF of phase [14,15,16]: 14.15/4.64 - RF of loop [14:1,16:1]: 14.15/4.64 V-1 14.15/4.64 - RF of loop [15:1]: 14.15/4.64 V/2-3 14.15/4.64 14.15/4.64 14.15/4.64 ### Specialization of cost equations start/4 14.15/4.64 * CE 3 is refined into CE [27,28] 14.15/4.64 * CE 1 is refined into CE [29] 14.15/4.64 * CE 2 is refined into CE [30,31] 14.15/4.64 * CE 4 is refined into CE [32,33] 14.15/4.64 * CE 5 is refined into CE [34,35,36] 14.15/4.64 14.15/4.64 14.15/4.64 ### Cost equations --> "Loop" of start/4 14.15/4.64 * CEs [36] --> Loop 18 14.15/4.64 * CEs [27,28] --> Loop 19 14.15/4.64 * CEs [30,31] --> Loop 20 14.15/4.64 * CEs [29,32,33,34,35] --> Loop 21 14.15/4.64 14.15/4.64 ### Ranking functions of CR start(V,V6,V9,V7) 14.15/4.64 14.15/4.64 #### Partial ranking functions of CR start(V,V6,V9,V7) 14.15/4.64 14.15/4.64 14.15/4.64 Computing Bounds 14.15/4.64 ===================================== 14.15/4.64 14.15/4.64 #### Cost of chains of eq(V,V6,Out): 14.15/4.64 * Chain [13]: 1 14.15/4.64 with precondition: [V=0,V6=0,Out=1] 14.15/4.64 14.15/4.64 * Chain [12]: 1 14.15/4.64 with precondition: [Out=0,V>=0,V6>=0] 14.15/4.64 14.15/4.64 * Chain [11]: 1 14.15/4.64 with precondition: [V6=0,Out=0,V>=1] 14.15/4.64 14.15/4.64 * Chain [multiple(10,[[12]])]: 3 14.15/4.64 with precondition: [V6=4,Out=1,V>=1] 14.15/4.64 14.15/4.64 14.15/4.64 #### Cost of chains of del(V,Out): 14.15/4.64 * Chain [[14,15,16],17]: 6*it(14)+5*it(15)+4 14.15/4.64 Such that:it(15) =< V/2 14.15/4.64 aux(3) =< V 14.15/4.64 it(14) =< aux(3) 14.15/4.64 it(15) =< aux(3) 14.15/4.64 14.15/4.64 with precondition: [V>=2,Out>=0,V>=Out+1] 14.15/4.64 14.15/4.64 * Chain [17]: 4 14.15/4.64 with precondition: [Out=0,V>=0] 14.15/4.64 14.15/4.64 14.15/4.64 #### Cost of chains of start(V,V6,V9,V7): 14.15/4.64 * Chain [21]: 5*s(1)+6*s(3)+4 14.15/4.64 Such that:s(2) =< V 14.15/4.64 s(1) =< V/2 14.15/4.64 s(3) =< s(2) 14.15/4.64 s(1) =< s(2) 14.15/4.64 14.15/4.64 with precondition: [V>=0] 14.15/4.64 14.15/4.64 * Chain [20]: 5*s(4)+6*s(6)+5 14.15/4.64 Such that:s(5) =< V9+V7+1 14.15/4.64 s(4) =< V9/2+V7/2+1/2 14.15/4.64 s(6) =< s(5) 14.15/4.64 s(4) =< s(5) 14.15/4.64 14.15/4.64 with precondition: [V=0,V6>=0,V9>=0,V7>=0] 14.15/4.64 14.15/4.64 * Chain [19]: 5*s(7)+6*s(9)+5 14.15/4.64 Such that:s(8) =< V9+V7+1 14.15/4.64 s(7) =< V9/2+V7/2+1/2 14.15/4.64 s(9) =< s(8) 14.15/4.64 s(7) =< s(8) 14.15/4.64 14.15/4.64 with precondition: [V=1,V6>=0,V9>=0,V7>=0] 14.15/4.64 14.15/4.64 * Chain [18]: 3 14.15/4.64 with precondition: [V6=4,V>=1] 14.15/4.64 14.15/4.64 14.15/4.64 Closed-form bounds of start(V,V6,V9,V7): 14.15/4.64 ------------------------------------- 14.15/4.64 * Chain [21] with precondition: [V>=0] 14.15/4.64 - Upper bound: 17/2*V+4 14.15/4.64 - Complexity: n 14.15/4.64 * Chain [20] with precondition: [V=0,V6>=0,V9>=0,V7>=0] 14.15/4.64 - Upper bound: 17/2*V9+17/2*V7+27/2 14.15/4.64 - Complexity: n 14.15/4.64 * Chain [19] with precondition: [V=1,V6>=0,V9>=0,V7>=0] 14.15/4.64 - Upper bound: 17/2*V9+17/2*V7+27/2 14.15/4.64 - Complexity: n 14.15/4.64 * Chain [18] with precondition: [V6=4,V>=1] 14.15/4.64 - Upper bound: 3 14.15/4.64 - Complexity: constant 14.15/4.64 14.15/4.64 ### Maximum cost of start(V,V6,V9,V7): max([17/2*V+1,nat(V9+V7+1)*6+2+nat(V9/2+V7/2+1/2)*5])+3 14.15/4.64 Asymptotic class: n 14.15/4.64 * Total analysis performed in 159 ms. 14.15/4.64 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (12) 14.15/4.64 BOUNDS(1, n^1) 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 14.15/4.64 Transformed a relative TRS into a decreasing-loop problem. 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (14) 14.15/4.64 Obligation: 14.15/4.64 Analyzing the following TRS for decreasing loops: 14.15/4.64 14.15/4.64 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 14.15/4.64 14.15/4.64 14.15/4.64 The TRS R consists of the following rules: 14.15/4.64 14.15/4.64 del(.(x, .(y, z))) -> f(=(x, y), x, y, z) 14.15/4.64 f(true, x, y, z) -> del(.(y, z)) 14.15/4.64 f(false, x, y, z) -> .(x, del(.(y, z))) 14.15/4.64 =(nil, nil) -> true 14.15/4.64 =(.(x, y), nil) -> false 14.15/4.64 =(nil, .(y, z)) -> false 14.15/4.64 =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) 14.15/4.64 14.15/4.64 S is empty. 14.15/4.64 Rewrite Strategy: INNERMOST 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (15) DecreasingLoopProof (LOWER BOUND(ID)) 14.15/4.64 The following loop(s) give(s) rise to the lower bound Omega(n^1): 14.15/4.64 14.15/4.64 The rewrite sequence 14.15/4.64 14.15/4.64 f(true, x, nil, .(nil, z3_0)) ->^+ f(true, nil, nil, z3_0) 14.15/4.64 14.15/4.64 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 14.15/4.64 14.15/4.64 The pumping substitution is [z3_0 / .(nil, z3_0)]. 14.15/4.64 14.15/4.64 The result substitution is [x / nil]. 14.15/4.64 14.15/4.64 14.15/4.64 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (16) 14.15/4.64 Complex Obligation (BEST) 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (17) 14.15/4.64 Obligation: 14.15/4.64 Proved the lower bound n^1 for the following obligation: 14.15/4.64 14.15/4.64 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 14.15/4.64 14.15/4.64 14.15/4.64 The TRS R consists of the following rules: 14.15/4.64 14.15/4.64 del(.(x, .(y, z))) -> f(=(x, y), x, y, z) 14.15/4.64 f(true, x, y, z) -> del(.(y, z)) 14.15/4.64 f(false, x, y, z) -> .(x, del(.(y, z))) 14.15/4.64 =(nil, nil) -> true 14.15/4.64 =(.(x, y), nil) -> false 14.15/4.64 =(nil, .(y, z)) -> false 14.15/4.64 =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) 14.15/4.64 14.15/4.64 S is empty. 14.15/4.64 Rewrite Strategy: INNERMOST 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (18) LowerBoundPropagationProof (FINISHED) 14.15/4.64 Propagated lower bound. 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (19) 14.15/4.64 BOUNDS(n^1, INF) 14.15/4.64 14.15/4.64 ---------------------------------------- 14.15/4.64 14.15/4.64 (20) 14.15/4.64 Obligation: 14.15/4.64 Analyzing the following TRS for decreasing loops: 14.15/4.64 14.15/4.64 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 14.15/4.64 14.15/4.64 14.15/4.64 The TRS R consists of the following rules: 14.15/4.64 14.15/4.64 del(.(x, .(y, z))) -> f(=(x, y), x, y, z) 14.15/4.64 f(true, x, y, z) -> del(.(y, z)) 14.15/4.64 f(false, x, y, z) -> .(x, del(.(y, z))) 14.15/4.64 =(nil, nil) -> true 14.15/4.64 =(.(x, y), nil) -> false 14.15/4.64 =(nil, .(y, z)) -> false 14.15/4.64 =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) 14.15/4.64 14.15/4.64 S is empty. 14.15/4.64 Rewrite Strategy: INNERMOST 14.51/4.70 EOF