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