33.29/12.88 WORST_CASE(Omega(n^1), O(n^1)) 33.29/12.89 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 33.29/12.89 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 33.29/12.89 33.29/12.89 33.29/12.89 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.29/12.89 33.29/12.89 (0) CpxTRS 33.29/12.89 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 33.29/12.89 (2) CpxTRS 33.29/12.89 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 33.29/12.89 (4) CpxWeightedTrs 33.29/12.89 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 33.29/12.89 (6) CpxTypedWeightedTrs 33.29/12.89 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 33.29/12.89 (8) CpxTypedWeightedCompleteTrs 33.29/12.89 (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 33.29/12.89 (10) CpxTypedWeightedCompleteTrs 33.29/12.89 (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 33.29/12.89 (12) CpxRNTS 33.29/12.89 (13) InliningProof [UPPER BOUND(ID), 76 ms] 33.29/12.89 (14) CpxRNTS 33.29/12.89 (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 33.29/12.89 (16) CpxRNTS 33.29/12.89 (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 33.29/12.89 (18) CpxRNTS 33.29/12.89 (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 33.29/12.89 (20) CpxRNTS 33.29/12.89 (21) IntTrsBoundProof [UPPER BOUND(ID), 264 ms] 33.29/12.89 (22) CpxRNTS 33.29/12.89 (23) IntTrsBoundProof [UPPER BOUND(ID), 45 ms] 33.29/12.89 (24) CpxRNTS 33.29/12.89 (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 33.29/12.89 (26) CpxRNTS 33.29/12.89 (27) IntTrsBoundProof [UPPER BOUND(ID), 5257 ms] 33.29/12.89 (28) CpxRNTS 33.29/12.89 (29) IntTrsBoundProof [UPPER BOUND(ID), 518 ms] 33.29/12.89 (30) CpxRNTS 33.29/12.89 (31) FinalProof [FINISHED, 0 ms] 33.29/12.89 (32) BOUNDS(1, n^1) 33.29/12.89 (33) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 33.29/12.89 (34) TRS for Loop Detection 33.29/12.89 (35) DecreasingLoopProof [LOWER BOUND(ID), 38 ms] 33.29/12.89 (36) BEST 33.29/12.89 (37) proven lower bound 33.29/12.89 (38) LowerBoundPropagationProof [FINISHED, 0 ms] 33.29/12.89 (39) BOUNDS(n^1, INF) 33.29/12.89 (40) TRS for Loop Detection 33.29/12.89 33.29/12.89 33.29/12.89 ---------------------------------------- 33.29/12.89 33.29/12.89 (0) 33.29/12.89 Obligation: 33.29/12.89 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.29/12.89 33.29/12.89 33.29/12.89 The TRS R consists of the following rules: 33.29/12.89 33.29/12.89 fst(0, Z) -> nil 33.29/12.89 fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) 33.29/12.89 from(X) -> cons(X, n__from(s(X))) 33.29/12.89 add(0, X) -> X 33.29/12.89 add(s(X), Y) -> s(n__add(activate(X), Y)) 33.29/12.89 len(nil) -> 0 33.29/12.89 len(cons(X, Z)) -> s(n__len(activate(Z))) 33.29/12.89 fst(X1, X2) -> n__fst(X1, X2) 33.29/12.89 from(X) -> n__from(X) 33.29/12.89 add(X1, X2) -> n__add(X1, X2) 33.29/12.89 len(X) -> n__len(X) 33.29/12.89 activate(n__fst(X1, X2)) -> fst(X1, X2) 33.29/12.89 activate(n__from(X)) -> from(X) 33.29/12.89 activate(n__add(X1, X2)) -> add(X1, X2) 33.29/12.89 activate(n__len(X)) -> len(X) 33.29/12.89 activate(X) -> X 33.29/12.89 33.29/12.89 S is empty. 33.29/12.89 Rewrite Strategy: FULL 33.29/12.89 ---------------------------------------- 33.29/12.89 33.29/12.89 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 33.29/12.89 Converted rc-obligation to irc-obligation. 33.29/12.89 33.29/12.89 As the TRS does not nest defined symbols, we have rc = irc. 33.29/12.89 ---------------------------------------- 33.29/12.89 33.29/12.89 (2) 33.29/12.89 Obligation: 33.29/12.89 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 33.29/12.89 33.29/12.89 33.29/12.89 The TRS R consists of the following rules: 33.29/12.89 33.29/12.89 fst(0, Z) -> nil 33.29/12.89 fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) 33.29/12.89 from(X) -> cons(X, n__from(s(X))) 33.29/12.89 add(0, X) -> X 33.29/12.89 add(s(X), Y) -> s(n__add(activate(X), Y)) 33.29/12.89 len(nil) -> 0 33.29/12.89 len(cons(X, Z)) -> s(n__len(activate(Z))) 33.29/12.89 fst(X1, X2) -> n__fst(X1, X2) 33.29/12.89 from(X) -> n__from(X) 33.29/12.89 add(X1, X2) -> n__add(X1, X2) 33.29/12.89 len(X) -> n__len(X) 33.29/12.89 activate(n__fst(X1, X2)) -> fst(X1, X2) 33.29/12.89 activate(n__from(X)) -> from(X) 33.29/12.89 activate(n__add(X1, X2)) -> add(X1, X2) 33.29/12.89 activate(n__len(X)) -> len(X) 33.29/12.89 activate(X) -> X 33.29/12.89 33.29/12.89 S is empty. 33.29/12.89 Rewrite Strategy: INNERMOST 33.29/12.89 ---------------------------------------- 33.29/12.89 33.29/12.89 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 33.29/12.89 Transformed relative TRS to weighted TRS 33.29/12.89 ---------------------------------------- 33.29/12.89 33.29/12.89 (4) 33.29/12.89 Obligation: 33.29/12.89 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 33.29/12.89 33.29/12.89 33.29/12.89 The TRS R consists of the following rules: 33.29/12.89 33.29/12.89 fst(0, Z) -> nil [1] 33.29/12.89 fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) [1] 33.29/12.89 from(X) -> cons(X, n__from(s(X))) [1] 33.29/12.89 add(0, X) -> X [1] 33.29/12.89 add(s(X), Y) -> s(n__add(activate(X), Y)) [1] 33.29/12.89 len(nil) -> 0 [1] 33.29/12.89 len(cons(X, Z)) -> s(n__len(activate(Z))) [1] 33.29/12.89 fst(X1, X2) -> n__fst(X1, X2) [1] 33.29/12.89 from(X) -> n__from(X) [1] 33.29/12.89 add(X1, X2) -> n__add(X1, X2) [1] 33.29/12.89 len(X) -> n__len(X) [1] 33.29/12.89 activate(n__fst(X1, X2)) -> fst(X1, X2) [1] 33.29/12.89 activate(n__from(X)) -> from(X) [1] 33.29/12.89 activate(n__add(X1, X2)) -> add(X1, X2) [1] 33.29/12.89 activate(n__len(X)) -> len(X) [1] 33.29/12.89 activate(X) -> X [1] 33.29/12.89 33.29/12.89 Rewrite Strategy: INNERMOST 33.29/12.89 ---------------------------------------- 33.29/12.89 33.29/12.89 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 33.29/12.89 Infered types. 33.29/12.89 ---------------------------------------- 33.29/12.89 33.29/12.89 (6) 33.29/12.89 Obligation: 33.29/12.89 Runtime Complexity Weighted TRS with Types. 33.29/12.89 The TRS R consists of the following rules: 33.29/12.89 33.29/12.89 fst(0, Z) -> nil [1] 33.29/12.89 fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) [1] 33.29/12.89 from(X) -> cons(X, n__from(s(X))) [1] 33.29/12.89 add(0, X) -> X [1] 33.29/12.89 add(s(X), Y) -> s(n__add(activate(X), Y)) [1] 33.29/12.89 len(nil) -> 0 [1] 33.29/12.89 len(cons(X, Z)) -> s(n__len(activate(Z))) [1] 33.29/12.89 fst(X1, X2) -> n__fst(X1, X2) [1] 33.29/12.89 from(X) -> n__from(X) [1] 33.29/12.89 add(X1, X2) -> n__add(X1, X2) [1] 33.29/12.89 len(X) -> n__len(X) [1] 33.29/12.89 activate(n__fst(X1, X2)) -> fst(X1, X2) [1] 33.29/12.89 activate(n__from(X)) -> from(X) [1] 33.29/12.89 activate(n__add(X1, X2)) -> add(X1, X2) [1] 33.29/12.89 activate(n__len(X)) -> len(X) [1] 33.29/12.89 activate(X) -> X [1] 33.29/12.89 33.29/12.89 The TRS has the following type information: 33.29/12.89 fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 0 :: 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 nil :: 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 s :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 cons :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 n__fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 activate :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 n__from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 n__add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 n__len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.89 33.29/12.89 Rewrite Strategy: INNERMOST 33.29/12.89 ---------------------------------------- 33.29/12.89 33.29/12.89 (7) CompletionProof (UPPER BOUND(ID)) 33.29/12.89 The transformation into a RNTS is sound, since: 33.29/12.89 33.29/12.89 (a) The obligation is a constructor system where every type has a constant constructor, 33.29/12.89 33.29/12.89 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 33.29/12.89 33.29/12.89 fst_2 33.29/12.89 from_1 33.29/12.89 add_2 33.29/12.89 len_1 33.29/12.89 activate_1 33.29/12.89 33.29/12.89 (c) The following functions are completely defined: 33.29/12.89 none 33.29/12.89 33.29/12.89 Due to the following rules being added: 33.29/12.89 none 33.29/12.89 33.29/12.89 And the following fresh constants: none 33.29/12.89 33.29/12.89 ---------------------------------------- 33.29/12.89 33.29/12.89 (8) 33.29/12.89 Obligation: 33.29/12.89 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 33.29/12.89 33.29/12.89 Runtime Complexity Weighted TRS with Types. 33.29/12.89 The TRS R consists of the following rules: 33.29/12.89 33.29/12.89 fst(0, Z) -> nil [1] 33.29/12.89 fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) [1] 33.29/12.89 from(X) -> cons(X, n__from(s(X))) [1] 33.29/12.89 add(0, X) -> X [1] 33.29/12.89 add(s(X), Y) -> s(n__add(activate(X), Y)) [1] 33.29/12.89 len(nil) -> 0 [1] 33.29/12.89 len(cons(X, Z)) -> s(n__len(activate(Z))) [1] 33.29/12.89 fst(X1, X2) -> n__fst(X1, X2) [1] 33.29/12.89 from(X) -> n__from(X) [1] 33.29/12.89 add(X1, X2) -> n__add(X1, X2) [1] 33.29/12.89 len(X) -> n__len(X) [1] 33.29/12.89 activate(n__fst(X1, X2)) -> fst(X1, X2) [1] 33.29/12.89 activate(n__from(X)) -> from(X) [1] 33.29/12.89 activate(n__add(X1, X2)) -> add(X1, X2) [1] 33.29/12.89 activate(n__len(X)) -> len(X) [1] 33.29/12.89 activate(X) -> X [1] 33.29/12.89 33.29/12.89 The TRS has the following type information: 33.29/12.90 fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 0 :: 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 nil :: 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 s :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 cons :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 n__fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 activate :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 n__from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 n__add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 n__len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 33.29/12.90 Rewrite Strategy: INNERMOST 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (9) NarrowingProof (BOTH BOUNDS(ID, ID)) 33.29/12.90 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (10) 33.29/12.90 Obligation: 33.29/12.90 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 33.29/12.90 33.29/12.90 Runtime Complexity Weighted TRS with Types. 33.29/12.90 The TRS R consists of the following rules: 33.29/12.90 33.29/12.90 fst(0, Z) -> nil [1] 33.29/12.90 fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) [1] 33.29/12.90 from(X) -> cons(X, n__from(s(X))) [1] 33.29/12.90 add(0, X) -> X [1] 33.29/12.90 add(s(X), Y) -> s(n__add(activate(X), Y)) [1] 33.29/12.90 len(nil) -> 0 [1] 33.29/12.90 len(cons(X, Z)) -> s(n__len(activate(Z))) [1] 33.29/12.90 fst(X1, X2) -> n__fst(X1, X2) [1] 33.29/12.90 from(X) -> n__from(X) [1] 33.29/12.90 add(X1, X2) -> n__add(X1, X2) [1] 33.29/12.90 len(X) -> n__len(X) [1] 33.29/12.90 activate(n__fst(X1, X2)) -> fst(X1, X2) [1] 33.29/12.90 activate(n__from(X)) -> from(X) [1] 33.29/12.90 activate(n__add(X1, X2)) -> add(X1, X2) [1] 33.29/12.90 activate(n__len(X)) -> len(X) [1] 33.29/12.90 activate(X) -> X [1] 33.29/12.90 33.29/12.90 The TRS has the following type information: 33.29/12.90 fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 0 :: 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 nil :: 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 s :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 cons :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 n__fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 activate :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 n__from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 n__add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 n__len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 33.29/12.90 33.29/12.90 Rewrite Strategy: INNERMOST 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 33.29/12.90 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 33.29/12.90 The constant constructors are abstracted as follows: 33.29/12.90 33.29/12.90 0 => 0 33.29/12.90 nil => 1 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (12) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> X :|: X >= 0, z = X 33.29/12.90 activate(z) -{ 1 }-> len(X) :|: z = 1 + X, X >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> from(X) :|: z = 1 + X, X >= 0 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 add(z, z') -{ 1 }-> X :|: z' = X, X >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(X) + Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 33.29/12.90 from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 33.29/12.90 from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: Z >= 0, z' = Z, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(X) + activate(Z)) :|: Z >= 0, z = 1 + X, Y >= 0, X >= 0, z' = 1 + Y + Z 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (13) InliningProof (UPPER BOUND(ID)) 33.29/12.90 Inlined the following terminating rules on right-hand sides where appropriate: 33.29/12.90 33.29/12.90 from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 33.29/12.90 from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (14) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> X :|: X >= 0, z = X 33.29/12.90 activate(z) -{ 1 }-> len(X) :|: z = 1 + X, X >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 2 }-> 1 + X' :|: z = 1 + X, X >= 0, X' >= 0, X = X' 33.29/12.90 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z = 1 + X, X >= 0, X' >= 0, X = X' 33.29/12.90 add(z, z') -{ 1 }-> X :|: z' = X, X >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(X) + Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 33.29/12.90 from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 33.29/12.90 from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: Z >= 0, z' = Z, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(X) + activate(Z)) :|: Z >= 0, z = 1 + X, Y >= 0, X >= 0, z' = 1 + Y + Z 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (15) SimplificationProof (BOTH BOUNDS(ID, ID)) 33.29/12.90 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (16) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> z :|: z >= 0 33.29/12.90 activate(z) -{ 1 }-> len(z - 1) :|: z - 1 >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(z - 1) + z') :|: z' >= 0, z - 1 >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 33.29/12.90 fst(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 33.29/12.90 Found the following analysis order by SCC decomposition: 33.29/12.90 33.29/12.90 { from } 33.29/12.90 { fst, add, activate, len } 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (18) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> z :|: z >= 0 33.29/12.90 activate(z) -{ 1 }-> len(z - 1) :|: z - 1 >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(z - 1) + z') :|: z' >= 0, z - 1 >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 33.29/12.90 fst(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 Function symbols to be analyzed: {from}, {fst,add,activate,len} 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (19) ResultPropagationProof (UPPER BOUND(ID)) 33.29/12.90 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (20) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> z :|: z >= 0 33.29/12.90 activate(z) -{ 1 }-> len(z - 1) :|: z - 1 >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(z - 1) + z') :|: z' >= 0, z - 1 >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 33.29/12.90 fst(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 Function symbols to be analyzed: {from}, {fst,add,activate,len} 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (21) IntTrsBoundProof (UPPER BOUND(ID)) 33.29/12.90 33.29/12.90 Computed SIZE bound using CoFloCo for: from 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(n^1) with polynomial bound: 3 + 2*z 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (22) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> z :|: z >= 0 33.29/12.90 activate(z) -{ 1 }-> len(z - 1) :|: z - 1 >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(z - 1) + z') :|: z' >= 0, z - 1 >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 33.29/12.90 fst(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 Function symbols to be analyzed: {from}, {fst,add,activate,len} 33.29/12.90 Previous analysis results are: 33.29/12.90 from: runtime: ?, size: O(n^1) [3 + 2*z] 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (23) IntTrsBoundProof (UPPER BOUND(ID)) 33.29/12.90 33.29/12.90 Computed RUNTIME bound using CoFloCo for: from 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(1) with polynomial bound: 1 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (24) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> z :|: z >= 0 33.29/12.90 activate(z) -{ 1 }-> len(z - 1) :|: z - 1 >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(z - 1) + z') :|: z' >= 0, z - 1 >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 33.29/12.90 fst(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 Function symbols to be analyzed: {fst,add,activate,len} 33.29/12.90 Previous analysis results are: 33.29/12.90 from: runtime: O(1) [1], size: O(n^1) [3 + 2*z] 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (25) ResultPropagationProof (UPPER BOUND(ID)) 33.29/12.90 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (26) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> z :|: z >= 0 33.29/12.90 activate(z) -{ 1 }-> len(z - 1) :|: z - 1 >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(z - 1) + z') :|: z' >= 0, z - 1 >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 33.29/12.90 fst(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 Function symbols to be analyzed: {fst,add,activate,len} 33.29/12.90 Previous analysis results are: 33.29/12.90 from: runtime: O(1) [1], size: O(n^1) [3 + 2*z] 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (27) IntTrsBoundProof (UPPER BOUND(ID)) 33.29/12.90 33.29/12.90 Computed SIZE bound using KoAT for: fst 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(n^2) with polynomial bound: 14 + 26*z + 24*z*z' + 12*z^2 + 26*z' + 12*z'^2 33.29/12.90 33.29/12.90 Computed SIZE bound using KoAT for: add 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(n^2) with polynomial bound: 20 + 64*z + z*z' + 49*z^2 + 2*z' 33.29/12.90 33.29/12.90 Computed SIZE bound using KoAT for: activate 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(n^2) with polynomial bound: 39 + 125*z + 98*z^2 33.29/12.90 33.29/12.90 Computed SIZE bound using KoAT for: len 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(n^2) with polynomial bound: 42 + 126*z + 98*z^2 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (28) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> z :|: z >= 0 33.29/12.90 activate(z) -{ 1 }-> len(z - 1) :|: z - 1 >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(z - 1) + z') :|: z' >= 0, z - 1 >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 33.29/12.90 fst(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 Function symbols to be analyzed: {fst,add,activate,len} 33.29/12.90 Previous analysis results are: 33.29/12.90 from: runtime: O(1) [1], size: O(n^1) [3 + 2*z] 33.29/12.90 fst: runtime: ?, size: O(n^2) [14 + 26*z + 24*z*z' + 12*z^2 + 26*z' + 12*z'^2] 33.29/12.90 add: runtime: ?, size: O(n^2) [20 + 64*z + z*z' + 49*z^2 + 2*z'] 33.29/12.90 activate: runtime: ?, size: O(n^2) [39 + 125*z + 98*z^2] 33.29/12.90 len: runtime: ?, size: O(n^2) [42 + 126*z + 98*z^2] 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (29) IntTrsBoundProof (UPPER BOUND(ID)) 33.29/12.90 33.29/12.90 Computed RUNTIME bound using KoAT for: fst 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(n^1) with polynomial bound: 15 + 15*z + 15*z' 33.29/12.90 33.29/12.90 Computed RUNTIME bound using KoAT for: add 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(n^1) with polynomial bound: 23 + 34*z 33.29/12.90 33.29/12.90 Computed RUNTIME bound using KoAT for: activate 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(n^1) with polynomial bound: 45 + 66*z 33.29/12.90 33.29/12.90 Computed RUNTIME bound using CoFloCo for: len 33.29/12.90 after applying outer abstraction to obtain an ITS, 33.29/12.90 resulting in: O(n^1) with polynomial bound: 20 + 66*z 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (30) 33.29/12.90 Obligation: 33.29/12.90 Complexity RNTS consisting of the following rules: 33.29/12.90 33.29/12.90 activate(z) -{ 1 }-> z :|: z >= 0 33.29/12.90 activate(z) -{ 1 }-> len(z - 1) :|: z - 1 >= 0 33.29/12.90 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 33.29/12.90 activate(z) -{ 2 }-> 1 + X' :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 activate(z) -{ 2 }-> 1 + X' + (1 + (1 + X')) :|: z - 1 >= 0, X' >= 0, z - 1 = X' 33.29/12.90 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + (1 + activate(z - 1) + z') :|: z' >= 0, z - 1 >= 0 33.29/12.90 add(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 from(z) -{ 1 }-> 1 + z + (1 + (1 + z)) :|: z >= 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 33.29/12.90 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 33.29/12.90 fst(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 33.29/12.90 len(z) -{ 1 }-> 0 :|: z = 1 33.29/12.90 len(z) -{ 1 }-> 1 + z :|: z >= 0 33.29/12.90 len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z 33.29/12.90 33.29/12.90 Function symbols to be analyzed: 33.29/12.90 Previous analysis results are: 33.29/12.90 from: runtime: O(1) [1], size: O(n^1) [3 + 2*z] 33.29/12.90 fst: runtime: O(n^1) [15 + 15*z + 15*z'], size: O(n^2) [14 + 26*z + 24*z*z' + 12*z^2 + 26*z' + 12*z'^2] 33.29/12.90 add: runtime: O(n^1) [23 + 34*z], size: O(n^2) [20 + 64*z + z*z' + 49*z^2 + 2*z'] 33.29/12.90 activate: runtime: O(n^1) [45 + 66*z], size: O(n^2) [39 + 125*z + 98*z^2] 33.29/12.90 len: runtime: O(n^1) [20 + 66*z], size: O(n^2) [42 + 126*z + 98*z^2] 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (31) FinalProof (FINISHED) 33.29/12.90 Computed overall runtime complexity 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (32) 33.29/12.90 BOUNDS(1, n^1) 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (33) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 33.29/12.90 Transformed a relative TRS into a decreasing-loop problem. 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (34) 33.29/12.90 Obligation: 33.29/12.90 Analyzing the following TRS for decreasing loops: 33.29/12.90 33.29/12.90 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.29/12.90 33.29/12.90 33.29/12.90 The TRS R consists of the following rules: 33.29/12.90 33.29/12.90 fst(0, Z) -> nil 33.29/12.90 fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) 33.29/12.90 from(X) -> cons(X, n__from(s(X))) 33.29/12.90 add(0, X) -> X 33.29/12.90 add(s(X), Y) -> s(n__add(activate(X), Y)) 33.29/12.90 len(nil) -> 0 33.29/12.90 len(cons(X, Z)) -> s(n__len(activate(Z))) 33.29/12.90 fst(X1, X2) -> n__fst(X1, X2) 33.29/12.90 from(X) -> n__from(X) 33.29/12.90 add(X1, X2) -> n__add(X1, X2) 33.29/12.90 len(X) -> n__len(X) 33.29/12.90 activate(n__fst(X1, X2)) -> fst(X1, X2) 33.29/12.90 activate(n__from(X)) -> from(X) 33.29/12.90 activate(n__add(X1, X2)) -> add(X1, X2) 33.29/12.90 activate(n__len(X)) -> len(X) 33.29/12.90 activate(X) -> X 33.29/12.90 33.29/12.90 S is empty. 33.29/12.90 Rewrite Strategy: FULL 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (35) DecreasingLoopProof (LOWER BOUND(ID)) 33.29/12.90 The following loop(s) give(s) rise to the lower bound Omega(n^1): 33.29/12.90 33.29/12.90 The rewrite sequence 33.29/12.90 33.29/12.90 activate(n__fst(s(X1_0), cons(Y2_0, Z3_0))) ->^+ cons(Y2_0, n__fst(activate(X1_0), activate(Z3_0))) 33.29/12.90 33.29/12.90 gives rise to a decreasing loop by considering the right hand sides subterm at position [1,0]. 33.29/12.90 33.29/12.90 The pumping substitution is [X1_0 / n__fst(s(X1_0), cons(Y2_0, Z3_0))]. 33.29/12.90 33.29/12.90 The result substitution is [ ]. 33.29/12.90 33.29/12.90 33.29/12.90 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (36) 33.29/12.90 Complex Obligation (BEST) 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (37) 33.29/12.90 Obligation: 33.29/12.90 Proved the lower bound n^1 for the following obligation: 33.29/12.90 33.29/12.90 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.29/12.90 33.29/12.90 33.29/12.90 The TRS R consists of the following rules: 33.29/12.90 33.29/12.90 fst(0, Z) -> nil 33.29/12.90 fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) 33.29/12.90 from(X) -> cons(X, n__from(s(X))) 33.29/12.90 add(0, X) -> X 33.29/12.90 add(s(X), Y) -> s(n__add(activate(X), Y)) 33.29/12.90 len(nil) -> 0 33.29/12.90 len(cons(X, Z)) -> s(n__len(activate(Z))) 33.29/12.90 fst(X1, X2) -> n__fst(X1, X2) 33.29/12.90 from(X) -> n__from(X) 33.29/12.90 add(X1, X2) -> n__add(X1, X2) 33.29/12.90 len(X) -> n__len(X) 33.29/12.90 activate(n__fst(X1, X2)) -> fst(X1, X2) 33.29/12.90 activate(n__from(X)) -> from(X) 33.29/12.90 activate(n__add(X1, X2)) -> add(X1, X2) 33.29/12.90 activate(n__len(X)) -> len(X) 33.29/12.90 activate(X) -> X 33.29/12.90 33.29/12.90 S is empty. 33.29/12.90 Rewrite Strategy: FULL 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (38) LowerBoundPropagationProof (FINISHED) 33.29/12.90 Propagated lower bound. 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (39) 33.29/12.90 BOUNDS(n^1, INF) 33.29/12.90 33.29/12.90 ---------------------------------------- 33.29/12.90 33.29/12.90 (40) 33.29/12.90 Obligation: 33.29/12.90 Analyzing the following TRS for decreasing loops: 33.29/12.90 33.29/12.90 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.29/12.90 33.29/12.90 33.29/12.90 The TRS R consists of the following rules: 33.29/12.90 33.29/12.90 fst(0, Z) -> nil 33.29/12.90 fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) 33.29/12.90 from(X) -> cons(X, n__from(s(X))) 33.29/12.90 add(0, X) -> X 33.29/12.90 add(s(X), Y) -> s(n__add(activate(X), Y)) 33.29/12.90 len(nil) -> 0 33.29/12.90 len(cons(X, Z)) -> s(n__len(activate(Z))) 33.29/12.90 fst(X1, X2) -> n__fst(X1, X2) 33.29/12.90 from(X) -> n__from(X) 33.29/12.90 add(X1, X2) -> n__add(X1, X2) 33.29/12.90 len(X) -> n__len(X) 33.29/12.90 activate(n__fst(X1, X2)) -> fst(X1, X2) 33.29/12.90 activate(n__from(X)) -> from(X) 33.29/12.90 activate(n__add(X1, X2)) -> add(X1, X2) 33.29/12.90 activate(n__len(X)) -> len(X) 33.29/12.90 activate(X) -> X 33.29/12.90 33.29/12.90 S is empty. 33.29/12.90 Rewrite Strategy: FULL 33.29/12.93 EOF