18.04/5.54 WORST_CASE(Omega(n^1), O(n^1)) 18.04/5.55 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 18.04/5.55 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 18.04/5.55 18.04/5.55 18.04/5.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 18.04/5.55 18.04/5.55 (0) CpxTRS 18.04/5.55 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/5.55 (2) CpxWeightedTrs 18.04/5.55 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/5.55 (4) CpxTypedWeightedTrs 18.04/5.55 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 18.04/5.55 (6) CpxTypedWeightedCompleteTrs 18.04/5.55 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 2 ms] 18.04/5.55 (8) CpxRNTS 18.04/5.55 (9) CompleteCoflocoProof [FINISHED, 508 ms] 18.04/5.55 (10) BOUNDS(1, n^1) 18.04/5.55 (11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/5.55 (12) CpxTRS 18.04/5.55 (13) SlicingProof [LOWER BOUND(ID), 0 ms] 18.04/5.55 (14) CpxTRS 18.04/5.55 (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/5.55 (16) typed CpxTrs 18.04/5.55 (17) OrderProof [LOWER BOUND(ID), 0 ms] 18.04/5.55 (18) typed CpxTrs 18.04/5.55 (19) RewriteLemmaProof [LOWER BOUND(ID), 1824 ms] 18.04/5.55 (20) proven lower bound 18.04/5.55 (21) LowerBoundPropagationProof [FINISHED, 0 ms] 18.04/5.55 (22) BOUNDS(n^1, INF) 18.04/5.55 18.04/5.55 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (0) 18.04/5.55 Obligation: 18.04/5.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 18.04/5.55 18.04/5.55 18.04/5.55 The TRS R consists of the following rules: 18.04/5.55 18.04/5.55 a__and(true, X) -> mark(X) 18.04/5.55 a__and(false, Y) -> false 18.04/5.55 a__if(true, X, Y) -> mark(X) 18.04/5.55 a__if(false, X, Y) -> mark(Y) 18.04/5.55 a__add(0, X) -> mark(X) 18.04/5.55 a__add(s(X), Y) -> s(add(X, Y)) 18.04/5.55 a__first(0, X) -> nil 18.04/5.55 a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) 18.04/5.55 a__from(X) -> cons(X, from(s(X))) 18.04/5.55 mark(and(X1, X2)) -> a__and(mark(X1), X2) 18.04/5.55 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 18.04/5.55 mark(add(X1, X2)) -> a__add(mark(X1), X2) 18.04/5.55 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 18.04/5.55 mark(from(X)) -> a__from(X) 18.04/5.55 mark(true) -> true 18.04/5.55 mark(false) -> false 18.04/5.55 mark(0) -> 0 18.04/5.55 mark(s(X)) -> s(X) 18.04/5.55 mark(nil) -> nil 18.04/5.55 mark(cons(X1, X2)) -> cons(X1, X2) 18.04/5.55 a__and(X1, X2) -> and(X1, X2) 18.04/5.55 a__if(X1, X2, X3) -> if(X1, X2, X3) 18.04/5.55 a__add(X1, X2) -> add(X1, X2) 18.04/5.55 a__first(X1, X2) -> first(X1, X2) 18.04/5.55 a__from(X) -> from(X) 18.04/5.55 18.04/5.55 S is empty. 18.04/5.55 Rewrite Strategy: INNERMOST 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 18.04/5.55 Transformed relative TRS to weighted TRS 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (2) 18.04/5.55 Obligation: 18.04/5.55 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 18.04/5.55 18.04/5.55 18.04/5.55 The TRS R consists of the following rules: 18.04/5.55 18.04/5.55 a__and(true, X) -> mark(X) [1] 18.04/5.55 a__and(false, Y) -> false [1] 18.04/5.55 a__if(true, X, Y) -> mark(X) [1] 18.04/5.55 a__if(false, X, Y) -> mark(Y) [1] 18.04/5.55 a__add(0, X) -> mark(X) [1] 18.04/5.55 a__add(s(X), Y) -> s(add(X, Y)) [1] 18.04/5.55 a__first(0, X) -> nil [1] 18.04/5.55 a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) [1] 18.04/5.55 a__from(X) -> cons(X, from(s(X))) [1] 18.04/5.55 mark(and(X1, X2)) -> a__and(mark(X1), X2) [1] 18.04/5.55 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) [1] 18.04/5.55 mark(add(X1, X2)) -> a__add(mark(X1), X2) [1] 18.04/5.55 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) [1] 18.04/5.55 mark(from(X)) -> a__from(X) [1] 18.04/5.55 mark(true) -> true [1] 18.04/5.55 mark(false) -> false [1] 18.04/5.55 mark(0) -> 0 [1] 18.04/5.55 mark(s(X)) -> s(X) [1] 18.04/5.55 mark(nil) -> nil [1] 18.04/5.55 mark(cons(X1, X2)) -> cons(X1, X2) [1] 18.04/5.55 a__and(X1, X2) -> and(X1, X2) [1] 18.04/5.55 a__if(X1, X2, X3) -> if(X1, X2, X3) [1] 18.04/5.55 a__add(X1, X2) -> add(X1, X2) [1] 18.04/5.55 a__first(X1, X2) -> first(X1, X2) [1] 18.04/5.55 a__from(X) -> from(X) [1] 18.04/5.55 18.04/5.55 Rewrite Strategy: INNERMOST 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 18.04/5.55 Infered types. 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (4) 18.04/5.55 Obligation: 18.04/5.55 Runtime Complexity Weighted TRS with Types. 18.04/5.55 The TRS R consists of the following rules: 18.04/5.55 18.04/5.55 a__and(true, X) -> mark(X) [1] 18.04/5.55 a__and(false, Y) -> false [1] 18.04/5.55 a__if(true, X, Y) -> mark(X) [1] 18.04/5.55 a__if(false, X, Y) -> mark(Y) [1] 18.04/5.55 a__add(0, X) -> mark(X) [1] 18.04/5.55 a__add(s(X), Y) -> s(add(X, Y)) [1] 18.04/5.55 a__first(0, X) -> nil [1] 18.04/5.55 a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) [1] 18.04/5.55 a__from(X) -> cons(X, from(s(X))) [1] 18.04/5.55 mark(and(X1, X2)) -> a__and(mark(X1), X2) [1] 18.04/5.55 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) [1] 18.04/5.55 mark(add(X1, X2)) -> a__add(mark(X1), X2) [1] 18.04/5.55 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) [1] 18.04/5.55 mark(from(X)) -> a__from(X) [1] 18.04/5.55 mark(true) -> true [1] 18.04/5.55 mark(false) -> false [1] 18.04/5.55 mark(0) -> 0 [1] 18.04/5.55 mark(s(X)) -> s(X) [1] 18.04/5.55 mark(nil) -> nil [1] 18.04/5.55 mark(cons(X1, X2)) -> cons(X1, X2) [1] 18.04/5.55 a__and(X1, X2) -> and(X1, X2) [1] 18.04/5.55 a__if(X1, X2, X3) -> if(X1, X2, X3) [1] 18.04/5.55 a__add(X1, X2) -> add(X1, X2) [1] 18.04/5.55 a__first(X1, X2) -> first(X1, X2) [1] 18.04/5.55 a__from(X) -> from(X) [1] 18.04/5.55 18.04/5.55 The TRS has the following type information: 18.04/5.55 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 18.04/5.55 true :: true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 mark :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 false :: true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 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 18.04/5.55 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 18.04/5.55 0 :: true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 s :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 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 18.04/5.55 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 18.04/5.55 nil :: true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 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 18.04/5.55 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 18.04/5.55 a__from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 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 18.04/5.55 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 18.04/5.55 18.04/5.55 Rewrite Strategy: INNERMOST 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (5) CompletionProof (UPPER BOUND(ID)) 18.04/5.55 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 18.04/5.55 none 18.04/5.55 18.04/5.55 And the following fresh constants: none 18.04/5.55 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (6) 18.04/5.55 Obligation: 18.04/5.55 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 18.04/5.55 18.04/5.55 Runtime Complexity Weighted TRS with Types. 18.04/5.55 The TRS R consists of the following rules: 18.04/5.55 18.04/5.55 a__and(true, X) -> mark(X) [1] 18.04/5.55 a__and(false, Y) -> false [1] 18.04/5.55 a__if(true, X, Y) -> mark(X) [1] 18.04/5.55 a__if(false, X, Y) -> mark(Y) [1] 18.04/5.55 a__add(0, X) -> mark(X) [1] 18.04/5.55 a__add(s(X), Y) -> s(add(X, Y)) [1] 18.04/5.55 a__first(0, X) -> nil [1] 18.04/5.55 a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) [1] 18.04/5.55 a__from(X) -> cons(X, from(s(X))) [1] 18.04/5.55 mark(and(X1, X2)) -> a__and(mark(X1), X2) [1] 18.04/5.55 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) [1] 18.04/5.55 mark(add(X1, X2)) -> a__add(mark(X1), X2) [1] 18.04/5.55 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) [1] 18.04/5.55 mark(from(X)) -> a__from(X) [1] 18.04/5.55 mark(true) -> true [1] 18.04/5.55 mark(false) -> false [1] 18.04/5.55 mark(0) -> 0 [1] 18.04/5.55 mark(s(X)) -> s(X) [1] 18.04/5.55 mark(nil) -> nil [1] 18.04/5.55 mark(cons(X1, X2)) -> cons(X1, X2) [1] 18.04/5.55 a__and(X1, X2) -> and(X1, X2) [1] 18.04/5.55 a__if(X1, X2, X3) -> if(X1, X2, X3) [1] 18.04/5.55 a__add(X1, X2) -> add(X1, X2) [1] 18.04/5.55 a__first(X1, X2) -> first(X1, X2) [1] 18.04/5.55 a__from(X) -> from(X) [1] 18.04/5.55 18.04/5.55 The TRS has the following type information: 18.04/5.55 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 18.04/5.55 true :: true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 mark :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 false :: true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 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 18.04/5.55 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 18.04/5.55 0 :: true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 s :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 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 18.04/5.55 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 18.04/5.55 nil :: true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 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 18.04/5.55 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 18.04/5.55 a__from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 from :: true:false:0:s:add:nil:cons:first:from:and:if -> true:false:0:s:add:nil:cons:first:from:and:if 18.04/5.55 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 18.04/5.55 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 18.04/5.55 18.04/5.55 Rewrite Strategy: INNERMOST 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 18.04/5.55 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 18.04/5.55 The constant constructors are abstracted as follows: 18.04/5.55 18.04/5.55 true => 3 18.04/5.55 false => 1 18.04/5.55 0 => 0 18.04/5.55 nil => 2 18.04/5.55 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (8) 18.04/5.55 Obligation: 18.04/5.55 Complexity RNTS consisting of the following rules: 18.04/5.55 18.04/5.55 a__add(z, z') -{ 1 }-> mark(X) :|: z' = X, X >= 0, z = 0 18.04/5.55 a__add(z, z') -{ 1 }-> 1 + (1 + X + Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0 18.04/5.55 a__add(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 18.04/5.55 a__and(z, z') -{ 1 }-> mark(X) :|: z' = X, z = 3, X >= 0 18.04/5.55 a__and(z, z') -{ 1 }-> 1 :|: z' = Y, Y >= 0, z = 1 18.04/5.55 a__and(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 18.04/5.55 a__first(z, z') -{ 1 }-> 2 :|: z' = X, X >= 0, z = 0 18.04/5.55 a__first(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 18.04/5.55 a__first(z, z') -{ 1 }-> 1 + Y + (1 + X + Z) :|: Z >= 0, z = 1 + X, Y >= 0, X >= 0, z' = 1 + Y + Z 18.04/5.55 a__from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 18.04/5.55 a__from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X 18.04/5.55 a__if(z, z', z'') -{ 1 }-> mark(X) :|: z' = X, z = 3, Y >= 0, z'' = Y, X >= 0 18.04/5.55 a__if(z, z', z'') -{ 1 }-> mark(Y) :|: z' = X, Y >= 0, z = 1, z'' = Y, X >= 0 18.04/5.55 a__if(z, z', z'') -{ 1 }-> 1 + X1 + X2 + X3 :|: X1 >= 0, X3 >= 0, X2 >= 0, z = X1, z' = X2, z'' = X3 18.04/5.55 mark(z) -{ 1 }-> a__if(mark(X1), X2, X3) :|: X1 >= 0, X3 >= 0, z = 1 + X1 + X2 + X3, X2 >= 0 18.04/5.55 mark(z) -{ 1 }-> a__from(X) :|: z = 1 + X, X >= 0 18.04/5.55 mark(z) -{ 1 }-> a__first(mark(X1), mark(X2)) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 18.04/5.55 mark(z) -{ 1 }-> a__and(mark(X1), X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 18.04/5.55 mark(z) -{ 1 }-> a__add(mark(X1), X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 18.04/5.55 mark(z) -{ 1 }-> 3 :|: z = 3 18.04/5.55 mark(z) -{ 1 }-> 2 :|: z = 2 18.04/5.55 mark(z) -{ 1 }-> 1 :|: z = 1 18.04/5.55 mark(z) -{ 1 }-> 0 :|: z = 0 18.04/5.55 mark(z) -{ 1 }-> 1 + X :|: z = 1 + X, X >= 0 18.04/5.55 mark(z) -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 18.04/5.55 18.04/5.55 Only complete derivations are relevant for the runtime complexity. 18.04/5.55 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (9) CompleteCoflocoProof (FINISHED) 18.04/5.55 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 18.04/5.55 18.04/5.55 eq(start(V1, V, V2),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). 18.04/5.55 eq(start(V1, V, V2),0,[fun1(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). 18.04/5.55 eq(start(V1, V, V2),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). 18.04/5.55 eq(start(V1, V, V2),0,[fun3(V1, V, Out)],[V1 >= 0,V >= 0]). 18.04/5.55 eq(start(V1, V, V2),0,[fun4(V1, Out)],[V1 >= 0]). 18.04/5.55 eq(start(V1, V, V2),0,[mark(V1, Out)],[V1 >= 0]). 18.04/5.55 eq(fun(V1, V, Out),1,[mark(X4, Ret)],[Out = Ret,V = X4,V1 = 3,X4 >= 0]). 18.04/5.55 eq(fun(V1, V, Out),1,[],[Out = 1,V = Y1,Y1 >= 0,V1 = 1]). 18.04/5.55 eq(fun1(V1, V, V2, Out),1,[mark(X5, Ret1)],[Out = Ret1,V = X5,V1 = 3,Y2 >= 0,V2 = Y2,X5 >= 0]). 18.04/5.55 eq(fun1(V1, V, V2, Out),1,[mark(Y3, Ret2)],[Out = Ret2,V = X6,Y3 >= 0,V1 = 1,V2 = Y3,X6 >= 0]). 18.04/5.55 eq(fun2(V1, V, Out),1,[mark(X7, Ret3)],[Out = Ret3,V = X7,X7 >= 0,V1 = 0]). 18.04/5.55 eq(fun2(V1, V, Out),1,[],[Out = 2 + X8 + Y4,V1 = 1 + X8,V = Y4,Y4 >= 0,X8 >= 0]). 18.04/5.55 eq(fun3(V1, V, Out),1,[],[Out = 2,V = X9,X9 >= 0,V1 = 0]). 18.04/5.55 eq(fun3(V1, V, Out),1,[],[Out = 2 + X10 + Y5 + Z1,Z1 >= 0,V1 = 1 + X10,Y5 >= 0,X10 >= 0,V = 1 + Y5 + Z1]). 18.04/5.55 eq(fun4(V1, Out),1,[],[Out = 3 + 2*X11,X11 >= 0,V1 = X11]). 18.04/5.55 eq(mark(V1, Out),1,[mark(X12, Ret0),fun(Ret0, X21, Ret4)],[Out = Ret4,X12 >= 0,X21 >= 0,V1 = 1 + X12 + X21]). 18.04/5.55 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]). 18.04/5.55 eq(mark(V1, Out),1,[mark(X14, Ret02),fun2(Ret02, X23, Ret6)],[Out = Ret6,X14 >= 0,X23 >= 0,V1 = 1 + X14 + X23]). 18.04/5.55 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]). 18.04/5.55 eq(mark(V1, Out),1,[fun4(X16, Ret8)],[Out = Ret8,V1 = 1 + X16,X16 >= 0]). 18.04/5.55 eq(mark(V1, Out),1,[],[Out = 3,V1 = 3]). 18.04/5.55 eq(mark(V1, Out),1,[],[Out = 1,V1 = 1]). 18.04/5.55 eq(mark(V1, Out),1,[],[Out = 0,V1 = 0]). 18.04/5.55 eq(mark(V1, Out),1,[],[Out = 1 + X17,V1 = 1 + X17,X17 >= 0]). 18.04/5.55 eq(mark(V1, Out),1,[],[Out = 2,V1 = 2]). 18.04/5.55 eq(mark(V1, Out),1,[],[Out = 1 + X18 + X25,X18 >= 0,X25 >= 0,V1 = 1 + X18 + X25]). 18.04/5.55 eq(fun(V1, V, Out),1,[],[Out = 1 + X19 + X26,X19 >= 0,X26 >= 0,V1 = X19,V = X26]). 18.04/5.55 eq(fun1(V1, V, V2, Out),1,[],[Out = 1 + X110 + X27 + X32,X110 >= 0,X32 >= 0,X27 >= 0,V1 = X110,V = X27,V2 = X32]). 18.04/5.55 eq(fun2(V1, V, Out),1,[],[Out = 1 + X111 + X28,X111 >= 0,X28 >= 0,V1 = X111,V = X28]). 18.04/5.55 eq(fun3(V1, V, Out),1,[],[Out = 1 + X112 + X29,X112 >= 0,X29 >= 0,V1 = X112,V = X29]). 18.04/5.55 eq(fun4(V1, Out),1,[],[Out = 1 + X20,X20 >= 0,V1 = X20]). 18.04/5.55 input_output_vars(fun(V1,V,Out),[V1,V],[Out]). 18.04/5.55 input_output_vars(fun1(V1,V,V2,Out),[V1,V,V2],[Out]). 18.04/5.55 input_output_vars(fun2(V1,V,Out),[V1,V],[Out]). 18.04/5.55 input_output_vars(fun3(V1,V,Out),[V1,V],[Out]). 18.04/5.55 input_output_vars(fun4(V1,Out),[V1],[Out]). 18.04/5.55 input_output_vars(mark(V1,Out),[V1],[Out]). 18.04/5.55 18.04/5.55 18.04/5.55 CoFloCo proof output: 18.04/5.55 Preprocessing Cost Relations 18.04/5.55 ===================================== 18.04/5.55 18.04/5.55 #### Computed strongly connected components 18.04/5.55 0. non_recursive : [fun3/3] 18.04/5.55 1. non_recursive : [fun4/2] 18.04/5.55 2. recursive [non_tail,multiple] : [fun/3,fun1/4,fun2/3,mark/2] 18.04/5.55 3. non_recursive : [start/3] 18.04/5.55 18.04/5.55 #### Obtained direct recursion through partial evaluation 18.04/5.55 0. SCC is partially evaluated into fun3/3 18.04/5.55 1. SCC is partially evaluated into fun4/2 18.04/5.55 2. SCC is partially evaluated into mark/2 18.04/5.55 3. SCC is partially evaluated into start/3 18.04/5.55 18.04/5.55 Control-Flow Refinement of Cost Relations 18.04/5.55 ===================================== 18.04/5.55 18.04/5.55 ### Specialization of cost equations fun3/3 18.04/5.55 * CE 19 is refined into CE [23] 18.04/5.55 * CE 20 is refined into CE [24] 18.04/5.55 * CE 18 is refined into CE [25] 18.04/5.55 18.04/5.55 18.04/5.55 ### Cost equations --> "Loop" of fun3/3 18.04/5.55 * CEs [23] --> Loop 16 18.04/5.55 * CEs [24] --> Loop 17 18.04/5.55 * CEs [25] --> Loop 18 18.04/5.55 18.04/5.55 ### Ranking functions of CR fun3(V1,V,Out) 18.04/5.55 18.04/5.55 #### Partial ranking functions of CR fun3(V1,V,Out) 18.04/5.55 18.04/5.55 18.04/5.55 ### Specialization of cost equations fun4/2 18.04/5.55 * CE 21 is refined into CE [26] 18.04/5.55 * CE 22 is refined into CE [27] 18.04/5.55 18.04/5.55 18.04/5.55 ### Cost equations --> "Loop" of fun4/2 18.04/5.55 * CEs [26] --> Loop 19 18.04/5.55 * CEs [27] --> Loop 20 18.04/5.55 18.04/5.55 ### Ranking functions of CR fun4(V1,Out) 18.04/5.55 18.04/5.55 #### Partial ranking functions of CR fun4(V1,Out) 18.04/5.55 18.04/5.55 18.04/5.55 ### Specialization of cost equations mark/2 18.04/5.55 * CE 14 is refined into CE [28,29] 18.04/5.55 * CE 15 is refined into CE [30] 18.04/5.55 * CE 16 is refined into CE [31] 18.04/5.55 * CE 17 is refined into CE [32] 18.04/5.55 * CE 11 is refined into CE [33] 18.04/5.55 * CE 10 is refined into CE [34] 18.04/5.55 * CE 9 is refined into CE [35] 18.04/5.55 * CE 13 is refined into CE [36,37,38] 18.04/5.55 * CE 8 is refined into CE [39] 18.04/5.55 * CE 12 is refined into CE [40] 18.04/5.55 18.04/5.55 18.04/5.55 ### Cost equations --> "Loop" of mark/2 18.04/5.55 * CEs [39] --> Loop 21 18.04/5.55 * CEs [40] --> Loop 22 18.04/5.55 * CEs [38] --> Loop 23 18.04/5.55 * CEs [37] --> Loop 24 18.04/5.55 * CEs [33] --> Loop 25 18.04/5.55 * CEs [34] --> Loop 26 18.04/5.55 * CEs [35] --> Loop 27 18.04/5.55 * CEs [36] --> Loop 28 18.04/5.55 * CEs [29] --> Loop 29 18.04/5.55 * CEs [28,30,31] --> Loop 30 18.04/5.55 * CEs [32] --> Loop 31 18.04/5.55 18.04/5.55 ### Ranking functions of CR mark(V1,Out) 18.04/5.55 * RF of phase [21,22,23,24,25,26,27,28]: [V1] 18.04/5.55 18.04/5.55 #### Partial ranking functions of CR mark(V1,Out) 18.04/5.55 * Partial RF of phase [21,22,23,24,25,26,27,28]: 18.04/5.55 - 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]: 18.04/5.55 V1 18.04/5.55 18.04/5.55 18.04/5.55 ### Specialization of cost equations start/3 18.04/5.55 * CE 4 is refined into CE [41,42,43] 18.04/5.55 * CE 3 is refined into CE [44,45,46] 18.04/5.55 * CE 1 is refined into CE [47] 18.04/5.55 * CE 2 is refined into CE [48,49,50] 18.04/5.55 * CE 5 is refined into CE [51,52,53] 18.04/5.55 * CE 6 is refined into CE [54,55] 18.04/5.55 * CE 7 is refined into CE [56,57,58] 18.04/5.55 18.04/5.55 18.04/5.55 ### Cost equations --> "Loop" of start/3 18.04/5.55 * CEs [42,43] --> Loop 32 18.04/5.55 * CEs [41] --> Loop 33 18.04/5.55 * CEs [45,46] --> Loop 34 18.04/5.55 * CEs [44] --> Loop 35 18.04/5.55 * CEs [47,48,49,50,51,52,53,54,55,56,57,58] --> Loop 36 18.04/5.55 18.04/5.55 ### Ranking functions of CR start(V1,V,V2) 18.04/5.55 18.04/5.55 #### Partial ranking functions of CR start(V1,V,V2) 18.04/5.55 18.04/5.55 18.04/5.55 Computing Bounds 18.04/5.55 ===================================== 18.04/5.55 18.04/5.55 #### Cost of chains of fun3(V1,V,Out): 18.04/5.55 * Chain [18]: 1 18.04/5.55 with precondition: [V1=0,Out=2,V>=0] 18.04/5.55 18.04/5.55 * Chain [17]: 1 18.04/5.55 with precondition: [V+V1+1=Out,V1>=0,V>=0] 18.04/5.55 18.04/5.55 * Chain [16]: 1 18.04/5.55 with precondition: [V+V1=Out,V1>=1,V>=1] 18.04/5.55 18.04/5.55 18.04/5.55 #### Cost of chains of fun4(V1,Out): 18.04/5.55 * Chain [20]: 1 18.04/5.55 with precondition: [V1+1=Out,V1>=0] 18.04/5.55 18.04/5.55 * Chain [19]: 1 18.04/5.55 with precondition: [2*V1+3=Out,V1>=0] 18.04/5.55 18.04/5.55 18.04/5.55 #### Cost of chains of mark(V1,Out): 18.04/5.55 * Chain [31]: 1 18.04/5.55 with precondition: [V1=0,Out=0] 18.04/5.55 18.04/5.55 * Chain [30]: 2 18.04/5.55 with precondition: [V1=Out,V1>=1] 18.04/5.55 18.04/5.55 * Chain [29]: 2 18.04/5.55 with precondition: [2*V1+1=Out,V1>=1] 18.04/5.55 18.04/5.55 * 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 18.04/5.55 Such that:aux(10) =< 1 18.04/5.55 aux(11) =< V1 18.04/5.55 aux(12) =< 2/3*V1 18.04/5.55 aux(13) =< 4/3*V1+1/3 18.04/5.55 aux(14) =< 6/7*V1 18.04/5.55 it(21) =< aux(11) 18.04/5.55 it(23) =< aux(11) 18.04/5.55 it(24) =< aux(11) 18.04/5.55 it(25) =< aux(11) 18.04/5.55 it(26) =< aux(11) 18.04/5.55 it([29]) =< aux(11) 18.04/5.55 it(25) =< aux(12) 18.04/5.55 it(24) =< aux(13) 18.04/5.55 it(25) =< aux(13) 18.04/5.55 it(26) =< aux(13) 18.04/5.55 it([29]) =< aux(13) 18.04/5.55 it(23) =< aux(14) 18.04/5.55 it(25) =< aux(14) 18.04/5.55 it(26) =< aux(14) 18.04/5.55 it([29]) =< it(24)+it(24)+it(26)+it(25)+it(24)+it(23)+aux(10) 18.04/5.55 it([31]) =< it(24)+it(24)+it(26)+it(25)+it(24)+it(23)+aux(10) 18.04/5.55 18.04/5.55 with precondition: [V1>=1,Out>=0,5*V1>=2*Out+1,2*V1+1>=Out] 18.04/5.55 18.04/5.55 18.04/5.55 #### Cost of chains of start(V1,V,V2): 18.04/5.55 * 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 18.04/5.55 Such that:s(26) =< V1 18.04/5.55 s(27) =< 2/3*V1 18.04/5.55 s(28) =< 4/3*V1+1/3 18.04/5.55 s(29) =< 6/7*V1 18.04/5.55 s(14) =< V 18.04/5.55 s(15) =< 2/3*V 18.04/5.55 s(16) =< 4/3*V+1/3 18.04/5.55 s(17) =< 6/7*V 18.04/5.55 aux(15) =< 1 18.04/5.55 s(18) =< s(14) 18.04/5.55 s(19) =< s(14) 18.04/5.55 s(20) =< s(14) 18.04/5.55 s(21) =< s(14) 18.04/5.55 s(22) =< s(14) 18.04/5.55 s(23) =< s(14) 18.04/5.55 s(21) =< s(15) 18.04/5.55 s(20) =< s(16) 18.04/5.55 s(21) =< s(16) 18.04/5.55 s(22) =< s(16) 18.04/5.55 s(23) =< s(16) 18.04/5.55 s(19) =< s(17) 18.04/5.55 s(21) =< s(17) 18.04/5.55 s(22) =< s(17) 18.04/5.55 s(23) =< s(20)+s(20)+s(22)+s(21)+s(20)+s(19)+aux(15) 18.04/5.55 s(24) =< s(20)+s(20)+s(22)+s(21)+s(20)+s(19)+aux(15) 18.04/5.55 s(30) =< s(26) 18.04/5.55 s(31) =< s(26) 18.04/5.55 s(32) =< s(26) 18.04/5.55 s(33) =< s(26) 18.04/5.55 s(34) =< s(26) 18.04/5.55 s(35) =< s(26) 18.04/5.55 s(33) =< s(27) 18.04/5.55 s(32) =< s(28) 18.04/5.55 s(33) =< s(28) 18.04/5.55 s(34) =< s(28) 18.04/5.55 s(35) =< s(28) 18.04/5.55 s(31) =< s(29) 18.04/5.55 s(33) =< s(29) 18.04/5.55 s(34) =< s(29) 18.04/5.55 s(35) =< s(32)+s(32)+s(34)+s(33)+s(32)+s(31)+aux(15) 18.04/5.55 s(36) =< s(32)+s(32)+s(34)+s(33)+s(32)+s(31)+aux(15) 18.04/5.55 18.04/5.55 with precondition: [V1>=0] 18.04/5.55 18.04/5.55 * Chain [35]: 2 18.04/5.55 with precondition: [V1=1,V2=0,V>=0] 18.04/5.55 18.04/5.55 * Chain [34]: 4*s(42)+2*s(43)+6*s(44)+2*s(45)+2*s(46)+4*s(47)+1*s(48)+3 18.04/5.55 Such that:s(37) =< 1 18.04/5.55 s(38) =< V2 18.04/5.55 s(39) =< 2/3*V2 18.04/5.55 s(40) =< 4/3*V2+1/3 18.04/5.55 s(41) =< 6/7*V2 18.04/5.55 s(42) =< s(38) 18.04/5.55 s(43) =< s(38) 18.04/5.55 s(44) =< s(38) 18.04/5.55 s(45) =< s(38) 18.04/5.55 s(46) =< s(38) 18.04/5.55 s(47) =< s(38) 18.04/5.55 s(45) =< s(39) 18.04/5.55 s(44) =< s(40) 18.04/5.55 s(45) =< s(40) 18.04/5.55 s(46) =< s(40) 18.04/5.55 s(47) =< s(40) 18.04/5.55 s(43) =< s(41) 18.04/5.55 s(45) =< s(41) 18.04/5.55 s(46) =< s(41) 18.04/5.55 s(47) =< s(44)+s(44)+s(46)+s(45)+s(44)+s(43)+s(37) 18.04/5.55 s(48) =< s(44)+s(44)+s(46)+s(45)+s(44)+s(43)+s(37) 18.04/5.55 18.04/5.55 with precondition: [V1=1,V>=0,V2>=1] 18.04/5.55 18.04/5.55 * Chain [33]: 2 18.04/5.55 with precondition: [V1=3,V=0] 18.04/5.55 18.04/5.55 * Chain [32]: 4*s(54)+2*s(55)+6*s(56)+2*s(57)+2*s(58)+4*s(59)+1*s(60)+3 18.04/5.55 Such that:s(49) =< 1 18.04/5.55 s(50) =< V 18.04/5.55 s(51) =< 2/3*V 18.04/5.55 s(52) =< 4/3*V+1/3 18.04/5.55 s(53) =< 6/7*V 18.04/5.55 s(54) =< s(50) 18.04/5.55 s(55) =< s(50) 18.04/5.55 s(56) =< s(50) 18.04/5.55 s(57) =< s(50) 18.04/5.55 s(58) =< s(50) 18.04/5.55 s(59) =< s(50) 18.04/5.55 s(57) =< s(51) 18.04/5.55 s(56) =< s(52) 18.04/5.55 s(57) =< s(52) 18.04/5.55 s(58) =< s(52) 18.04/5.55 s(59) =< s(52) 18.04/5.55 s(55) =< s(53) 18.04/5.55 s(57) =< s(53) 18.04/5.55 s(58) =< s(53) 18.04/5.55 s(59) =< s(56)+s(56)+s(58)+s(57)+s(56)+s(55)+s(49) 18.04/5.55 s(60) =< s(56)+s(56)+s(58)+s(57)+s(56)+s(55)+s(49) 18.04/5.55 18.04/5.55 with precondition: [V1=3,V>=1] 18.04/5.55 18.04/5.55 18.04/5.55 Closed-form bounds of start(V1,V,V2): 18.04/5.55 ------------------------------------- 18.04/5.55 * Chain [36] with precondition: [V1>=0] 18.04/5.55 - Upper bound: 26*V1+5+nat(V)*26 18.04/5.55 - Complexity: n 18.04/5.55 * Chain [35] with precondition: [V1=1,V2=0,V>=0] 18.04/5.55 - Upper bound: 2 18.04/5.55 - Complexity: constant 18.04/5.55 * Chain [34] with precondition: [V1=1,V>=0,V2>=1] 18.04/5.55 - Upper bound: 26*V2+4 18.04/5.55 - Complexity: n 18.04/5.55 * Chain [33] with precondition: [V1=3,V=0] 18.04/5.55 - Upper bound: 2 18.04/5.55 - Complexity: constant 18.04/5.55 * Chain [32] with precondition: [V1=3,V>=1] 18.04/5.55 - Upper bound: 26*V+4 18.04/5.55 - Complexity: n 18.04/5.55 18.04/5.55 ### Maximum cost of start(V1,V,V2): max([nat(V2)*26+2,nat(V)*26+2+(26*V1+1)])+2 18.04/5.55 Asymptotic class: n 18.04/5.55 * Total analysis performed in 379 ms. 18.04/5.55 18.04/5.55 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (10) 18.04/5.55 BOUNDS(1, n^1) 18.04/5.55 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (11) RenamingProof (BOTH BOUNDS(ID, ID)) 18.04/5.55 Renamed function symbols to avoid clashes with predefined symbol. 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (12) 18.04/5.55 Obligation: 18.04/5.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 18.04/5.55 18.04/5.55 18.04/5.55 The TRS R consists of the following rules: 18.04/5.55 18.04/5.55 a__and(true, X) -> mark(X) 18.04/5.55 a__and(false, Y) -> false 18.04/5.55 a__if(true, X, Y) -> mark(X) 18.04/5.55 a__if(false, X, Y) -> mark(Y) 18.04/5.55 a__add(0', X) -> mark(X) 18.04/5.55 a__add(s(X), Y) -> s(add(X, Y)) 18.04/5.55 a__first(0', X) -> nil 18.04/5.55 a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z)) 18.04/5.55 a__from(X) -> cons(X, from(s(X))) 18.04/5.55 mark(and(X1, X2)) -> a__and(mark(X1), X2) 18.04/5.55 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 18.04/5.55 mark(add(X1, X2)) -> a__add(mark(X1), X2) 18.04/5.55 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 18.04/5.55 mark(from(X)) -> a__from(X) 18.04/5.55 mark(true) -> true 18.04/5.55 mark(false) -> false 18.04/5.55 mark(0') -> 0' 18.04/5.55 mark(s(X)) -> s(X) 18.04/5.55 mark(nil) -> nil 18.04/5.55 mark(cons(X1, X2)) -> cons(X1, X2) 18.04/5.55 a__and(X1, X2) -> and(X1, X2) 18.04/5.55 a__if(X1, X2, X3) -> if(X1, X2, X3) 18.04/5.55 a__add(X1, X2) -> add(X1, X2) 18.04/5.55 a__first(X1, X2) -> first(X1, X2) 18.04/5.55 a__from(X) -> from(X) 18.04/5.55 18.04/5.55 S is empty. 18.04/5.55 Rewrite Strategy: INNERMOST 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (13) SlicingProof (LOWER BOUND(ID)) 18.04/5.55 Sliced the following arguments: 18.04/5.55 s/0 18.04/5.55 cons/0 18.04/5.55 cons/1 18.04/5.55 a__from/0 18.04/5.55 from/0 18.04/5.55 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (14) 18.04/5.55 Obligation: 18.04/5.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 18.04/5.55 18.04/5.55 18.04/5.55 The TRS R consists of the following rules: 18.04/5.55 18.04/5.55 a__and(true, X) -> mark(X) 18.04/5.55 a__and(false, Y) -> false 18.04/5.55 a__if(true, X, Y) -> mark(X) 18.04/5.55 a__if(false, X, Y) -> mark(Y) 18.04/5.55 a__add(0', X) -> mark(X) 18.04/5.55 a__add(s, Y) -> s 18.04/5.55 a__first(0', X) -> nil 18.04/5.55 a__first(s, cons) -> cons 18.04/5.55 a__from -> cons 18.04/5.55 mark(and(X1, X2)) -> a__and(mark(X1), X2) 18.04/5.55 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 18.04/5.55 mark(add(X1, X2)) -> a__add(mark(X1), X2) 18.04/5.55 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 18.04/5.55 mark(from) -> a__from 18.04/5.55 mark(true) -> true 18.04/5.55 mark(false) -> false 18.04/5.55 mark(0') -> 0' 18.04/5.55 mark(s) -> s 18.04/5.55 mark(nil) -> nil 18.04/5.55 mark(cons) -> cons 18.04/5.55 a__and(X1, X2) -> and(X1, X2) 18.04/5.55 a__if(X1, X2, X3) -> if(X1, X2, X3) 18.04/5.55 a__add(X1, X2) -> add(X1, X2) 18.04/5.55 a__first(X1, X2) -> first(X1, X2) 18.04/5.55 a__from -> from 18.04/5.55 18.04/5.55 S is empty. 18.04/5.55 Rewrite Strategy: INNERMOST 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (15) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 18.04/5.55 Infered types. 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (16) 18.04/5.55 Obligation: 18.04/5.55 Innermost TRS: 18.04/5.55 Rules: 18.04/5.55 a__and(true, X) -> mark(X) 18.04/5.55 a__and(false, Y) -> false 18.04/5.55 a__if(true, X, Y) -> mark(X) 18.04/5.55 a__if(false, X, Y) -> mark(Y) 18.04/5.55 a__add(0', X) -> mark(X) 18.04/5.55 a__add(s, Y) -> s 18.04/5.55 a__first(0', X) -> nil 18.04/5.55 a__first(s, cons) -> cons 18.04/5.55 a__from -> cons 18.04/5.55 mark(and(X1, X2)) -> a__and(mark(X1), X2) 18.04/5.55 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 18.04/5.55 mark(add(X1, X2)) -> a__add(mark(X1), X2) 18.04/5.55 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 18.04/5.55 mark(from) -> a__from 18.04/5.55 mark(true) -> true 18.04/5.55 mark(false) -> false 18.04/5.55 mark(0') -> 0' 18.04/5.55 mark(s) -> s 18.04/5.55 mark(nil) -> nil 18.04/5.55 mark(cons) -> cons 18.04/5.55 a__and(X1, X2) -> and(X1, X2) 18.04/5.55 a__if(X1, X2, X3) -> if(X1, X2, X3) 18.04/5.55 a__add(X1, X2) -> add(X1, X2) 18.04/5.55 a__first(X1, X2) -> first(X1, X2) 18.04/5.55 a__from -> from 18.04/5.55 18.04/5.55 Types: 18.04/5.55 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 18.04/5.55 true :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 mark :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 false :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 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 18.04/5.55 0' :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 s :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 nil :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 cons :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 a__from :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 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 18.04/5.55 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 18.04/5.55 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 18.04/5.55 from :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 hole_true:false:0':s:nil:cons:and:if:add:first:from1_0 :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (17) OrderProof (LOWER BOUND(ID)) 18.04/5.55 Heuristically decided to analyse the following defined symbols: 18.04/5.55 mark 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (18) 18.04/5.55 Obligation: 18.04/5.55 Innermost TRS: 18.04/5.55 Rules: 18.04/5.55 a__and(true, X) -> mark(X) 18.04/5.55 a__and(false, Y) -> false 18.04/5.55 a__if(true, X, Y) -> mark(X) 18.04/5.55 a__if(false, X, Y) -> mark(Y) 18.04/5.55 a__add(0', X) -> mark(X) 18.04/5.55 a__add(s, Y) -> s 18.04/5.55 a__first(0', X) -> nil 18.04/5.55 a__first(s, cons) -> cons 18.04/5.55 a__from -> cons 18.04/5.55 mark(and(X1, X2)) -> a__and(mark(X1), X2) 18.04/5.55 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 18.04/5.55 mark(add(X1, X2)) -> a__add(mark(X1), X2) 18.04/5.55 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 18.04/5.55 mark(from) -> a__from 18.04/5.55 mark(true) -> true 18.04/5.55 mark(false) -> false 18.04/5.55 mark(0') -> 0' 18.04/5.55 mark(s) -> s 18.04/5.55 mark(nil) -> nil 18.04/5.55 mark(cons) -> cons 18.04/5.55 a__and(X1, X2) -> and(X1, X2) 18.04/5.55 a__if(X1, X2, X3) -> if(X1, X2, X3) 18.04/5.55 a__add(X1, X2) -> add(X1, X2) 18.04/5.55 a__first(X1, X2) -> first(X1, X2) 18.04/5.55 a__from -> from 18.04/5.55 18.04/5.55 Types: 18.04/5.55 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 18.04/5.55 true :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 mark :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 false :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 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 18.04/5.55 0' :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 s :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 nil :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 cons :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 a__from :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 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 18.04/5.55 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 18.04/5.55 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 18.04/5.55 from :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 hole_true:false:0':s:nil:cons:and:if:add:first:from1_0 :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 18.04/5.55 18.04/5.55 Generator Equations: 18.04/5.55 gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(0) <=> true 18.04/5.55 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) 18.04/5.55 18.04/5.55 18.04/5.55 The following defined symbols remain to be analysed: 18.04/5.55 mark 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (19) RewriteLemmaProof (LOWER BOUND(ID)) 18.04/5.55 Proved the following rewrite lemma: 18.04/5.55 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) 18.04/5.55 18.04/5.55 Induction Base: 18.04/5.55 mark(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(0)) ->_R^Omega(1) 18.04/5.55 true 18.04/5.55 18.04/5.55 Induction Step: 18.04/5.55 mark(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(+(n4_0, 1))) ->_R^Omega(1) 18.04/5.55 a__and(mark(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(n4_0)), true) ->_IH 18.04/5.55 a__and(gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(0), true) ->_R^Omega(1) 18.04/5.55 mark(true) ->_R^Omega(1) 18.04/5.55 true 18.04/5.55 18.04/5.55 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (20) 18.04/5.55 Obligation: 18.04/5.55 Proved the lower bound n^1 for the following obligation: 18.04/5.55 18.04/5.55 Innermost TRS: 18.04/5.55 Rules: 18.04/5.55 a__and(true, X) -> mark(X) 18.04/5.55 a__and(false, Y) -> false 18.04/5.55 a__if(true, X, Y) -> mark(X) 18.04/5.55 a__if(false, X, Y) -> mark(Y) 18.04/5.55 a__add(0', X) -> mark(X) 18.04/5.55 a__add(s, Y) -> s 18.04/5.55 a__first(0', X) -> nil 18.04/5.55 a__first(s, cons) -> cons 18.04/5.55 a__from -> cons 18.04/5.55 mark(and(X1, X2)) -> a__and(mark(X1), X2) 18.04/5.55 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 18.04/5.55 mark(add(X1, X2)) -> a__add(mark(X1), X2) 18.04/5.55 mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) 18.04/5.55 mark(from) -> a__from 18.04/5.55 mark(true) -> true 18.04/5.55 mark(false) -> false 18.04/5.55 mark(0') -> 0' 18.04/5.55 mark(s) -> s 18.04/5.55 mark(nil) -> nil 18.04/5.55 mark(cons) -> cons 18.04/5.55 a__and(X1, X2) -> and(X1, X2) 18.04/5.55 a__if(X1, X2, X3) -> if(X1, X2, X3) 18.04/5.55 a__add(X1, X2) -> add(X1, X2) 18.04/5.55 a__first(X1, X2) -> first(X1, X2) 18.04/5.55 a__from -> from 18.04/5.55 18.04/5.55 Types: 18.04/5.55 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 18.04/5.55 true :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 mark :: true:false:0':s:nil:cons:and:if:add:first:from -> true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 false :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 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 18.04/5.55 0' :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 s :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 nil :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 cons :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 a__from :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 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 18.04/5.55 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 18.04/5.55 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 18.04/5.55 from :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 hole_true:false:0':s:nil:cons:and:if:add:first:from1_0 :: true:false:0':s:nil:cons:and:if:add:first:from 18.04/5.55 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 18.04/5.55 18.04/5.55 18.04/5.55 Generator Equations: 18.04/5.55 gen_true:false:0':s:nil:cons:and:if:add:first:from2_0(0) <=> true 18.04/5.55 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) 18.04/5.55 18.04/5.55 18.04/5.55 The following defined symbols remain to be analysed: 18.04/5.55 mark 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (21) LowerBoundPropagationProof (FINISHED) 18.04/5.55 Propagated lower bound. 18.04/5.55 ---------------------------------------- 18.04/5.55 18.04/5.55 (22) 18.04/5.55 BOUNDS(n^1, INF) 18.75/6.14 EOF