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