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