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