13.65/4.67 WORST_CASE(Omega(n^1), O(n^1)) 13.83/4.69 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 13.83/4.69 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.83/4.69 13.83/4.69 13.83/4.69 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 13.83/4.69 13.83/4.69 (0) CpxTRS 13.83/4.69 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 13.83/4.69 (2) CpxTRS 13.83/4.69 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 13.83/4.69 (4) CpxWeightedTrs 13.83/4.69 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 13.83/4.69 (6) CpxTypedWeightedTrs 13.83/4.69 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 13.83/4.69 (8) CpxTypedWeightedCompleteTrs 13.83/4.69 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 13.83/4.69 (10) CpxRNTS 13.83/4.69 (11) CompleteCoflocoProof [FINISHED, 136 ms] 13.83/4.69 (12) BOUNDS(1, n^1) 13.83/4.69 (13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 13.83/4.69 (14) CpxTRS 13.83/4.69 (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 13.83/4.69 (16) typed CpxTrs 13.83/4.69 (17) OrderProof [LOWER BOUND(ID), 0 ms] 13.83/4.69 (18) typed CpxTrs 13.83/4.69 (19) RewriteLemmaProof [LOWER BOUND(ID), 499 ms] 13.83/4.69 (20) BEST 13.83/4.69 (21) proven lower bound 13.83/4.69 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 13.83/4.69 (23) BOUNDS(n^1, INF) 13.83/4.69 (24) typed CpxTrs 13.83/4.69 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (0) 13.83/4.69 Obligation: 13.83/4.69 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 13.83/4.69 13.83/4.69 13.83/4.69 The TRS R consists of the following rules: 13.83/4.69 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) 13.83/4.69 13.83/4.69 S is empty. 13.83/4.69 Rewrite Strategy: FULL 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 13.83/4.69 Converted rc-obligation to irc-obligation. 13.83/4.69 13.83/4.69 The duplicating contexts are: 13.83/4.69 ackin(s([]), s(Y)) 13.83/4.69 13.83/4.69 13.83/4.69 The defined contexts are: 13.83/4.69 u21([], x1) 13.83/4.69 ackin(x0, []) 13.83/4.69 ackin(s(x0), []) 13.83/4.69 13.83/4.69 13.83/4.69 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (2) 13.83/4.69 Obligation: 13.83/4.69 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 13.83/4.69 13.83/4.69 13.83/4.69 The TRS R consists of the following rules: 13.83/4.69 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) 13.83/4.69 13.83/4.69 S is empty. 13.83/4.69 Rewrite Strategy: INNERMOST 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 13.83/4.69 Transformed relative TRS to weighted TRS 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (4) 13.83/4.69 Obligation: 13.83/4.69 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 13.83/4.69 13.83/4.69 13.83/4.69 The TRS R consists of the following rules: 13.83/4.69 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) [1] 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) [1] 13.83/4.69 13.83/4.69 Rewrite Strategy: INNERMOST 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 13.83/4.69 Infered types. 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (6) 13.83/4.69 Obligation: 13.83/4.69 Runtime Complexity Weighted TRS with Types. 13.83/4.69 The TRS R consists of the following rules: 13.83/4.69 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) [1] 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) [1] 13.83/4.69 13.83/4.69 The TRS has the following type information: 13.83/4.69 ackin :: s -> s -> ackout:u22 13.83/4.69 s :: s -> s 13.83/4.69 u21 :: ackout:u22 -> s -> ackout:u22 13.83/4.69 ackout :: s -> ackout:u22 13.83/4.69 u22 :: ackout:u22 -> ackout:u22 13.83/4.69 13.83/4.69 Rewrite Strategy: INNERMOST 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (7) CompletionProof (UPPER BOUND(ID)) 13.83/4.69 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 13.83/4.69 13.83/4.69 ackin(v0, v1) -> null_ackin [0] 13.83/4.69 u21(v0, v1) -> null_u21 [0] 13.83/4.69 13.83/4.69 And the following fresh constants: null_ackin, null_u21, const 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (8) 13.83/4.69 Obligation: 13.83/4.69 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 13.83/4.69 13.83/4.69 Runtime Complexity Weighted TRS with Types. 13.83/4.69 The TRS R consists of the following rules: 13.83/4.69 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) [1] 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) [1] 13.83/4.69 ackin(v0, v1) -> null_ackin [0] 13.83/4.69 u21(v0, v1) -> null_u21 [0] 13.83/4.69 13.83/4.69 The TRS has the following type information: 13.83/4.69 ackin :: s -> s -> ackout:u22:null_ackin:null_u21 13.83/4.69 s :: s -> s 13.83/4.69 u21 :: ackout:u22:null_ackin:null_u21 -> s -> ackout:u22:null_ackin:null_u21 13.83/4.69 ackout :: s -> ackout:u22:null_ackin:null_u21 13.83/4.69 u22 :: ackout:u22:null_ackin:null_u21 -> ackout:u22:null_ackin:null_u21 13.83/4.69 null_ackin :: ackout:u22:null_ackin:null_u21 13.83/4.69 null_u21 :: ackout:u22:null_ackin:null_u21 13.83/4.69 const :: s 13.83/4.69 13.83/4.69 Rewrite Strategy: INNERMOST 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 13.83/4.69 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 13.83/4.69 The constant constructors are abstracted as follows: 13.83/4.69 13.83/4.69 null_ackin => 0 13.83/4.69 null_u21 => 0 13.83/4.69 const => 0 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (10) 13.83/4.69 Obligation: 13.83/4.69 Complexity RNTS consisting of the following rules: 13.83/4.69 13.83/4.69 ackin(z, z') -{ 1 }-> u21(ackin(1 + X, Y), X) :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0 13.83/4.69 ackin(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 13.83/4.69 u21(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 13.83/4.69 u21(z, z') -{ 1 }-> 1 + ackin(Y, X) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0 13.83/4.69 13.83/4.69 Only complete derivations are relevant for the runtime complexity. 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (11) CompleteCoflocoProof (FINISHED) 13.83/4.69 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 13.83/4.69 13.83/4.69 eq(start(V1, V),0,[ackin(V1, V, Out)],[V1 >= 0,V >= 0]). 13.83/4.69 eq(start(V1, V),0,[u21(V1, V, Out)],[V1 >= 0,V >= 0]). 13.83/4.69 eq(ackin(V1, V, Out),1,[ackin(1 + X1, Y1, Ret0),u21(Ret0, X1, Ret)],[Out = Ret,V1 = 1 + X1,Y1 >= 0,V = 1 + Y1,X1 >= 0]). 13.83/4.69 eq(u21(V1, V, Out),1,[ackin(Y2, X2, Ret1)],[Out = 1 + Ret1,V1 = 1 + X2,V = Y2,Y2 >= 0,X2 >= 0]). 13.83/4.69 eq(ackin(V1, V, Out),0,[],[Out = 0,V3 >= 0,V2 >= 0,V1 = V3,V = V2]). 13.83/4.69 eq(u21(V1, V, Out),0,[],[Out = 0,V5 >= 0,V4 >= 0,V1 = V5,V = V4]). 13.83/4.69 input_output_vars(ackin(V1,V,Out),[V1,V],[Out]). 13.83/4.69 input_output_vars(u21(V1,V,Out),[V1,V],[Out]). 13.83/4.69 13.83/4.69 13.83/4.69 CoFloCo proof output: 13.83/4.69 Preprocessing Cost Relations 13.83/4.69 ===================================== 13.83/4.69 13.83/4.69 #### Computed strongly connected components 13.83/4.69 0. recursive [multiple] : [ackin/3,u21/3] 13.83/4.69 1. non_recursive : [start/2] 13.83/4.69 13.83/4.69 #### Obtained direct recursion through partial evaluation 13.83/4.69 0. SCC is partially evaluated into ackin/3 13.83/4.69 1. SCC is partially evaluated into start/2 13.83/4.69 13.83/4.69 Control-Flow Refinement of Cost Relations 13.83/4.69 ===================================== 13.83/4.69 13.83/4.69 ### Specialization of cost equations ackin/3 13.83/4.69 * CE 6 is refined into CE [7] 13.83/4.69 * CE 5 is refined into CE [8] 13.83/4.69 * CE 4 is refined into CE [9] 13.83/4.69 13.83/4.69 13.83/4.69 ### Cost equations --> "Loop" of ackin/3 13.83/4.69 * CEs [9] --> Loop 5 13.83/4.69 * CEs [8] --> Loop 6 13.83/4.69 * CEs [7] --> Loop 7 13.83/4.69 13.83/4.69 ### Ranking functions of CR ackin(V1,V,Out) 13.83/4.69 13.83/4.69 #### Partial ranking functions of CR ackin(V1,V,Out) 13.83/4.69 * Partial RF of phase [5,6]: 13.83/4.69 - RF of loop [5:1,6:1]: 13.83/4.69 V depends on loops [6:2] 13.83/4.69 - RF of loop [6:2]: 13.83/4.69 V1 13.83/4.69 13.83/4.69 13.83/4.69 ### Specialization of cost equations start/2 13.83/4.69 * CE 1 is refined into CE [10] 13.83/4.69 * CE 2 is refined into CE [11] 13.83/4.69 * CE 3 is refined into CE [12] 13.83/4.69 13.83/4.69 13.83/4.69 ### Cost equations --> "Loop" of start/2 13.83/4.69 * CEs [10,11,12] --> Loop 8 13.83/4.69 13.83/4.69 ### Ranking functions of CR start(V1,V) 13.83/4.69 13.83/4.69 #### Partial ranking functions of CR start(V1,V) 13.83/4.69 13.83/4.69 13.83/4.69 Computing Bounds 13.83/4.69 ===================================== 13.83/4.69 13.83/4.69 #### Cost of chains of ackin(V1,V,Out): 13.83/4.69 * Chain [7]: 0 13.83/4.69 with precondition: [Out=0,V1>=0,V>=0] 13.83/4.69 13.83/4.69 * Chain [multiple([5,6],[[7]])]: 1*it(5)+0 13.83/4.69 Such that:it(5) =< V 13.83/4.69 13.83/4.69 with precondition: [Out=0,V1>=1,V>=1] 13.83/4.69 13.83/4.69 13.83/4.69 #### Cost of chains of start(V1,V): 13.83/4.69 * Chain [8]: 1*s(2)+1*s(3)+1 13.83/4.69 Such that:s(2) =< V1 13.83/4.69 s(3) =< V 13.83/4.69 13.83/4.69 with precondition: [V1>=0,V>=0] 13.83/4.69 13.83/4.69 13.83/4.69 Closed-form bounds of start(V1,V): 13.83/4.69 ------------------------------------- 13.83/4.69 * Chain [8] with precondition: [V1>=0,V>=0] 13.83/4.69 - Upper bound: V1+V+1 13.83/4.69 - Complexity: n 13.83/4.69 13.83/4.69 ### Maximum cost of start(V1,V): V1+V+1 13.83/4.69 Asymptotic class: n 13.83/4.69 * Total analysis performed in 73 ms. 13.83/4.69 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (12) 13.83/4.69 BOUNDS(1, n^1) 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (13) RenamingProof (BOTH BOUNDS(ID, ID)) 13.83/4.69 Renamed function symbols to avoid clashes with predefined symbol. 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (14) 13.83/4.69 Obligation: 13.83/4.69 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 13.83/4.69 13.83/4.69 13.83/4.69 The TRS R consists of the following rules: 13.83/4.69 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) 13.83/4.69 13.83/4.69 S is empty. 13.83/4.69 Rewrite Strategy: FULL 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (15) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 13.83/4.69 Infered types. 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (16) 13.83/4.69 Obligation: 13.83/4.69 TRS: 13.83/4.69 Rules: 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) 13.83/4.69 13.83/4.69 Types: 13.83/4.69 ackin :: s -> s -> ackout:u22 13.83/4.69 s :: s -> s 13.83/4.69 u21 :: ackout:u22 -> s -> ackout:u22 13.83/4.69 ackout :: s -> ackout:u22 13.83/4.69 u22 :: ackout:u22 -> ackout:u22 13.83/4.69 hole_ackout:u221_0 :: ackout:u22 13.83/4.69 hole_s2_0 :: s 13.83/4.69 gen_ackout:u223_0 :: Nat -> ackout:u22 13.83/4.69 gen_s4_0 :: Nat -> s 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (17) OrderProof (LOWER BOUND(ID)) 13.83/4.69 Heuristically decided to analyse the following defined symbols: 13.83/4.69 ackin, u21 13.83/4.69 13.83/4.69 They will be analysed ascendingly in the following order: 13.83/4.69 ackin = u21 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (18) 13.83/4.69 Obligation: 13.83/4.69 TRS: 13.83/4.69 Rules: 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) 13.83/4.69 13.83/4.69 Types: 13.83/4.69 ackin :: s -> s -> ackout:u22 13.83/4.69 s :: s -> s 13.83/4.69 u21 :: ackout:u22 -> s -> ackout:u22 13.83/4.69 ackout :: s -> ackout:u22 13.83/4.69 u22 :: ackout:u22 -> ackout:u22 13.83/4.69 hole_ackout:u221_0 :: ackout:u22 13.83/4.69 hole_s2_0 :: s 13.83/4.69 gen_ackout:u223_0 :: Nat -> ackout:u22 13.83/4.69 gen_s4_0 :: Nat -> s 13.83/4.69 13.83/4.69 13.83/4.69 Generator Equations: 13.83/4.69 gen_ackout:u223_0(0) <=> ackout(hole_s2_0) 13.83/4.69 gen_ackout:u223_0(+(x, 1)) <=> u22(gen_ackout:u223_0(x)) 13.83/4.69 gen_s4_0(0) <=> hole_s2_0 13.83/4.69 gen_s4_0(+(x, 1)) <=> s(gen_s4_0(x)) 13.83/4.69 13.83/4.69 13.83/4.69 The following defined symbols remain to be analysed: 13.83/4.69 u21, ackin 13.83/4.69 13.83/4.69 They will be analysed ascendingly in the following order: 13.83/4.69 ackin = u21 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (19) RewriteLemmaProof (LOWER BOUND(ID)) 13.83/4.69 Proved the following rewrite lemma: 13.83/4.69 ackin(gen_s4_0(1), gen_s4_0(+(1, n115_0))) -> *5_0, rt in Omega(n115_0) 13.83/4.69 13.83/4.69 Induction Base: 13.83/4.69 ackin(gen_s4_0(1), gen_s4_0(+(1, 0))) 13.83/4.69 13.83/4.69 Induction Step: 13.83/4.69 ackin(gen_s4_0(1), gen_s4_0(+(1, +(n115_0, 1)))) ->_R^Omega(1) 13.83/4.69 u21(ackin(s(gen_s4_0(0)), gen_s4_0(+(1, n115_0))), gen_s4_0(0)) ->_IH 13.83/4.69 u21(*5_0, gen_s4_0(0)) 13.83/4.69 13.83/4.69 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (20) 13.83/4.69 Complex Obligation (BEST) 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (21) 13.83/4.69 Obligation: 13.83/4.69 Proved the lower bound n^1 for the following obligation: 13.83/4.69 13.83/4.69 TRS: 13.83/4.69 Rules: 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) 13.83/4.69 13.83/4.69 Types: 13.83/4.69 ackin :: s -> s -> ackout:u22 13.83/4.69 s :: s -> s 13.83/4.69 u21 :: ackout:u22 -> s -> ackout:u22 13.83/4.69 ackout :: s -> ackout:u22 13.83/4.69 u22 :: ackout:u22 -> ackout:u22 13.83/4.69 hole_ackout:u221_0 :: ackout:u22 13.83/4.69 hole_s2_0 :: s 13.83/4.69 gen_ackout:u223_0 :: Nat -> ackout:u22 13.83/4.69 gen_s4_0 :: Nat -> s 13.83/4.69 13.83/4.69 13.83/4.69 Generator Equations: 13.83/4.69 gen_ackout:u223_0(0) <=> ackout(hole_s2_0) 13.83/4.69 gen_ackout:u223_0(+(x, 1)) <=> u22(gen_ackout:u223_0(x)) 13.83/4.69 gen_s4_0(0) <=> hole_s2_0 13.83/4.69 gen_s4_0(+(x, 1)) <=> s(gen_s4_0(x)) 13.83/4.69 13.83/4.69 13.83/4.69 The following defined symbols remain to be analysed: 13.83/4.69 ackin 13.83/4.69 13.83/4.69 They will be analysed ascendingly in the following order: 13.83/4.69 ackin = u21 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (22) LowerBoundPropagationProof (FINISHED) 13.83/4.69 Propagated lower bound. 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (23) 13.83/4.69 BOUNDS(n^1, INF) 13.83/4.69 13.83/4.69 ---------------------------------------- 13.83/4.69 13.83/4.69 (24) 13.83/4.69 Obligation: 13.83/4.69 TRS: 13.83/4.69 Rules: 13.83/4.69 ackin(s(X), s(Y)) -> u21(ackin(s(X), Y), X) 13.83/4.69 u21(ackout(X), Y) -> u22(ackin(Y, X)) 13.83/4.69 13.83/4.69 Types: 13.83/4.69 ackin :: s -> s -> ackout:u22 13.83/4.69 s :: s -> s 13.83/4.69 u21 :: ackout:u22 -> s -> ackout:u22 13.83/4.69 ackout :: s -> ackout:u22 13.83/4.69 u22 :: ackout:u22 -> ackout:u22 13.83/4.69 hole_ackout:u221_0 :: ackout:u22 13.83/4.69 hole_s2_0 :: s 13.83/4.69 gen_ackout:u223_0 :: Nat -> ackout:u22 13.83/4.69 gen_s4_0 :: Nat -> s 13.83/4.69 13.83/4.69 13.83/4.69 Lemmas: 13.83/4.69 ackin(gen_s4_0(1), gen_s4_0(+(1, n115_0))) -> *5_0, rt in Omega(n115_0) 13.83/4.69 13.83/4.69 13.83/4.69 Generator Equations: 13.83/4.69 gen_ackout:u223_0(0) <=> ackout(hole_s2_0) 13.83/4.69 gen_ackout:u223_0(+(x, 1)) <=> u22(gen_ackout:u223_0(x)) 13.83/4.69 gen_s4_0(0) <=> hole_s2_0 13.83/4.69 gen_s4_0(+(x, 1)) <=> s(gen_s4_0(x)) 13.83/4.69 13.83/4.69 13.83/4.69 The following defined symbols remain to be analysed: 13.83/4.69 u21 13.83/4.69 13.83/4.69 They will be analysed ascendingly in the following order: 13.83/4.69 ackin = u21 13.83/4.73 EOF