17.76/6.27 WORST_CASE(Omega(n^1), O(n^1)) 18.04/6.29 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 18.04/6.29 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 18.04/6.29 18.04/6.29 18.04/6.29 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 18.04/6.29 18.04/6.29 (0) CpxTRS 18.04/6.29 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/6.29 (2) CpxWeightedTrs 18.04/6.29 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/6.29 (4) CpxTypedWeightedTrs 18.04/6.29 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 18.04/6.29 (6) CpxTypedWeightedCompleteTrs 18.04/6.29 (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/6.29 (8) CpxTypedWeightedCompleteTrs 18.04/6.29 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 18.04/6.29 (10) CpxRNTS 18.04/6.29 (11) InliningProof [UPPER BOUND(ID), 78 ms] 18.04/6.29 (12) CpxRNTS 18.04/6.29 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 1 ms] 18.04/6.29 (14) CpxRNTS 18.04/6.29 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/6.29 (16) CpxRNTS 18.04/6.29 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 18.04/6.29 (18) CpxRNTS 18.04/6.29 (19) IntTrsBoundProof [UPPER BOUND(ID), 149 ms] 18.04/6.29 (20) CpxRNTS 18.04/6.29 (21) IntTrsBoundProof [UPPER BOUND(ID), 5 ms] 18.04/6.29 (22) CpxRNTS 18.04/6.29 (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 18.04/6.29 (24) CpxRNTS 18.04/6.29 (25) IntTrsBoundProof [UPPER BOUND(ID), 189 ms] 18.04/6.29 (26) CpxRNTS 18.04/6.29 (27) IntTrsBoundProof [UPPER BOUND(ID), 42 ms] 18.04/6.29 (28) CpxRNTS 18.04/6.29 (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 18.04/6.29 (30) CpxRNTS 18.04/6.29 (31) IntTrsBoundProof [UPPER BOUND(ID), 310 ms] 18.04/6.29 (32) CpxRNTS 18.04/6.29 (33) IntTrsBoundProof [UPPER BOUND(ID), 158 ms] 18.04/6.29 (34) CpxRNTS 18.04/6.29 (35) FinalProof [FINISHED, 0 ms] 18.04/6.29 (36) BOUNDS(1, n^1) 18.04/6.29 (37) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/6.29 (38) CpxTRS 18.04/6.29 (39) SlicingProof [LOWER BOUND(ID), 0 ms] 18.04/6.29 (40) CpxTRS 18.04/6.29 (41) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 18.04/6.29 (42) typed CpxTrs 18.04/6.29 (43) OrderProof [LOWER BOUND(ID), 0 ms] 18.04/6.29 (44) typed CpxTrs 18.04/6.29 (45) RewriteLemmaProof [LOWER BOUND(ID), 237 ms] 18.04/6.29 (46) proven lower bound 18.04/6.29 (47) LowerBoundPropagationProof [FINISHED, 0 ms] 18.04/6.29 (48) BOUNDS(n^1, INF) 18.04/6.29 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (0) 18.04/6.29 Obligation: 18.04/6.29 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 18.04/6.29 18.04/6.29 18.04/6.29 The TRS R consists of the following rules: 18.04/6.29 18.04/6.29 from(X) -> cons(X, n__from(s(X))) 18.04/6.29 after(0, XS) -> XS 18.04/6.29 after(s(N), cons(X, XS)) -> after(N, activate(XS)) 18.04/6.29 from(X) -> n__from(X) 18.04/6.29 activate(n__from(X)) -> from(X) 18.04/6.29 activate(X) -> X 18.04/6.29 18.04/6.29 S is empty. 18.04/6.29 Rewrite Strategy: INNERMOST 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 18.04/6.29 Transformed relative TRS to weighted TRS 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (2) 18.04/6.29 Obligation: 18.04/6.29 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 18.04/6.29 18.04/6.29 18.04/6.29 The TRS R consists of the following rules: 18.04/6.29 18.04/6.29 from(X) -> cons(X, n__from(s(X))) [1] 18.04/6.29 after(0, XS) -> XS [1] 18.04/6.29 after(s(N), cons(X, XS)) -> after(N, activate(XS)) [1] 18.04/6.29 from(X) -> n__from(X) [1] 18.04/6.29 activate(n__from(X)) -> from(X) [1] 18.04/6.29 activate(X) -> X [1] 18.04/6.29 18.04/6.29 Rewrite Strategy: INNERMOST 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 18.04/6.29 Infered types. 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (4) 18.04/6.29 Obligation: 18.04/6.29 Runtime Complexity Weighted TRS with Types. 18.04/6.29 The TRS R consists of the following rules: 18.04/6.29 18.04/6.29 from(X) -> cons(X, n__from(s(X))) [1] 18.04/6.29 after(0, XS) -> XS [1] 18.04/6.29 after(s(N), cons(X, XS)) -> after(N, activate(XS)) [1] 18.04/6.29 from(X) -> n__from(X) [1] 18.04/6.29 activate(n__from(X)) -> from(X) [1] 18.04/6.29 activate(X) -> X [1] 18.04/6.29 18.04/6.29 The TRS has the following type information: 18.04/6.29 from :: s:0 -> n__from:cons 18.04/6.29 cons :: s:0 -> n__from:cons -> n__from:cons 18.04/6.29 n__from :: s:0 -> n__from:cons 18.04/6.29 s :: s:0 -> s:0 18.04/6.29 after :: s:0 -> n__from:cons -> n__from:cons 18.04/6.29 0 :: s:0 18.04/6.29 activate :: n__from:cons -> n__from:cons 18.04/6.29 18.04/6.29 Rewrite Strategy: INNERMOST 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (5) CompletionProof (UPPER BOUND(ID)) 18.04/6.29 The transformation into a RNTS is sound, since: 18.04/6.29 18.04/6.29 (a) The obligation is a constructor system where every type has a constant constructor, 18.04/6.29 18.04/6.29 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 18.04/6.29 18.04/6.29 after_2 18.04/6.29 18.04/6.29 (c) The following functions are completely defined: 18.04/6.29 18.04/6.29 activate_1 18.04/6.29 from_1 18.04/6.29 18.04/6.29 Due to the following rules being added: 18.04/6.29 none 18.04/6.29 18.04/6.29 And the following fresh constants: const 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (6) 18.04/6.29 Obligation: 18.04/6.29 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 18.04/6.29 18.04/6.29 Runtime Complexity Weighted TRS with Types. 18.04/6.29 The TRS R consists of the following rules: 18.04/6.29 18.04/6.29 from(X) -> cons(X, n__from(s(X))) [1] 18.04/6.29 after(0, XS) -> XS [1] 18.04/6.29 after(s(N), cons(X, XS)) -> after(N, activate(XS)) [1] 18.04/6.29 from(X) -> n__from(X) [1] 18.04/6.29 activate(n__from(X)) -> from(X) [1] 18.04/6.29 activate(X) -> X [1] 18.04/6.29 18.04/6.29 The TRS has the following type information: 18.04/6.29 from :: s:0 -> n__from:cons 18.04/6.29 cons :: s:0 -> n__from:cons -> n__from:cons 18.04/6.29 n__from :: s:0 -> n__from:cons 18.04/6.29 s :: s:0 -> s:0 18.04/6.29 after :: s:0 -> n__from:cons -> n__from:cons 18.04/6.29 0 :: s:0 18.04/6.29 activate :: n__from:cons -> n__from:cons 18.04/6.29 const :: n__from:cons 18.04/6.29 18.04/6.29 Rewrite Strategy: INNERMOST 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (7) NarrowingProof (BOTH BOUNDS(ID, ID)) 18.04/6.29 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (8) 18.04/6.29 Obligation: 18.04/6.29 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 18.04/6.29 18.04/6.29 Runtime Complexity Weighted TRS with Types. 18.04/6.29 The TRS R consists of the following rules: 18.04/6.29 18.04/6.29 from(X) -> cons(X, n__from(s(X))) [1] 18.04/6.29 after(0, XS) -> XS [1] 18.04/6.29 after(s(N), cons(X, n__from(X'))) -> after(N, from(X')) [2] 18.04/6.29 after(s(N), cons(X, XS)) -> after(N, XS) [2] 18.04/6.29 from(X) -> n__from(X) [1] 18.04/6.29 activate(n__from(X)) -> from(X) [1] 18.04/6.29 activate(X) -> X [1] 18.04/6.29 18.04/6.29 The TRS has the following type information: 18.04/6.29 from :: s:0 -> n__from:cons 18.04/6.29 cons :: s:0 -> n__from:cons -> n__from:cons 18.04/6.29 n__from :: s:0 -> n__from:cons 18.04/6.29 s :: s:0 -> s:0 18.04/6.29 after :: s:0 -> n__from:cons -> n__from:cons 18.04/6.29 0 :: s:0 18.04/6.29 activate :: n__from:cons -> n__from:cons 18.04/6.29 const :: n__from:cons 18.04/6.29 18.04/6.29 Rewrite Strategy: INNERMOST 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 18.04/6.29 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 18.04/6.29 The constant constructors are abstracted as follows: 18.04/6.29 18.04/6.29 0 => 0 18.04/6.29 const => 0 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (10) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> X :|: X >= 0, z = X 18.04/6.29 activate(z) -{ 1 }-> from(X) :|: z = 1 + X, X >= 0 18.04/6.29 after(z, z') -{ 1 }-> XS :|: z' = XS, z = 0, XS >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(N, XS) :|: z = 1 + N, z' = 1 + X + XS, X >= 0, XS >= 0, N >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(N, from(X')) :|: z = 1 + N, z' = 1 + X + (1 + X'), X >= 0, X' >= 0, N >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 18.04/6.29 from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X 18.04/6.29 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (11) InliningProof (UPPER BOUND(ID)) 18.04/6.29 Inlined the following terminating rules on right-hand sides where appropriate: 18.04/6.29 18.04/6.29 from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 18.04/6.29 from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (12) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> X :|: X >= 0, z = X 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z = 1 + X, X >= 0, X' >= 0, X = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z = 1 + X, X >= 0, X' >= 0, X = X' 18.04/6.29 after(z, z') -{ 1 }-> XS :|: z' = XS, z = 0, XS >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(N, XS) :|: z = 1 + N, z' = 1 + X + XS, X >= 0, XS >= 0, N >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(N, 1 + X'') :|: z = 1 + N, z' = 1 + X + (1 + X'), X >= 0, X' >= 0, N >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(N, 1 + X'' + (1 + (1 + X''))) :|: z = 1 + N, z' = 1 + X + (1 + X'), X >= 0, X' >= 0, N >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 18.04/6.29 from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X 18.04/6.29 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 18.04/6.29 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (14) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 18.04/6.29 Found the following analysis order by SCC decomposition: 18.04/6.29 18.04/6.29 { activate } 18.04/6.29 { from } 18.04/6.29 { after } 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (16) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: {activate}, {from}, {after} 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (17) ResultPropagationProof (UPPER BOUND(ID)) 18.04/6.29 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (18) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: {activate}, {from}, {after} 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (19) IntTrsBoundProof (UPPER BOUND(ID)) 18.04/6.29 18.04/6.29 Computed SIZE bound using KoAT for: activate 18.04/6.29 after applying outer abstraction to obtain an ITS, 18.04/6.29 resulting in: O(n^1) with polynomial bound: 1 + 2*z 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (20) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: {activate}, {from}, {after} 18.04/6.29 Previous analysis results are: 18.04/6.29 activate: runtime: ?, size: O(n^1) [1 + 2*z] 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (21) IntTrsBoundProof (UPPER BOUND(ID)) 18.04/6.29 18.04/6.29 Computed RUNTIME bound using KoAT for: activate 18.04/6.29 after applying outer abstraction to obtain an ITS, 18.04/6.29 resulting in: O(1) with polynomial bound: 3 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (22) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: {from}, {after} 18.04/6.29 Previous analysis results are: 18.04/6.29 activate: runtime: O(1) [3], size: O(n^1) [1 + 2*z] 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (23) ResultPropagationProof (UPPER BOUND(ID)) 18.04/6.29 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (24) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: {from}, {after} 18.04/6.29 Previous analysis results are: 18.04/6.29 activate: runtime: O(1) [3], size: O(n^1) [1 + 2*z] 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (25) IntTrsBoundProof (UPPER BOUND(ID)) 18.04/6.29 18.04/6.29 Computed SIZE bound using CoFloCo for: from 18.04/6.29 after applying outer abstraction to obtain an ITS, 18.04/6.29 resulting in: O(n^1) with polynomial bound: 3 + 2*z 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (26) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: {from}, {after} 18.04/6.29 Previous analysis results are: 18.04/6.29 activate: runtime: O(1) [3], size: O(n^1) [1 + 2*z] 18.04/6.29 from: runtime: ?, size: O(n^1) [3 + 2*z] 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (27) IntTrsBoundProof (UPPER BOUND(ID)) 18.04/6.29 18.04/6.29 Computed RUNTIME bound using CoFloCo for: from 18.04/6.29 after applying outer abstraction to obtain an ITS, 18.04/6.29 resulting in: O(1) with polynomial bound: 1 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (28) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: {after} 18.04/6.29 Previous analysis results are: 18.04/6.29 activate: runtime: O(1) [3], size: O(n^1) [1 + 2*z] 18.04/6.29 from: runtime: O(1) [1], size: O(n^1) [3 + 2*z] 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (29) ResultPropagationProof (UPPER BOUND(ID)) 18.04/6.29 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (30) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: {after} 18.04/6.29 Previous analysis results are: 18.04/6.29 activate: runtime: O(1) [3], size: O(n^1) [1 + 2*z] 18.04/6.29 from: runtime: O(1) [1], size: O(n^1) [3 + 2*z] 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (31) IntTrsBoundProof (UPPER BOUND(ID)) 18.04/6.29 18.04/6.29 Computed SIZE bound using KoAT for: after 18.04/6.29 after applying outer abstraction to obtain an ITS, 18.04/6.29 resulting in: EXP with polynomial bound: ? 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (32) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: {after} 18.04/6.29 Previous analysis results are: 18.04/6.29 activate: runtime: O(1) [3], size: O(n^1) [1 + 2*z] 18.04/6.29 from: runtime: O(1) [1], size: O(n^1) [3 + 2*z] 18.04/6.29 after: runtime: ?, size: EXP 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (33) IntTrsBoundProof (UPPER BOUND(ID)) 18.04/6.29 18.04/6.29 Computed RUNTIME bound using KoAT for: after 18.04/6.29 after applying outer abstraction to obtain an ITS, 18.04/6.29 resulting in: O(n^1) with polynomial bound: 1 + 8*z 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (34) 18.04/6.29 Obligation: 18.04/6.29 Complexity RNTS consisting of the following rules: 18.04/6.29 18.04/6.29 activate(z) -{ 1 }-> z :|: z >= 0 18.04/6.29 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 18.04/6.29 after(z, z') -{ 1 }-> z' :|: z = 0, z' >= 0 18.04/6.29 after(z, z') -{ 2 }-> after(z - 1, XS) :|: z' = 1 + X + XS, X >= 0, XS >= 0, z - 1 >= 0 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'') :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 after(z, z') -{ 3 }-> after(z - 1, 1 + X'' + (1 + (1 + X''))) :|: z' = 1 + X + (1 + X'), X >= 0, X' >= 0, z - 1 >= 0, X'' >= 0, X' = X'' 18.04/6.29 from(z) -{ 1 }-> 1 + z :|: z >= 0 18.04/6.29 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 18.04/6.29 18.04/6.29 Function symbols to be analyzed: 18.04/6.29 Previous analysis results are: 18.04/6.29 activate: runtime: O(1) [3], size: O(n^1) [1 + 2*z] 18.04/6.29 from: runtime: O(1) [1], size: O(n^1) [3 + 2*z] 18.04/6.29 after: runtime: O(n^1) [1 + 8*z], size: EXP 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (35) FinalProof (FINISHED) 18.04/6.29 Computed overall runtime complexity 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (36) 18.04/6.29 BOUNDS(1, n^1) 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (37) RenamingProof (BOTH BOUNDS(ID, ID)) 18.04/6.29 Renamed function symbols to avoid clashes with predefined symbol. 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (38) 18.04/6.29 Obligation: 18.04/6.29 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 18.04/6.29 18.04/6.29 18.04/6.29 The TRS R consists of the following rules: 18.04/6.29 18.04/6.29 from(X) -> cons(X, n__from(s(X))) 18.04/6.29 after(0', XS) -> XS 18.04/6.29 after(s(N), cons(X, XS)) -> after(N, activate(XS)) 18.04/6.29 from(X) -> n__from(X) 18.04/6.29 activate(n__from(X)) -> from(X) 18.04/6.29 activate(X) -> X 18.04/6.29 18.04/6.29 S is empty. 18.04/6.29 Rewrite Strategy: INNERMOST 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (39) SlicingProof (LOWER BOUND(ID)) 18.04/6.29 Sliced the following arguments: 18.04/6.29 from/0 18.04/6.29 cons/0 18.04/6.29 n__from/0 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (40) 18.04/6.29 Obligation: 18.04/6.29 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 18.04/6.29 18.04/6.29 18.04/6.29 The TRS R consists of the following rules: 18.04/6.29 18.04/6.29 from -> cons(n__from) 18.04/6.29 after(0', XS) -> XS 18.04/6.29 after(s(N), cons(XS)) -> after(N, activate(XS)) 18.04/6.29 from -> n__from 18.04/6.29 activate(n__from) -> from 18.04/6.29 activate(X) -> X 18.04/6.29 18.04/6.29 S is empty. 18.04/6.29 Rewrite Strategy: INNERMOST 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (41) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 18.04/6.29 Infered types. 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (42) 18.04/6.29 Obligation: 18.04/6.29 Innermost TRS: 18.04/6.29 Rules: 18.04/6.29 from -> cons(n__from) 18.04/6.29 after(0', XS) -> XS 18.04/6.29 after(s(N), cons(XS)) -> after(N, activate(XS)) 18.04/6.29 from -> n__from 18.04/6.29 activate(n__from) -> from 18.04/6.29 activate(X) -> X 18.04/6.29 18.04/6.29 Types: 18.04/6.29 from :: n__from:cons 18.04/6.29 cons :: n__from:cons -> n__from:cons 18.04/6.29 n__from :: n__from:cons 18.04/6.29 after :: 0':s -> n__from:cons -> n__from:cons 18.04/6.29 0' :: 0':s 18.04/6.29 s :: 0':s -> 0':s 18.04/6.29 activate :: n__from:cons -> n__from:cons 18.04/6.29 hole_n__from:cons1_0 :: n__from:cons 18.04/6.29 hole_0':s2_0 :: 0':s 18.04/6.29 gen_n__from:cons3_0 :: Nat -> n__from:cons 18.04/6.29 gen_0':s4_0 :: Nat -> 0':s 18.04/6.29 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (43) OrderProof (LOWER BOUND(ID)) 18.04/6.29 Heuristically decided to analyse the following defined symbols: 18.04/6.29 after 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (44) 18.04/6.29 Obligation: 18.04/6.29 Innermost TRS: 18.04/6.29 Rules: 18.04/6.29 from -> cons(n__from) 18.04/6.29 after(0', XS) -> XS 18.04/6.29 after(s(N), cons(XS)) -> after(N, activate(XS)) 18.04/6.29 from -> n__from 18.04/6.29 activate(n__from) -> from 18.04/6.29 activate(X) -> X 18.04/6.29 18.04/6.29 Types: 18.04/6.29 from :: n__from:cons 18.04/6.29 cons :: n__from:cons -> n__from:cons 18.04/6.29 n__from :: n__from:cons 18.04/6.29 after :: 0':s -> n__from:cons -> n__from:cons 18.04/6.29 0' :: 0':s 18.04/6.29 s :: 0':s -> 0':s 18.04/6.29 activate :: n__from:cons -> n__from:cons 18.04/6.29 hole_n__from:cons1_0 :: n__from:cons 18.04/6.29 hole_0':s2_0 :: 0':s 18.04/6.29 gen_n__from:cons3_0 :: Nat -> n__from:cons 18.04/6.29 gen_0':s4_0 :: Nat -> 0':s 18.04/6.29 18.04/6.29 18.04/6.29 Generator Equations: 18.04/6.29 gen_n__from:cons3_0(0) <=> n__from 18.04/6.29 gen_n__from:cons3_0(+(x, 1)) <=> cons(gen_n__from:cons3_0(x)) 18.04/6.29 gen_0':s4_0(0) <=> 0' 18.04/6.29 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 18.04/6.29 18.04/6.29 18.04/6.29 The following defined symbols remain to be analysed: 18.04/6.29 after 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (45) RewriteLemmaProof (LOWER BOUND(ID)) 18.04/6.29 Proved the following rewrite lemma: 18.04/6.29 after(gen_0':s4_0(n6_0), gen_n__from:cons3_0(1)) -> gen_n__from:cons3_0(1), rt in Omega(1 + n6_0) 18.04/6.29 18.04/6.29 Induction Base: 18.04/6.29 after(gen_0':s4_0(0), gen_n__from:cons3_0(1)) ->_R^Omega(1) 18.04/6.29 gen_n__from:cons3_0(1) 18.04/6.29 18.04/6.29 Induction Step: 18.04/6.29 after(gen_0':s4_0(+(n6_0, 1)), gen_n__from:cons3_0(1)) ->_R^Omega(1) 18.04/6.29 after(gen_0':s4_0(n6_0), activate(gen_n__from:cons3_0(0))) ->_R^Omega(1) 18.04/6.29 after(gen_0':s4_0(n6_0), from) ->_R^Omega(1) 18.04/6.29 after(gen_0':s4_0(n6_0), cons(n__from)) ->_IH 18.04/6.29 gen_n__from:cons3_0(1) 18.04/6.29 18.04/6.29 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (46) 18.04/6.29 Obligation: 18.04/6.29 Proved the lower bound n^1 for the following obligation: 18.04/6.29 18.04/6.29 Innermost TRS: 18.04/6.29 Rules: 18.04/6.29 from -> cons(n__from) 18.04/6.29 after(0', XS) -> XS 18.04/6.29 after(s(N), cons(XS)) -> after(N, activate(XS)) 18.04/6.29 from -> n__from 18.04/6.29 activate(n__from) -> from 18.04/6.29 activate(X) -> X 18.04/6.29 18.04/6.29 Types: 18.04/6.29 from :: n__from:cons 18.04/6.29 cons :: n__from:cons -> n__from:cons 18.04/6.29 n__from :: n__from:cons 18.04/6.29 after :: 0':s -> n__from:cons -> n__from:cons 18.04/6.29 0' :: 0':s 18.04/6.29 s :: 0':s -> 0':s 18.04/6.29 activate :: n__from:cons -> n__from:cons 18.04/6.29 hole_n__from:cons1_0 :: n__from:cons 18.04/6.29 hole_0':s2_0 :: 0':s 18.04/6.29 gen_n__from:cons3_0 :: Nat -> n__from:cons 18.04/6.29 gen_0':s4_0 :: Nat -> 0':s 18.04/6.29 18.04/6.29 18.04/6.29 Generator Equations: 18.04/6.29 gen_n__from:cons3_0(0) <=> n__from 18.04/6.29 gen_n__from:cons3_0(+(x, 1)) <=> cons(gen_n__from:cons3_0(x)) 18.04/6.29 gen_0':s4_0(0) <=> 0' 18.04/6.29 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 18.04/6.29 18.04/6.29 18.04/6.29 The following defined symbols remain to be analysed: 18.04/6.29 after 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (47) LowerBoundPropagationProof (FINISHED) 18.04/6.29 Propagated lower bound. 18.04/6.29 ---------------------------------------- 18.04/6.29 18.04/6.29 (48) 18.04/6.29 BOUNDS(n^1, INF) 18.06/8.59 EOF