4.07/1.86 WORST_CASE(Omega(n^1), O(n^1)) 4.07/1.87 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.07/1.87 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.07/1.87 4.07/1.87 4.07/1.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.07/1.87 4.07/1.87 (0) CpxTRS 4.07/1.87 (1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 4.07/1.87 (2) CpxTRS 4.07/1.87 (3) CpxTrsMatchBoundsTAProof [FINISHED, 132 ms] 4.07/1.87 (4) BOUNDS(1, n^1) 4.07/1.87 (5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 4.07/1.87 (6) TRS for Loop Detection 4.07/1.87 (7) DecreasingLoopProof [LOWER BOUND(ID), 37 ms] 4.07/1.87 (8) BEST 4.07/1.87 (9) proven lower bound 4.07/1.87 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 4.07/1.87 (11) BOUNDS(n^1, INF) 4.07/1.87 (12) TRS for Loop Detection 4.07/1.87 4.07/1.87 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (0) 4.07/1.87 Obligation: 4.07/1.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.07/1.87 4.07/1.87 4.07/1.87 The TRS R consists of the following rules: 4.07/1.87 4.07/1.87 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 4.07/1.87 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 4.07/1.87 plus(N, 0) -> N 4.07/1.87 plus(N, s(M)) -> U11(tt, M, N) 4.07/1.87 activate(X) -> X 4.07/1.87 4.07/1.87 S is empty. 4.07/1.87 Rewrite Strategy: INNERMOST 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (1) RelTrsToTrsProof (UPPER BOUND(ID)) 4.07/1.87 transformed relative TRS to TRS 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (2) 4.07/1.87 Obligation: 4.07/1.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 4.07/1.87 4.07/1.87 4.07/1.87 The TRS R consists of the following rules: 4.07/1.87 4.07/1.87 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 4.07/1.87 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 4.07/1.87 plus(N, 0) -> N 4.07/1.87 plus(N, s(M)) -> U11(tt, M, N) 4.07/1.87 activate(X) -> X 4.07/1.87 4.07/1.87 S is empty. 4.07/1.87 Rewrite Strategy: INNERMOST 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (3) CpxTrsMatchBoundsTAProof (FINISHED) 4.07/1.87 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 3. 4.07/1.87 4.07/1.87 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 4.07/1.87 final states : [1, 2, 3, 4] 4.07/1.87 transitions: 4.07/1.87 tt0() -> 0 4.07/1.87 s0(0) -> 0 4.07/1.87 00() -> 0 4.07/1.87 U110(0, 0, 0) -> 1 4.07/1.87 U120(0, 0, 0) -> 2 4.07/1.87 plus0(0, 0) -> 3 4.07/1.87 activate0(0) -> 4 4.07/1.87 tt1() -> 5 4.07/1.87 activate1(0) -> 6 4.07/1.87 activate1(0) -> 7 4.07/1.87 U121(5, 6, 7) -> 1 4.07/1.87 activate1(0) -> 9 4.07/1.87 activate1(0) -> 10 4.07/1.87 plus1(9, 10) -> 8 4.07/1.87 s1(8) -> 2 4.07/1.87 tt1() -> 11 4.07/1.87 U111(11, 0, 0) -> 3 4.07/1.87 tt2() -> 12 4.07/1.87 activate2(0) -> 13 4.07/1.87 activate2(0) -> 14 4.07/1.87 U122(12, 13, 14) -> 3 4.07/1.87 activate2(7) -> 16 4.07/1.87 activate2(6) -> 17 4.07/1.87 plus2(16, 17) -> 15 4.07/1.87 s2(15) -> 1 4.07/1.87 U111(11, 0, 9) -> 8 4.07/1.87 activate3(14) -> 19 4.07/1.87 activate3(13) -> 20 4.07/1.87 plus3(19, 20) -> 18 4.07/1.87 s3(18) -> 3 4.07/1.87 activate2(9) -> 14 4.07/1.87 U122(12, 13, 14) -> 8 4.07/1.87 U111(11, 0, 16) -> 15 4.07/1.87 activate2(16) -> 14 4.07/1.87 U122(12, 13, 14) -> 15 4.07/1.87 s3(18) -> 8 4.07/1.87 U111(11, 0, 19) -> 18 4.07/1.87 activate2(19) -> 14 4.07/1.87 U122(12, 13, 14) -> 18 4.07/1.87 s3(18) -> 15 4.07/1.87 s3(18) -> 18 4.07/1.87 0 -> 3 4.07/1.87 0 -> 4 4.07/1.87 0 -> 6 4.07/1.87 0 -> 7 4.07/1.87 0 -> 9 4.07/1.87 0 -> 10 4.07/1.87 0 -> 13 4.07/1.87 0 -> 14 4.07/1.87 9 -> 8 4.07/1.87 9 -> 14 4.07/1.87 7 -> 16 4.07/1.87 6 -> 17 4.07/1.87 16 -> 15 4.07/1.87 16 -> 14 4.07/1.87 14 -> 19 4.07/1.87 13 -> 20 4.07/1.87 19 -> 18 4.07/1.87 19 -> 14 4.07/1.87 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (4) 4.07/1.87 BOUNDS(1, n^1) 4.07/1.87 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 4.07/1.87 Transformed a relative TRS into a decreasing-loop problem. 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (6) 4.07/1.87 Obligation: 4.07/1.87 Analyzing the following TRS for decreasing loops: 4.07/1.87 4.07/1.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.07/1.87 4.07/1.87 4.07/1.87 The TRS R consists of the following rules: 4.07/1.87 4.07/1.87 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 4.07/1.87 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 4.07/1.87 plus(N, 0) -> N 4.07/1.87 plus(N, s(M)) -> U11(tt, M, N) 4.07/1.87 activate(X) -> X 4.07/1.87 4.07/1.87 S is empty. 4.07/1.87 Rewrite Strategy: INNERMOST 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (7) DecreasingLoopProof (LOWER BOUND(ID)) 4.07/1.87 The following loop(s) give(s) rise to the lower bound Omega(n^1): 4.07/1.87 4.07/1.87 The rewrite sequence 4.07/1.87 4.07/1.87 U12(tt, s(M2_0), N) ->^+ s(U12(tt, M2_0, activate(N))) 4.07/1.87 4.07/1.87 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 4.07/1.87 4.07/1.87 The pumping substitution is [M2_0 / s(M2_0)]. 4.07/1.87 4.07/1.87 The result substitution is [N / activate(N)]. 4.07/1.87 4.07/1.87 4.07/1.87 4.07/1.87 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (8) 4.07/1.87 Complex Obligation (BEST) 4.07/1.87 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (9) 4.07/1.87 Obligation: 4.07/1.87 Proved the lower bound n^1 for the following obligation: 4.07/1.87 4.07/1.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.07/1.87 4.07/1.87 4.07/1.87 The TRS R consists of the following rules: 4.07/1.87 4.07/1.87 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 4.07/1.87 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 4.07/1.87 plus(N, 0) -> N 4.07/1.87 plus(N, s(M)) -> U11(tt, M, N) 4.07/1.87 activate(X) -> X 4.07/1.87 4.07/1.87 S is empty. 4.07/1.87 Rewrite Strategy: INNERMOST 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (10) LowerBoundPropagationProof (FINISHED) 4.07/1.87 Propagated lower bound. 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (11) 4.07/1.87 BOUNDS(n^1, INF) 4.07/1.87 4.07/1.87 ---------------------------------------- 4.07/1.87 4.07/1.87 (12) 4.07/1.87 Obligation: 4.07/1.87 Analyzing the following TRS for decreasing loops: 4.07/1.87 4.07/1.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.07/1.87 4.07/1.87 4.07/1.87 The TRS R consists of the following rules: 4.07/1.87 4.07/1.87 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 4.07/1.87 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 4.07/1.87 plus(N, 0) -> N 4.07/1.87 plus(N, s(M)) -> U11(tt, M, N) 4.07/1.87 activate(X) -> X 4.07/1.87 4.07/1.87 S is empty. 4.07/1.87 Rewrite Strategy: INNERMOST 4.07/1.89 EOF