/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 182 ms] (4) CpxRelTRS (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxWeightedTrs (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxTypedWeightedTrs (9) CompletionProof [UPPER BOUND(ID), 0 ms] (10) CpxTypedWeightedCompleteTrs (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 242 ms] (14) BOUNDS(1, n^1) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(s(x), y, y) -> f(y, x, s(x)) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_s(x_1) -> s(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(s(x), y, y) -> f(y, x, s(x)) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_s(x_1) -> s(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(s(x), y, y) -> f(y, x, s(x)) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_s(x_1) -> s(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (6) 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: f(s(x), y, y) -> f(y, x, s(x)) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: f(s(x), y, y) -> f(y, x, s(x)) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] The TRS has the following type information: f :: s:cons_f -> s:cons_f -> s:cons_f -> s:cons_f s :: s:cons_f -> s:cons_f encArg :: s:cons_f -> s:cons_f cons_f :: s:cons_f -> s:cons_f -> s:cons_f -> s:cons_f encode_f :: s:cons_f -> s:cons_f -> s:cons_f -> s:cons_f encode_s :: s:cons_f -> s:cons_f Rewrite Strategy: INNERMOST ---------------------------------------- (9) 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: encArg(v0) -> null_encArg [0] encode_f(v0, v1, v2) -> null_encode_f [0] encode_s(v0) -> null_encode_s [0] f(v0, v1, v2) -> null_f [0] And the following fresh constants: null_encArg, null_encode_f, null_encode_s, null_f ---------------------------------------- (10) 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: f(s(x), y, y) -> f(y, x, s(x)) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encArg(v0) -> null_encArg [0] encode_f(v0, v1, v2) -> null_encode_f [0] encode_s(v0) -> null_encode_s [0] f(v0, v1, v2) -> null_f [0] The TRS has the following type information: f :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f s :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f encArg :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f cons_f :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f encode_f :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f encode_s :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f -> s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f null_encArg :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f null_encode_f :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f null_encode_s :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f null_f :: s:cons_f:null_encArg:null_encode_f:null_encode_s:null_f Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: null_encArg => 0 null_encode_f => 0 null_encode_s => 0 null_f => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0 encode_f(z, z', z'') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, x_3 >= 0, x_2 >= 0, z = x_1, z' = x_2, z'' = x_3 encode_f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 f(z, z', z'') -{ 1 }-> f(y, x, 1 + x) :|: z'' = y, x >= 0, y >= 0, z = 1 + x, z' = y f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (13) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V, V2),0,[f(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). eq(start(V1, V, V2),0,[encArg(V1, Out)],[V1 >= 0]). 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(f(V1, V, V2, Out),1,[f(V3, V4, 1 + V4, Ret)],[Out = Ret,V2 = V3,V4 >= 0,V3 >= 0,V1 = 1 + V4,V = V3]). eq(encArg(V1, Out),0,[encArg(V5, Ret1)],[Out = 1 + Ret1,V1 = 1 + V5,V5 >= 0]). eq(encArg(V1, Out),0,[encArg(V7, Ret0),encArg(V8, Ret11),encArg(V6, Ret2),f(Ret0, Ret11, Ret2, Ret3)],[Out = Ret3,V7 >= 0,V1 = 1 + V6 + V7 + V8,V6 >= 0,V8 >= 0]). eq(fun(V1, V, V2, Out),0,[encArg(V9, Ret01),encArg(V11, Ret12),encArg(V10, Ret21),f(Ret01, Ret12, Ret21, Ret4)],[Out = Ret4,V9 >= 0,V10 >= 0,V11 >= 0,V1 = V9,V = V11,V2 = V10]). eq(fun1(V1, Out),0,[encArg(V12, Ret13)],[Out = 1 + Ret13,V12 >= 0,V1 = V12]). eq(encArg(V1, Out),0,[],[Out = 0,V13 >= 0,V1 = V13]). eq(fun(V1, V, V2, Out),0,[],[Out = 0,V15 >= 0,V2 = V16,V14 >= 0,V1 = V15,V = V14,V16 >= 0]). eq(fun1(V1, Out),0,[],[Out = 0,V17 >= 0,V1 = V17]). eq(f(V1, V, V2, Out),0,[],[Out = 0,V18 >= 0,V2 = V19,V20 >= 0,V1 = V18,V = V20,V19 >= 0]). input_output_vars(f(V1,V,V2,Out),[V1,V,V2],[Out]). input_output_vars(encArg(V1,Out),[V1],[Out]). input_output_vars(fun(V1,V,V2,Out),[V1,V,V2],[Out]). input_output_vars(fun1(V1,Out),[V1],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [f/4] 1. recursive [non_tail,multiple] : [encArg/2] 2. non_recursive : [fun/4] 3. non_recursive : [fun1/2] 4. non_recursive : [start/3] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into f/4 1. SCC is partially evaluated into encArg/2 2. SCC is partially evaluated into fun/4 3. SCC is partially evaluated into fun1/2 4. SCC is partially evaluated into start/3 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations f/4 * CE 6 is refined into CE [14] * CE 5 is refined into CE [15] ### Cost equations --> "Loop" of f/4 * CEs [15] --> Loop 9 * CEs [14] --> Loop 10 ### Ranking functions of CR f(V1,V,V2,Out) #### Partial ranking functions of CR f(V1,V,V2,Out) ### Specialization of cost equations encArg/2 * CE 9 is refined into CE [16] * CE 8 is refined into CE [17] * CE 7 is refined into CE [18] ### Cost equations --> "Loop" of encArg/2 * CEs [18] --> Loop 11 * CEs [17] --> Loop 12 * CEs [16] --> Loop 13 ### Ranking functions of CR encArg(V1,Out) * RF of phase [11,12]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [11,12]: - RF of loop [11:1,12:1,12:2,12:3]: V1 ### Specialization of cost equations fun/4 * CE 10 is refined into CE [19,20,21,22,23,24,25,26] * CE 11 is refined into CE [27] ### Cost equations --> "Loop" of fun/4 * CEs [19,20,21,22,23,24,25,26,27] --> Loop 14 ### 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 12 is refined into CE [28,29] * CE 13 is refined into CE [30] ### Cost equations --> "Loop" of fun1/2 * CEs [29] --> Loop 15 * CEs [28] --> Loop 16 * CEs [30] --> Loop 17 ### Ranking functions of CR fun1(V1,Out) #### Partial ranking functions of CR fun1(V1,Out) ### Specialization of cost equations start/3 * CE 1 is refined into CE [31] * CE 2 is refined into CE [32,33] * CE 3 is refined into CE [34] * CE 4 is refined into CE [35,36,37] ### Cost equations --> "Loop" of start/3 * CEs [31,32,33,34,35,36,37] --> Loop 18 ### Ranking functions of CR start(V1,V,V2) #### Partial ranking functions of CR start(V1,V,V2) Computing Bounds ===================================== #### Cost of chains of f(V1,V,V2,Out): * Chain [10]: 0 with precondition: [Out=0,V1>=0,V>=0,V2>=0] * Chain [9,10]: 1 with precondition: [Out=0,V=V2,V1>=1,V>=0] #### Cost of chains of encArg(V1,Out): * Chain [13]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([11,12],[[13]])]: 1*it(12)+0 Such that:aux(4) =< V1 it(12) =< aux(4) with precondition: [V1>=1,Out>=0,V1>=Out] #### Cost of chains of fun(V1,V,V2,Out): * Chain [14]: 4*s(2)+4*s(4)+4*s(10)+1 Such that:aux(5) =< V1 aux(6) =< V aux(7) =< V2 s(10) =< aux(5) s(2) =< aux(7) s(4) =< aux(6) with precondition: [Out=0,V1>=0,V>=0,V2>=0] #### Cost of chains of fun1(V1,Out): * Chain [17]: 0 with precondition: [Out=0,V1>=0] * Chain [16]: 0 with precondition: [Out=1,V1>=0] * Chain [15]: 1*s(26)+0 Such that:s(25) =< V1 s(26) =< s(25) with precondition: [V1>=1,Out>=1,V1+1>=Out] #### Cost of chains of start(V1,V,V2): * Chain [18]: 6*s(28)+4*s(33)+4*s(34)+1 Such that:s(30) =< V s(31) =< V2 aux(8) =< V1 s(28) =< aux(8) s(33) =< s(31) s(34) =< s(30) with precondition: [V1>=0] Closed-form bounds of start(V1,V,V2): ------------------------------------- * Chain [18] with precondition: [V1>=0] - Upper bound: 6*V1+1+nat(V)*4+nat(V2)*4 - Complexity: n ### Maximum cost of start(V1,V,V2): 6*V1+1+nat(V)*4+nat(V2)*4 Asymptotic class: n * Total analysis performed in 180 ms. ---------------------------------------- (14) BOUNDS(1, n^1)