1137.77/291.62 WORST_CASE(Omega(n^1), ?) 1137.97/291.69 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1137.97/291.69 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1137.97/291.69 1137.97/291.69 1137.97/291.69 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1137.97/291.69 1137.97/291.69 (0) CpxTRS 1137.97/291.69 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1137.97/291.69 (2) TRS for Loop Detection 1137.97/291.69 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1137.97/291.69 (4) BEST 1137.97/291.69 (5) proven lower bound 1137.97/291.69 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 1137.97/291.69 (7) BOUNDS(n^1, INF) 1137.97/291.69 (8) TRS for Loop Detection 1137.97/291.69 1137.97/291.69 1137.97/291.69 ---------------------------------------- 1137.97/291.69 1137.97/291.69 (0) 1137.97/291.69 Obligation: 1137.97/291.69 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1137.97/291.69 1137.97/291.69 1137.97/291.69 The TRS R consists of the following rules: 1137.97/291.69 1137.97/291.69 eq(0, 0) -> true 1137.97/291.69 eq(0, s(x)) -> false 1137.97/291.69 eq(s(x), 0) -> false 1137.97/291.69 eq(s(x), s(y)) -> eq(x, y) 1137.97/291.69 or(true, y) -> true 1137.97/291.69 or(false, y) -> y 1137.97/291.69 and(true, y) -> y 1137.97/291.69 and(false, y) -> false 1137.97/291.69 size(empty) -> 0 1137.97/291.69 size(edge(x, y, i)) -> s(size(i)) 1137.97/291.69 le(0, y) -> true 1137.97/291.69 le(s(x), 0) -> false 1137.97/291.69 le(s(x), s(y)) -> le(x, y) 1137.97/291.69 reachable(x, y, i) -> reach(x, y, 0, i, i) 1137.97/291.69 reach(x, y, c, i, j) -> if1(eq(x, y), x, y, c, i, j) 1137.97/291.69 if1(true, x, y, c, i, j) -> true 1137.97/291.69 if1(false, x, y, c, i, j) -> if2(le(c, size(j)), x, y, c, i, j) 1137.97/291.69 if2(false, x, y, c, i, j) -> false 1137.97/291.69 if2(true, x, y, c, empty, j) -> false 1137.97/291.69 if2(true, x, y, c, edge(u, v, i), j) -> or(if2(true, x, y, c, i, j), and(eq(x, u), reach(v, y, s(c), j, j))) 1137.97/291.69 1137.97/291.69 S is empty. 1137.97/291.69 Rewrite Strategy: FULL 1137.97/291.69 ---------------------------------------- 1137.97/291.69 1137.97/291.69 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1137.97/291.69 Transformed a relative TRS into a decreasing-loop problem. 1137.97/291.69 ---------------------------------------- 1137.97/291.69 1137.97/291.69 (2) 1137.97/291.69 Obligation: 1137.97/291.69 Analyzing the following TRS for decreasing loops: 1137.97/291.69 1137.97/291.69 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1137.97/291.69 1137.97/291.69 1137.97/291.69 The TRS R consists of the following rules: 1137.97/291.69 1137.97/291.69 eq(0, 0) -> true 1137.97/291.69 eq(0, s(x)) -> false 1137.97/291.69 eq(s(x), 0) -> false 1137.97/291.69 eq(s(x), s(y)) -> eq(x, y) 1137.97/291.69 or(true, y) -> true 1137.97/291.69 or(false, y) -> y 1137.97/291.69 and(true, y) -> y 1137.97/291.69 and(false, y) -> false 1137.97/291.69 size(empty) -> 0 1137.97/291.69 size(edge(x, y, i)) -> s(size(i)) 1137.97/291.69 le(0, y) -> true 1137.97/291.69 le(s(x), 0) -> false 1137.97/291.69 le(s(x), s(y)) -> le(x, y) 1137.97/291.69 reachable(x, y, i) -> reach(x, y, 0, i, i) 1137.97/291.69 reach(x, y, c, i, j) -> if1(eq(x, y), x, y, c, i, j) 1137.97/291.69 if1(true, x, y, c, i, j) -> true 1137.97/291.69 if1(false, x, y, c, i, j) -> if2(le(c, size(j)), x, y, c, i, j) 1137.97/291.69 if2(false, x, y, c, i, j) -> false 1137.97/291.69 if2(true, x, y, c, empty, j) -> false 1137.97/291.69 if2(true, x, y, c, edge(u, v, i), j) -> or(if2(true, x, y, c, i, j), and(eq(x, u), reach(v, y, s(c), j, j))) 1137.97/291.69 1137.97/291.69 S is empty. 1137.97/291.69 Rewrite Strategy: FULL 1137.97/291.69 ---------------------------------------- 1137.97/291.69 1137.97/291.69 (3) DecreasingLoopProof (LOWER BOUND(ID)) 1137.97/291.69 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1137.97/291.69 1137.97/291.69 The rewrite sequence 1137.97/291.69 1137.97/291.69 if2(true, x, y, c, edge(u, v, i), j) ->^+ or(if2(true, x, y, c, i, j), and(eq(x, u), reach(v, y, s(c), j, j))) 1137.97/291.69 1137.97/291.69 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 1137.97/291.69 1137.97/291.69 The pumping substitution is [i / edge(u, v, i)]. 1137.97/291.69 1137.97/291.69 The result substitution is [ ]. 1137.97/291.69 1137.97/291.69 1137.97/291.69 1137.97/291.69 1137.97/291.69 ---------------------------------------- 1137.97/291.69 1137.97/291.69 (4) 1137.97/291.69 Complex Obligation (BEST) 1137.97/291.69 1137.97/291.69 ---------------------------------------- 1137.97/291.69 1137.97/291.69 (5) 1137.97/291.69 Obligation: 1137.97/291.69 Proved the lower bound n^1 for the following obligation: 1137.97/291.69 1137.97/291.69 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1137.97/291.69 1137.97/291.69 1137.97/291.69 The TRS R consists of the following rules: 1137.97/291.69 1137.97/291.69 eq(0, 0) -> true 1137.97/291.69 eq(0, s(x)) -> false 1137.97/291.69 eq(s(x), 0) -> false 1137.97/291.69 eq(s(x), s(y)) -> eq(x, y) 1137.97/291.69 or(true, y) -> true 1137.97/291.69 or(false, y) -> y 1137.97/291.69 and(true, y) -> y 1137.97/291.69 and(false, y) -> false 1137.97/291.69 size(empty) -> 0 1137.97/291.69 size(edge(x, y, i)) -> s(size(i)) 1137.97/291.69 le(0, y) -> true 1137.97/291.69 le(s(x), 0) -> false 1137.97/291.69 le(s(x), s(y)) -> le(x, y) 1137.97/291.69 reachable(x, y, i) -> reach(x, y, 0, i, i) 1137.97/291.69 reach(x, y, c, i, j) -> if1(eq(x, y), x, y, c, i, j) 1137.97/291.69 if1(true, x, y, c, i, j) -> true 1137.97/291.69 if1(false, x, y, c, i, j) -> if2(le(c, size(j)), x, y, c, i, j) 1137.97/291.69 if2(false, x, y, c, i, j) -> false 1137.97/291.69 if2(true, x, y, c, empty, j) -> false 1137.97/291.69 if2(true, x, y, c, edge(u, v, i), j) -> or(if2(true, x, y, c, i, j), and(eq(x, u), reach(v, y, s(c), j, j))) 1137.97/291.69 1137.97/291.69 S is empty. 1137.97/291.69 Rewrite Strategy: FULL 1137.97/291.69 ---------------------------------------- 1137.97/291.69 1137.97/291.69 (6) LowerBoundPropagationProof (FINISHED) 1137.97/291.69 Propagated lower bound. 1137.97/291.69 ---------------------------------------- 1137.97/291.69 1137.97/291.69 (7) 1137.97/291.69 BOUNDS(n^1, INF) 1137.97/291.69 1137.97/291.69 ---------------------------------------- 1137.97/291.69 1137.97/291.69 (8) 1137.97/291.69 Obligation: 1137.97/291.69 Analyzing the following TRS for decreasing loops: 1137.97/291.69 1137.97/291.69 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1137.97/291.69 1137.97/291.69 1137.97/291.69 The TRS R consists of the following rules: 1137.97/291.69 1137.97/291.69 eq(0, 0) -> true 1137.97/291.69 eq(0, s(x)) -> false 1137.97/291.69 eq(s(x), 0) -> false 1137.97/291.69 eq(s(x), s(y)) -> eq(x, y) 1137.97/291.69 or(true, y) -> true 1137.97/291.69 or(false, y) -> y 1137.97/291.69 and(true, y) -> y 1137.97/291.69 and(false, y) -> false 1137.97/291.69 size(empty) -> 0 1137.97/291.69 size(edge(x, y, i)) -> s(size(i)) 1137.97/291.69 le(0, y) -> true 1137.97/291.69 le(s(x), 0) -> false 1137.97/291.69 le(s(x), s(y)) -> le(x, y) 1137.97/291.69 reachable(x, y, i) -> reach(x, y, 0, i, i) 1137.97/291.69 reach(x, y, c, i, j) -> if1(eq(x, y), x, y, c, i, j) 1137.97/291.69 if1(true, x, y, c, i, j) -> true 1137.97/291.69 if1(false, x, y, c, i, j) -> if2(le(c, size(j)), x, y, c, i, j) 1137.97/291.69 if2(false, x, y, c, i, j) -> false 1137.97/291.69 if2(true, x, y, c, empty, j) -> false 1137.97/291.69 if2(true, x, y, c, edge(u, v, i), j) -> or(if2(true, x, y, c, i, j), and(eq(x, u), reach(v, y, s(c), j, j))) 1137.97/291.69 1137.97/291.69 S is empty. 1137.97/291.69 Rewrite Strategy: FULL 1138.18/291.77 EOF