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