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