4.15/1.85 WORST_CASE(Omega(n^1), O(n^1)) 4.15/1.85 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.15/1.85 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.15/1.85 4.15/1.85 4.15/1.85 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.15/1.85 4.15/1.85 (0) CpxTRS 4.15/1.85 (1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 4.15/1.85 (2) CpxTRS 4.15/1.85 (3) CpxTrsMatchBoundsTAProof [FINISHED, 82 ms] 4.15/1.85 (4) BOUNDS(1, n^1) 4.15/1.85 (5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 4.15/1.85 (6) TRS for Loop Detection 4.15/1.85 (7) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 4.15/1.85 (8) BEST 4.15/1.85 (9) proven lower bound 4.15/1.85 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 4.15/1.85 (11) BOUNDS(n^1, INF) 4.15/1.85 (12) TRS for Loop Detection 4.15/1.85 4.15/1.85 4.15/1.85 ---------------------------------------- 4.15/1.85 4.15/1.85 (0) 4.15/1.85 Obligation: 4.15/1.85 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.15/1.85 4.15/1.85 4.15/1.85 The TRS R consists of the following rules: 4.15/1.85 4.15/1.85 f(a, a) -> f(a, b) 4.15/1.85 f(a, b) -> f(s(a), c) 4.15/1.85 f(s(X), c) -> f(X, c) 4.15/1.85 f(c, c) -> f(a, a) 4.15/1.85 4.15/1.85 S is empty. 4.15/1.85 Rewrite Strategy: INNERMOST 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (1) RelTrsToTrsProof (UPPER BOUND(ID)) 4.15/1.86 transformed relative TRS to TRS 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (2) 4.15/1.86 Obligation: 4.15/1.86 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 4.15/1.86 4.15/1.86 4.15/1.86 The TRS R consists of the following rules: 4.15/1.86 4.15/1.86 f(a, a) -> f(a, b) 4.15/1.86 f(a, b) -> f(s(a), c) 4.15/1.86 f(s(X), c) -> f(X, c) 4.15/1.86 f(c, c) -> f(a, a) 4.15/1.86 4.15/1.86 S is empty. 4.15/1.86 Rewrite Strategy: INNERMOST 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (3) CpxTrsMatchBoundsTAProof (FINISHED) 4.15/1.86 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 4. 4.15/1.86 4.15/1.86 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 4.15/1.86 final states : [1] 4.15/1.86 transitions: 4.15/1.86 a0() -> 0 4.15/1.86 b0() -> 0 4.15/1.86 s0(0) -> 0 4.15/1.86 c0() -> 0 4.15/1.86 f0(0, 0) -> 1 4.15/1.86 a1() -> 2 4.15/1.86 b1() -> 3 4.15/1.86 f1(2, 3) -> 1 4.15/1.86 a1() -> 5 4.15/1.86 s1(5) -> 4 4.15/1.86 c1() -> 6 4.15/1.86 f1(4, 6) -> 1 4.15/1.86 f1(0, 6) -> 1 4.15/1.86 a1() -> 7 4.15/1.86 f1(2, 7) -> 1 4.15/1.86 a2() -> 8 4.15/1.86 b2() -> 9 4.15/1.86 f2(8, 9) -> 1 4.15/1.86 a2() -> 11 4.15/1.86 s2(11) -> 10 4.15/1.86 c2() -> 12 4.15/1.86 f2(10, 12) -> 1 4.15/1.86 f2(5, 12) -> 1 4.15/1.86 a3() -> 14 4.15/1.86 s3(14) -> 13 4.15/1.86 c3() -> 15 4.15/1.86 f3(13, 15) -> 1 4.15/1.86 f3(11, 15) -> 1 4.15/1.86 c4() -> 16 4.15/1.86 f4(14, 16) -> 1 4.15/1.86 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (4) 4.15/1.86 BOUNDS(1, n^1) 4.15/1.86 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 4.15/1.86 Transformed a relative TRS into a decreasing-loop problem. 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (6) 4.15/1.86 Obligation: 4.15/1.86 Analyzing the following TRS for decreasing loops: 4.15/1.86 4.15/1.86 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.15/1.86 4.15/1.86 4.15/1.86 The TRS R consists of the following rules: 4.15/1.86 4.15/1.86 f(a, a) -> f(a, b) 4.15/1.86 f(a, b) -> f(s(a), c) 4.15/1.86 f(s(X), c) -> f(X, c) 4.15/1.86 f(c, c) -> f(a, a) 4.15/1.86 4.15/1.86 S is empty. 4.15/1.86 Rewrite Strategy: INNERMOST 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (7) DecreasingLoopProof (LOWER BOUND(ID)) 4.15/1.86 The following loop(s) give(s) rise to the lower bound Omega(n^1): 4.15/1.86 4.15/1.86 The rewrite sequence 4.15/1.86 4.15/1.86 f(s(X), c) ->^+ f(X, c) 4.15/1.86 4.15/1.86 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 4.15/1.86 4.15/1.86 The pumping substitution is [X / s(X)]. 4.15/1.86 4.15/1.86 The result substitution is [ ]. 4.15/1.86 4.15/1.86 4.15/1.86 4.15/1.86 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (8) 4.15/1.86 Complex Obligation (BEST) 4.15/1.86 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (9) 4.15/1.86 Obligation: 4.15/1.86 Proved the lower bound n^1 for the following obligation: 4.15/1.86 4.15/1.86 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.15/1.86 4.15/1.86 4.15/1.86 The TRS R consists of the following rules: 4.15/1.86 4.15/1.86 f(a, a) -> f(a, b) 4.15/1.86 f(a, b) -> f(s(a), c) 4.15/1.86 f(s(X), c) -> f(X, c) 4.15/1.86 f(c, c) -> f(a, a) 4.15/1.86 4.15/1.86 S is empty. 4.15/1.86 Rewrite Strategy: INNERMOST 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (10) LowerBoundPropagationProof (FINISHED) 4.15/1.86 Propagated lower bound. 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (11) 4.15/1.86 BOUNDS(n^1, INF) 4.15/1.86 4.15/1.86 ---------------------------------------- 4.15/1.86 4.15/1.86 (12) 4.15/1.86 Obligation: 4.15/1.86 Analyzing the following TRS for decreasing loops: 4.15/1.86 4.15/1.86 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.15/1.86 4.15/1.86 4.15/1.86 The TRS R consists of the following rules: 4.15/1.86 4.15/1.86 f(a, a) -> f(a, b) 4.15/1.86 f(a, b) -> f(s(a), c) 4.15/1.86 f(s(X), c) -> f(X, c) 4.15/1.86 f(c, c) -> f(a, a) 4.15/1.86 4.15/1.86 S is empty. 4.15/1.86 Rewrite Strategy: INNERMOST 4.24/2.06 EOF