/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), 3 ms] (8) CpxTypedWeightedCompleteTrs (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (10) CpxRNTS (11) CompleteCoflocoProof [FINISHED, 505 ms] (12) BOUNDS(1, n^1) (13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (14) CpxTRS (15) SlicingProof [LOWER BOUND(ID), 0 ms] (16) CpxTRS (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (18) typed CpxTrs (19) OrderProof [LOWER BOUND(ID), 0 ms] (20) typed CpxTrs (21) RewriteLemmaProof [LOWER BOUND(ID), 1518 ms] (22) proven lower bound (23) LowerBoundPropagationProof [FINISHED, 0 ms] (24) BOUNDS(n^1, INF) ---------------------------------------- (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__and(true, X) -> mark(X) a__and(false, Y) -> false a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__add(0, X) -> mark(X) a__add(s(X), Y) -> s(add(X, Y)) a__first(0, X) -> nil a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) a__from(X) -> cons(X, from(s(X))) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(add(X1, X2)) -> a__add(mark(X1), X2) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(X) mark(true) -> true mark(false) -> false mark(0) -> 0 mark(s(X)) -> s(X) mark(nil) -> nil mark(cons(X1, X2)) -> cons(X1, X2) a__and(X1, X2) -> and(X1, X2) a__if(X1, X2, X3) -> if(X1, X2, X3) a__add(X1, X2) -> add(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. The duplicating contexts are: a__from([]) The defined contexts are: a__first([], x1) a__first(x0, []) a__add([], x1) a__and([], x1) a__if([], x1, x2) 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__and(true, X) -> mark(X) a__and(false, Y) -> false a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__add(0, X) -> mark(X) a__add(s(X), Y) -> s(add(X, Y)) a__first(0, X) -> nil a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) a__from(X) -> cons(X, from(s(X))) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(add(X1, X2)) -> a__add(mark(X1), X2) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(X) mark(true) -> true mark(false) -> false mark(0) -> 0 mark(s(X)) -> s(X) mark(nil) -> nil mark(cons(X1, X2)) -> cons(X1, X2) a__and(X1, X2) -> and(X1, X2) a__if(X1, X2, X3) -> if(X1, X2, X3) a__add(X1, X2) -> add(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) 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__and(true, X) -> mark(X) [1] a__and(false, Y) -> false [1] a__if(true, X, Y) -> mark(X) [1] a__if(false, X, Y) -> mark(Y) [1] a__add(0, X) -> mark(X) [1] a__add(s(X), Y) -> s(add(X, Y)) [1] a__first(0, X) -> nil [1] a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) [1] a__from(X) -> cons(X, from(s(X))) [1] mark(and(X1, X2)) -> a__and(mark(X1), X2) [1] mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) [1] mark(add(X1, X2)) -> a__add(mark(X1), X2) [1] mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) [1] mark(from(X)) -> a__from(X) [1] mark(true) -> true [1] mark(false) -> false [1] mark(0) -> 0 [1] mark(s(X)) -> s(X) [1] mark(nil) -> nil [1] mark(cons(X1, X2)) -> cons(X1, X2) [1] a__and(X1, X2) -> and(X1, X2) [1] a__if(X1, X2, X3) -> if(X1, X2, X3) [1] a__add(X1, X2) -> add(X1, X2) [1] a__first(X1, X2) -> first(X1, X2) [1] a__from(X) -> from(X) [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__and(true, X) -> mark(X) [1] a__and(false, Y) -> false [1] a__if(true, X, Y) -> mark(X) [1] a__if(false, X, Y) -> mark(Y) [1] a__add(0, X) -> mark(X) [1] a__add(s(X), Y) -> s(add(X, Y)) [1] a__first(0, X) -> nil [1] a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) [1] a__from(X) -> cons(X, from(s(X))) [1] mark(and(X1, X2)) -> a__and(mark(X1), X2) [1] mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) [1] mark(add(X1, X2)) -> a__add(mark(X1), X2) [1] mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) [1] mark(from(X)) -> a__from(X) [1] mark(true) -> true [1] mark(false) -> false [1] mark(0) -> 0 [1] mark(s(X)) -> s(X) [1] mark(nil) -> nil [1] mark(cons(X1, X2)) -> cons(X1, X2) [1] a__and(X1, X2) -> and(X1, X2) [1] a__if(X1, X2, X3) -> if(X1, X2, X3) [1] a__add(X1, X2) -> add(X1, X2) [1] a__first(X1, X2) -> first(X1, X2) [1] a__from(X) -> from(X) [1] The TRS has the following type information: a__and :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if true :: true:false:0:s:add:nil:cons:first:from:and:if mark :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if false :: true:false:0:s:add:nil:cons:first:from:and:if a__if :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if a__add :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 0 :: true:false:0:s:add:nil:cons:first:from:and:if s :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if add :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if a__first :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if nil :: true:false:0:s:add:nil:cons:first:from:and:if cons :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if first :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if a__from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if and :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if if :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 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__and(true, X) -> mark(X) [1] a__and(false, Y) -> false [1] a__if(true, X, Y) -> mark(X) [1] a__if(false, X, Y) -> mark(Y) [1] a__add(0, X) -> mark(X) [1] a__add(s(X), Y) -> s(add(X, Y)) [1] a__first(0, X) -> nil [1] a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) [1] a__from(X) -> cons(X, from(s(X))) [1] mark(and(X1, X2)) -> a__and(mark(X1), X2) [1] mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) [1] mark(add(X1, X2)) -> a__add(mark(X1), X2) [1] mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) [1] mark(from(X)) -> a__from(X) [1] mark(true) -> true [1] mark(false) -> false [1] mark(0) -> 0 [1] mark(s(X)) -> s(X) [1] mark(nil) -> nil [1] mark(cons(X1, X2)) -> cons(X1, X2) [1] a__and(X1, X2) -> and(X1, X2) [1] a__if(X1, X2, X3) -> if(X1, X2, X3) [1] a__add(X1, X2) -> add(X1, X2) [1] a__first(X1, X2) -> first(X1, X2) [1] a__from(X) -> from(X) [1] The TRS has the following type information: a__and :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if true :: true:false:0:s:add:nil:cons:first:from:and:if mark :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if false :: true:false:0:s:add:nil:cons:first:from:and:if a__if :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if a__add :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 0 :: true:false:0:s:add:nil:cons:first:from:and:if s :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if add :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if a__first :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if nil :: true:false:0:s:add:nil:cons:first:from:and:if cons :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if first :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if a__from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if and :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if if :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 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: true => 3 false => 1 0 => 0 nil => 2 ---------------------------------------- (10) Obligation: Complexity RNTS consisting of the following rules: a__add(z, z') -{ 1 }-> mark(X) :|: z' = X, X >= 0, z = 0 a__add(z, z') -{ 1 }-> 1 + (1 + X + Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0 a__add(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 a__and(z, z') -{ 1 }-> mark(X) :|: z' = X, z = 3, X >= 0 a__and(z, z') -{ 1 }-> 1 :|: z' = Y, Y >= 0, z = 1 a__and(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 a__first(z, z') -{ 1 }-> 2 :|: z' = X, X >= 0, z = 0 a__first(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 a__first(z, z') -{ 1 }-> 1 + Y + (1 + X + Z) :|: Z >= 0, z = 1 + X, Y >= 0, X >= 0, z' = 1 + Y + Z a__from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X a__from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X a__if(z, z', z'') -{ 1 }-> mark(X) :|: z' = X, z = 3, Y >= 0, z'' = Y, X >= 0 a__if(z, z', z'') -{ 1 }-> mark(Y) :|: z' = X, Y >= 0, z = 1, z'' = Y, X >= 0 a__if(z, z', z'') -{ 1 }-> 1 + X1 + X2 + X3 :|: X1 >= 0, X3 >= 0, X2 >= 0, z = X1, z' = X2, z'' = X3 mark(z) -{ 1 }-> a__if(mark(X1), X2, X3) :|: X1 >= 0, X3 >= 0, z = 1 + X1 + X2 + X3, X2 >= 0 mark(z) -{ 1 }-> a__from(X) :|: z = 1 + X, X >= 0 mark(z) -{ 1 }-> a__first(mark(X1), mark(X2)) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 mark(z) -{ 1 }-> a__and(mark(X1), X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 mark(z) -{ 1 }-> a__add(mark(X1), X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 mark(z) -{ 1 }-> 3 :|: z = 3 mark(z) -{ 1 }-> 2 :|: z = 2 mark(z) -{ 1 }-> 1 :|: z = 1 mark(z) -{ 1 }-> 0 :|: z = 0 mark(z) -{ 1 }-> 1 + X :|: z = 1 + X, X >= 0 mark(z) -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 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, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V2),0,[fun1(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). eq(start(V1, V, V2),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V2),0,[fun3(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V2),0,[fun4(V1, Out)],[V1 >= 0]). eq(start(V1, V, V2),0,[mark(V1, Out)],[V1 >= 0]). eq(fun(V1, V, Out),1,[mark(X4, Ret)],[Out = Ret,V = X4,V1 = 3,X4 >= 0]). eq(fun(V1, V, Out),1,[],[Out = 1,V = Y1,Y1 >= 0,V1 = 1]). eq(fun1(V1, V, V2, Out),1,[mark(X5, Ret1)],[Out = Ret1,V = X5,V1 = 3,Y2 >= 0,V2 = Y2,X5 >= 0]). eq(fun1(V1, V, V2, Out),1,[mark(Y3, Ret2)],[Out = Ret2,V = X6,Y3 >= 0,V1 = 1,V2 = Y3,X6 >= 0]). eq(fun2(V1, V, Out),1,[mark(X7, Ret3)],[Out = Ret3,V = X7,X7 >= 0,V1 = 0]). eq(fun2(V1, V, Out),1,[],[Out = 2 + X8 + Y4,V1 = 1 + X8,V = Y4,Y4 >= 0,X8 >= 0]). eq(fun3(V1, V, Out),1,[],[Out = 2,V = X9,X9 >= 0,V1 = 0]). eq(fun3(V1, V, Out),1,[],[Out = 2 + X10 + Y5 + Z1,Z1 >= 0,V1 = 1 + X10,Y5 >= 0,X10 >= 0,V = 1 + Y5 + Z1]). eq(fun4(V1, Out),1,[],[Out = 3 + 2*X11,X11 >= 0,V1 = X11]). eq(mark(V1, Out),1,[mark(X12, Ret0),fun(Ret0, X21, Ret4)],[Out = Ret4,X12 >= 0,X21 >= 0,V1 = 1 + X12 + X21]). eq(mark(V1, Out),1,[mark(X13, Ret01),fun1(Ret01, X22, X31, Ret5)],[Out = Ret5,X13 >= 0,X31 >= 0,V1 = 1 + X13 + X22 + X31,X22 >= 0]). eq(mark(V1, Out),1,[mark(X14, Ret02),fun2(Ret02, X23, Ret6)],[Out = Ret6,X14 >= 0,X23 >= 0,V1 = 1 + X14 + X23]). eq(mark(V1, Out),1,[mark(X15, Ret03),mark(X24, Ret11),fun3(Ret03, Ret11, Ret7)],[Out = Ret7,X15 >= 0,X24 >= 0,V1 = 1 + X15 + X24]). eq(mark(V1, Out),1,[fun4(X16, Ret8)],[Out = Ret8,V1 = 1 + X16,X16 >= 0]). eq(mark(V1, Out),1,[],[Out = 3,V1 = 3]). eq(mark(V1, Out),1,[],[Out = 1,V1 = 1]). eq(mark(V1, Out),1,[],[Out = 0,V1 = 0]). eq(mark(V1, Out),1,[],[Out = 1 + X17,V1 = 1 + X17,X17 >= 0]). eq(mark(V1, Out),1,[],[Out = 2,V1 = 2]). eq(mark(V1, Out),1,[],[Out = 1 + X18 + X25,X18 >= 0,X25 >= 0,V1 = 1 + X18 + X25]). eq(fun(V1, V, Out),1,[],[Out = 1 + X19 + X26,X19 >= 0,X26 >= 0,V1 = X19,V = X26]). eq(fun1(V1, V, V2, Out),1,[],[Out = 1 + X110 + X27 + X32,X110 >= 0,X32 >= 0,X27 >= 0,V1 = X110,V = X27,V2 = X32]). eq(fun2(V1, V, Out),1,[],[Out = 1 + X111 + X28,X111 >= 0,X28 >= 0,V1 = X111,V = X28]). eq(fun3(V1, V, Out),1,[],[Out = 1 + X112 + X29,X112 >= 0,X29 >= 0,V1 = X112,V = X29]). eq(fun4(V1, Out),1,[],[Out = 1 + X20,X20 >= 0,V1 = X20]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(V1,V,V2,Out),[V1,V,V2],[Out]). input_output_vars(fun2(V1,V,Out),[V1,V],[Out]). input_output_vars(fun3(V1,V,Out),[V1,V],[Out]). input_output_vars(fun4(V1,Out),[V1],[Out]). input_output_vars(mark(V1,Out),[V1],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [fun3/3] 1. non_recursive : [fun4/2] 2. recursive [non_tail,multiple] : [fun/3,fun1/4,fun2/3,mark/2] 3. non_recursive : [start/3] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into fun3/3 1. SCC is partially evaluated into fun4/2 2. SCC is partially evaluated into mark/2 3. SCC is partially evaluated into start/3 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations fun3/3 * CE 19 is refined into CE [23] * CE 20 is refined into CE [24] * CE 18 is refined into CE [25] ### Cost equations --> "Loop" of fun3/3 * CEs [23] --> Loop 16 * CEs [24] --> Loop 17 * CEs [25] --> Loop 18 ### Ranking functions of CR fun3(V1,V,Out) #### Partial ranking functions of CR fun3(V1,V,Out) ### Specialization of cost equations fun4/2 * CE 21 is refined into CE [26] * CE 22 is refined into CE [27] ### Cost equations --> "Loop" of fun4/2 * CEs [26] --> Loop 19 * CEs [27] --> Loop 20 ### Ranking functions of CR fun4(V1,Out) #### Partial ranking functions of CR fun4(V1,Out) ### Specialization of cost equations mark/2 * CE 14 is refined into CE [28,29] * CE 15 is refined into CE [30] * CE 16 is refined into CE [31] * CE 17 is refined into CE [32] * CE 11 is refined into CE [33] * CE 10 is refined into CE [34] * CE 9 is refined into CE [35] * CE 13 is refined into CE [36,37,38] * CE 8 is refined into CE [39] * CE 12 is refined into CE [40] ### Cost equations --> "Loop" of mark/2 * CEs [39] --> Loop 21 * CEs [40] --> Loop 22 * CEs [38] --> Loop 23 * CEs [37] --> Loop 24 * CEs [33] --> Loop 25 * CEs [34] --> Loop 26 * CEs [35] --> Loop 27 * CEs [36] --> Loop 28 * CEs [29] --> Loop 29 * CEs [28,30,31] --> Loop 30 * CEs [32] --> Loop 31 ### Ranking functions of CR mark(V1,Out) * RF of phase [21,22,23,24,25,26,27,28]: [V1] #### Partial ranking functions of CR mark(V1,Out) * Partial RF of phase [21,22,23,24,25,26,27,28]: - RF of loop [21:1,22:1,23:1,23:2,24:1,24:2,25:1,25:2,26:1,26:2,27:1,27:2,28:1,28:2]: V1 ### Specialization of cost equations start/3 * CE 4 is refined into CE [41,42,43] * CE 3 is refined into CE [44,45,46] * CE 1 is refined into CE [47] * CE 2 is refined into CE [48,49,50] * CE 5 is refined into CE [51,52,53] * CE 6 is refined into CE [54,55] * CE 7 is refined into CE [56,57,58] ### Cost equations --> "Loop" of start/3 * CEs [42,43] --> Loop 32 * CEs [41] --> Loop 33 * CEs [45,46] --> Loop 34 * CEs [44] --> Loop 35 * CEs [47,48,49,50,51,52,53,54,55,56,57,58] --> Loop 36 ### Ranking functions of CR start(V1,V,V2) #### Partial ranking functions of CR start(V1,V,V2) Computing Bounds ===================================== #### Cost of chains of fun3(V1,V,Out): * Chain [18]: 1 with precondition: [V1=0,Out=2,V>=0] * Chain [17]: 1 with precondition: [V+V1+1=Out,V1>=0,V>=0] * Chain [16]: 1 with precondition: [V+V1=Out,V1>=1,V>=1] #### Cost of chains of fun4(V1,Out): * Chain [20]: 1 with precondition: [V1+1=Out,V1>=0] * Chain [19]: 1 with precondition: [2*V1+3=Out,V1>=0] #### Cost of chains of mark(V1,Out): * Chain [31]: 1 with precondition: [V1=0,Out=0] * Chain [30]: 2 with precondition: [V1=Out,V1>=1] * Chain [29]: 2 with precondition: [2*V1+1=Out,V1>=1] * Chain [multiple([21,22,23,24,25,26,27,28],[[31],[30],[29]])]: 4*it(21)+2*it(23)+6*it(24)+2*it(25)+2*it(26)+4*it([29])+1*it([31])+0 Such that:aux(10) =< 1 aux(11) =< V1 aux(12) =< 2/3*V1 aux(13) =< 4/3*V1+1/3 aux(14) =< 6/7*V1 it(21) =< aux(11) it(23) =< aux(11) it(24) =< aux(11) it(25) =< aux(11) it(26) =< aux(11) it([29]) =< aux(11) it(25) =< aux(12) it(24) =< aux(13) it(25) =< aux(13) it(26) =< aux(13) it([29]) =< aux(13) it(23) =< aux(14) it(25) =< aux(14) it(26) =< aux(14) it([29]) =< it(24)+it(24)+it(26)+it(25)+it(24)+it(23)+aux(10) it([31]) =< it(24)+it(24)+it(26)+it(25)+it(24)+it(23)+aux(10) with precondition: [V1>=1,Out>=0,5*V1>=2*Out+1,2*V1+1>=Out] #### Cost of chains of start(V1,V,V2): * Chain [36]: 4*s(18)+2*s(19)+6*s(20)+2*s(21)+2*s(22)+4*s(23)+1*s(24)+4*s(30)+2*s(31)+6*s(32)+2*s(33)+2*s(34)+4*s(35)+1*s(36)+3 Such that:s(26) =< V1 s(27) =< 2/3*V1 s(28) =< 4/3*V1+1/3 s(29) =< 6/7*V1 s(14) =< V s(15) =< 2/3*V s(16) =< 4/3*V+1/3 s(17) =< 6/7*V aux(15) =< 1 s(18) =< s(14) s(19) =< s(14) s(20) =< s(14) s(21) =< s(14) s(22) =< s(14) s(23) =< s(14) s(21) =< s(15) s(20) =< s(16) s(21) =< s(16) s(22) =< s(16) s(23) =< s(16) s(19) =< s(17) s(21) =< s(17) s(22) =< s(17) s(23) =< s(20)+s(20)+s(22)+s(21)+s(20)+s(19)+aux(15) s(24) =< s(20)+s(20)+s(22)+s(21)+s(20)+s(19)+aux(15) s(30) =< s(26) s(31) =< s(26) s(32) =< s(26) s(33) =< s(26) s(34) =< s(26) s(35) =< s(26) s(33) =< s(27) s(32) =< s(28) s(33) =< s(28) s(34) =< s(28) s(35) =< s(28) s(31) =< s(29) s(33) =< s(29) s(34) =< s(29) s(35) =< s(32)+s(32)+s(34)+s(33)+s(32)+s(31)+aux(15) s(36) =< s(32)+s(32)+s(34)+s(33)+s(32)+s(31)+aux(15) with precondition: [V1>=0] * Chain [35]: 2 with precondition: [V1=1,V2=0,V>=0] * Chain [34]: 4*s(42)+2*s(43)+6*s(44)+2*s(45)+2*s(46)+4*s(47)+1*s(48)+3 Such that:s(37) =< 1 s(38) =< V2 s(39) =< 2/3*V2 s(40) =< 4/3*V2+1/3 s(41) =< 6/7*V2 s(42) =< s(38) s(43) =< s(38) s(44) =< s(38) s(45) =< s(38) s(46) =< s(38) s(47) =< s(38) s(45) =< s(39) s(44) =< s(40) s(45) =< s(40) s(46) =< s(40) s(47) =< s(40) s(43) =< s(41) s(45) =< s(41) s(46) =< s(41) s(47) =< s(44)+s(44)+s(46)+s(45)+s(44)+s(43)+s(37) s(48) =< s(44)+s(44)+s(46)+s(45)+s(44)+s(43)+s(37) with precondition: [V1=1,V>=0,V2>=1] * Chain [33]: 2 with precondition: [V1=3,V=0] * Chain [32]: 4*s(54)+2*s(55)+6*s(56)+2*s(57)+2*s(58)+4*s(59)+1*s(60)+3 Such that:s(49) =< 1 s(50) =< V s(51) =< 2/3*V s(52) =< 4/3*V+1/3 s(53) =< 6/7*V s(54) =< s(50) s(55) =< s(50) s(56) =< s(50) s(57) =< s(50) s(58) =< s(50) s(59) =< s(50) s(57) =< s(51) s(56) =< s(52) s(57) =< s(52) s(58) =< s(52) s(59) =< s(52) s(55) =< s(53) s(57) =< s(53) s(58) =< s(53) s(59) =< s(56)+s(56)+s(58)+s(57)+s(56)+s(55)+s(49) s(60) =< s(56)+s(56)+s(58)+s(57)+s(56)+s(55)+s(49) with precondition: [V1=3,V>=1] Closed-form bounds of start(V1,V,V2): ------------------------------------- * Chain [36] with precondition: [V1>=0] - Upper bound: 26*V1+5+nat(V)*26 - Complexity: n * Chain [35] with precondition: [V1=1,V2=0,V>=0] - Upper bound: 2 - Complexity: constant * Chain [34] with precondition: [V1=1,V>=0,V2>=1] - Upper bound: 26*V2+4 - Complexity: n * Chain [33] with precondition: [V1=3,V=0] - Upper bound: 2 - Complexity: constant * Chain [32] with precondition: [V1=3,V>=1] - Upper bound: 26*V+4 - Complexity: n ### Maximum cost of start(V1,V,V2): max([nat(V2)*26+2,nat(V)*26+2+(26*V1+1)])+2 Asymptotic class: n * Total analysis performed in 382 ms. ---------------------------------------- (12) BOUNDS(1, n^1) ---------------------------------------- (13) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (14) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: a__and(true, X) -> mark(X) a__and(false, Y) -> false a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__add(0', X) -> mark(X) a__add(s(X), Y) -> s(add(X, Y)) a__first(0', X) -> nil a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) a__from(X) -> cons(X, from(s(X))) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(add(X1, X2)) -> a__add(mark(X1), X2) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(X) mark(true) -> true mark(false) -> false mark(0') -> 0' mark(s(X)) -> s(X) mark(nil) -> nil mark(cons(X1, X2)) -> cons(X1, X2) a__and(X1, X2) -> and(X1, X2) a__if(X1, X2, X3) -> if(X1, X2, X3) a__add(X1, X2) -> add(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) S is empty. Rewrite Strategy: FULL ---------------------------------------- (15) SlicingProof (LOWER BOUND(ID)) Sliced the following arguments: s/0 cons/0 cons/1 a__from/0 from/0 ---------------------------------------- (16) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: a__and(true, X) -> mark(X) a__and(false, Y) -> false a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__add(0', X) -> mark(X) a__add(s, Y) -> s a__first(0', X) -> nil a__first(s, cons) -> cons a__from -> cons mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(add(X1, X2)) -> a__add(mark(X1), X2) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from) -> a__from mark(true) -> true mark(false) -> false mark(0') -> 0' mark(s) -> s mark(nil) -> nil mark(cons) -> cons a__and(X1, X2) -> and(X1, X2) a__if(X1, X2, X3) -> if(X1, X2, X3) a__add(X1, X2) -> add(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from -> from S is empty. Rewrite Strategy: FULL ---------------------------------------- (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (18) Obligation: TRS: Rules: a__and(true, X) -> mark(X) a__and(false, Y) -> false a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__add(0', X) -> mark(X) a__add(s, Y) -> s a__first(0', X) -> nil a__first(s, cons) -> cons a__from -> cons mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(add(X1, X2)) -> a__add(mark(X1), X2) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from) -> a__from mark(true) -> true mark(false) -> false mark(0') -> 0' mark(s) -> s mark(nil) -> nil mark(cons) -> cons a__and(X1, X2) -> and(X1, X2) a__if(X1, X2, X3) -> if(X1, X2, X3) a__add(X1, X2) -> add(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from -> from Types: a__and :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from true :: true:false:0':s:nil:cons:and:if:add:first:from mark :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from false :: true:false:0':s:nil:cons:and:if:add:first:from a__if :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from a__add :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from 0' :: true:false:0':s:nil:cons:and:if:add:first:from s :: true:false:0':s:nil:cons:and:if:add:first:from a__first :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from nil :: true:false:0':s:nil:cons:and:if:add:first:from cons :: true:false:0':s:nil:cons:and:if:add:first:from a__from :: true:false:0':s:nil:cons:and:if:add:first:from and :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from if :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from add :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from first :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from from :: true:false:0':s:nil:cons:and:if:add:first:from hole_true:false:0':s:nil:cons:and:if:add:first:from1_0 :: true:false:0':s:nil:cons:and:if:add:first:from gen_true:false:0':s:nil:cons:and:if:add:first:from2_0 :: Nat -> true:false:0':s:nil:cons:and:if:add:first:from ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: mark ---------------------------------------- (20) Obligation: TRS: Rules: a__and(true, X) -> mark(X) a__and(false, Y) -> false a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__add(0', X) -> mark(X) a__add(s, Y) -> s a__first(0', X) -> nil a__first(s, cons) -> cons a__from -> cons mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(add(X1, X2)) -> a__add(mark(X1), X2) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from) -> a__from mark(true) -> true mark(false) -> false mark(0') -> 0' mark(s) -> s mark(nil) -> nil mark(cons) -> cons a__and(X1, X2) -> and(X1, X2) a__if(X1, X2, X3) -> if(X1, X2, X3) a__add(X1, X2) -> add(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from -> from Types: a__and :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from true :: true:false:0':s:nil:cons:and:if:add:first:from mark :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from false :: true:false:0':s:nil:cons:and:if:add:first:from a__if :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from a__add :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from 0' :: true:false:0':s:nil:cons:and:if:add:first:from s :: true:false:0':s:nil:cons:and:if:add:first:from a__first :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from nil :: true:false:0':s:nil:cons:and:if:add:first:from cons :: true:false:0':s:nil:cons:and:if:add:first:from a__from :: true:false:0':s:nil:cons:and:if:add:first:from and :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from if :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from add :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from first :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from from :: true:false:0':s:nil:cons:and:if:add:first:from hole_true:false:0':s:nil:cons:and:if:add:first:from1_0 :: true:false:0':s:nil:cons:and:if:add:first:from gen_true:false:0':s:nil:cons:and:if:add:first:from2_0 :: Nat -> true:false:0':s:nil:cons:and:if:add:first:from Generator Equations: gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(0) <=> true gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(+(x, 1)) <=> and(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(x), true) The following defined symbols remain to be analysed: mark ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mark(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(n4_0)) -> gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(0), rt in Omega(1 + n4_0) Induction Base: mark(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(0)) ->_R^Omega(1) true Induction Step: mark(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(+(n4_0, 1))) ->_R^Omega(1) a__and(mark(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(n4_0)), true) ->_IH a__and(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(0), true) ->_R^Omega(1) mark(true) ->_R^Omega(1) true We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (22) Obligation: Proved the lower bound n^1 for the following obligation: TRS: Rules: a__and(true, X) -> mark(X) a__and(false, Y) -> false a__if(true, X, Y) -> mark(X) a__if(false, X, Y) -> mark(Y) a__add(0', X) -> mark(X) a__add(s, Y) -> s a__first(0', X) -> nil a__first(s, cons) -> cons a__from -> cons mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) mark(add(X1, X2)) -> a__add(mark(X1), X2) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from) -> a__from mark(true) -> true mark(false) -> false mark(0') -> 0' mark(s) -> s mark(nil) -> nil mark(cons) -> cons a__and(X1, X2) -> and(X1, X2) a__if(X1, X2, X3) -> if(X1, X2, X3) a__add(X1, X2) -> add(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from -> from Types: a__and :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from true :: true:false:0':s:nil:cons:and:if:add:first:from mark :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from false :: true:false:0':s:nil:cons:and:if:add:first:from a__if :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from a__add :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from 0' :: true:false:0':s:nil:cons:and:if:add:first:from s :: true:false:0':s:nil:cons:and:if:add:first:from a__first :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from nil :: true:false:0':s:nil:cons:and:if:add:first:from cons :: true:false:0':s:nil:cons:and:if:add:first:from a__from :: true:false:0':s:nil:cons:and:if:add:first:from and :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from if :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from add :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from first :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from from :: true:false:0':s:nil:cons:and:if:add:first:from hole_true:false:0':s:nil:cons:and:if:add:first:from1_0 :: true:false:0':s:nil:cons:and:if:add:first:from gen_true:false:0':s:nil:cons:and:if:add:first:from2_0 :: Nat -> true:false:0':s:nil:cons:and:if:add:first:from Generator Equations: gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(0) <=> true gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(+(x, 1)) <=> and(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(x), true) The following defined symbols remain to be analysed: mark ---------------------------------------- (23) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (24) BOUNDS(n^1, INF)