/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), ?) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). (0) CpxRelTRS (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 247 ms] (2) CpxRelTRS (3) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (4) TRS for Loop Detection (5) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (6) BEST (7) proven lower bound (8) LowerBoundPropagationProof [FINISHED, 0 ms] (9) BOUNDS(n^1, INF) (10) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) revapp(Nil, rest) -> rest possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) possible(color, Nil, colorednodes) -> True colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorrest[Ite][True][Let](cs, ncs, colorednodes, Cons(x, xs), colornode(ncs, x, colorednodes)) colorrest(cs, ncs, colorednodes, Nil) -> colorednodes colorof(node, Nil) -> NoColor colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) colornode(Nil, node, colorednodes) -> NotPossible graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) eqColorList(Cons(c1, cs1), Nil) -> False eqColorList(Nil, Cons(c2, cs2)) -> False eqColorList(Nil, Nil) -> True eqColor(Yellow, NoColor) -> False eqColor(Yellow, Yellow) -> True eqColor(Yellow, Blue) -> False eqColor(Yellow, Red) -> False eqColor(Blue, NoColor) -> False eqColor(Blue, Yellow) -> False eqColor(Blue, Blue) -> True eqColor(Blue, Red) -> False eqColor(Red, NoColor) -> False eqColor(Red, Yellow) -> False eqColor(Red, Blue) -> False eqColor(Red, Red) -> True notEmpty(Cons(x, xs)) -> True notEmpty(Nil) -> False isPossible(CN(cl, n)) -> True isPossible(NotPossible) -> False getNodeName(N(name, adjs)) -> name getNodeFromCN(CN(cl, n)) -> n getColorListFromCN(CN(cl, n)) -> cl getAdjs(N(n, ns)) -> ns eqColor(NoColor, b) -> False reverse(xs) -> revapp(xs, Nil) colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) The (relative) TRS S consists of the following rules: and(False, False) -> False and(True, False) -> False and(False, True) -> False and(True, True) -> True !EQ(S(x), S(y)) -> !EQ(x, y) !EQ(0, S(y)) -> False !EQ(S(x), 0) -> False !EQ(0, 0) -> True colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, CN(cl, n)) -> colorrest[Ite][True][Let][Ite](True, cs, ncs, colorednodes, rest, CN(cl, n)) colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, NotPossible) -> colorrest[Ite][True][Let][Ite](False, cs, ncs, colorednodes, rest, NotPossible) possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, cs1, colorednodes, rest) colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) Rewrite Strategy: INNERMOST ---------------------------------------- (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved termination of relative rules ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) revapp(Nil, rest) -> rest possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) possible(color, Nil, colorednodes) -> True colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorrest[Ite][True][Let](cs, ncs, colorednodes, Cons(x, xs), colornode(ncs, x, colorednodes)) colorrest(cs, ncs, colorednodes, Nil) -> colorednodes colorof(node, Nil) -> NoColor colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) colornode(Nil, node, colorednodes) -> NotPossible graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) eqColorList(Cons(c1, cs1), Nil) -> False eqColorList(Nil, Cons(c2, cs2)) -> False eqColorList(Nil, Nil) -> True eqColor(Yellow, NoColor) -> False eqColor(Yellow, Yellow) -> True eqColor(Yellow, Blue) -> False eqColor(Yellow, Red) -> False eqColor(Blue, NoColor) -> False eqColor(Blue, Yellow) -> False eqColor(Blue, Blue) -> True eqColor(Blue, Red) -> False eqColor(Red, NoColor) -> False eqColor(Red, Yellow) -> False eqColor(Red, Blue) -> False eqColor(Red, Red) -> True notEmpty(Cons(x, xs)) -> True notEmpty(Nil) -> False isPossible(CN(cl, n)) -> True isPossible(NotPossible) -> False getNodeName(N(name, adjs)) -> name getNodeFromCN(CN(cl, n)) -> n getColorListFromCN(CN(cl, n)) -> cl getAdjs(N(n, ns)) -> ns eqColor(NoColor, b) -> False reverse(xs) -> revapp(xs, Nil) colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) The (relative) TRS S consists of the following rules: and(False, False) -> False and(True, False) -> False and(False, True) -> False and(True, True) -> True !EQ(S(x), S(y)) -> !EQ(x, y) !EQ(0, S(y)) -> False !EQ(S(x), 0) -> False !EQ(0, 0) -> True colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, CN(cl, n)) -> colorrest[Ite][True][Let][Ite](True, cs, ncs, colorednodes, rest, CN(cl, n)) colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, NotPossible) -> colorrest[Ite][True][Let][Ite](False, cs, ncs, colorednodes, rest, NotPossible) possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, cs1, colorednodes, rest) colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) Rewrite Strategy: INNERMOST ---------------------------------------- (3) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (4) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) revapp(Nil, rest) -> rest possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) possible(color, Nil, colorednodes) -> True colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorrest[Ite][True][Let](cs, ncs, colorednodes, Cons(x, xs), colornode(ncs, x, colorednodes)) colorrest(cs, ncs, colorednodes, Nil) -> colorednodes colorof(node, Nil) -> NoColor colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) colornode(Nil, node, colorednodes) -> NotPossible graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) eqColorList(Cons(c1, cs1), Nil) -> False eqColorList(Nil, Cons(c2, cs2)) -> False eqColorList(Nil, Nil) -> True eqColor(Yellow, NoColor) -> False eqColor(Yellow, Yellow) -> True eqColor(Yellow, Blue) -> False eqColor(Yellow, Red) -> False eqColor(Blue, NoColor) -> False eqColor(Blue, Yellow) -> False eqColor(Blue, Blue) -> True eqColor(Blue, Red) -> False eqColor(Red, NoColor) -> False eqColor(Red, Yellow) -> False eqColor(Red, Blue) -> False eqColor(Red, Red) -> True notEmpty(Cons(x, xs)) -> True notEmpty(Nil) -> False isPossible(CN(cl, n)) -> True isPossible(NotPossible) -> False getNodeName(N(name, adjs)) -> name getNodeFromCN(CN(cl, n)) -> n getColorListFromCN(CN(cl, n)) -> cl getAdjs(N(n, ns)) -> ns eqColor(NoColor, b) -> False reverse(xs) -> revapp(xs, Nil) colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) The (relative) TRS S consists of the following rules: and(False, False) -> False and(True, False) -> False and(False, True) -> False and(True, True) -> True !EQ(S(x), S(y)) -> !EQ(x, y) !EQ(0, S(y)) -> False !EQ(S(x), 0) -> False !EQ(0, 0) -> True colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, CN(cl, n)) -> colorrest[Ite][True][Let][Ite](True, cs, ncs, colorednodes, rest, CN(cl, n)) colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, NotPossible) -> colorrest[Ite][True][Let][Ite](False, cs, ncs, colorednodes, rest, NotPossible) possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, cs1, colorednodes, rest) colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) Rewrite Strategy: INNERMOST ---------------------------------------- (5) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) ->^+ and(True, eqColorList(cs1, cs2)) gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. The pumping substitution is [cs1 / Cons(Yellow, cs1), cs2 / Cons(Yellow, cs2)]. The result substitution is [ ]. ---------------------------------------- (6) Complex Obligation (BEST) ---------------------------------------- (7) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) revapp(Nil, rest) -> rest possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) possible(color, Nil, colorednodes) -> True colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorrest[Ite][True][Let](cs, ncs, colorednodes, Cons(x, xs), colornode(ncs, x, colorednodes)) colorrest(cs, ncs, colorednodes, Nil) -> colorednodes colorof(node, Nil) -> NoColor colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) colornode(Nil, node, colorednodes) -> NotPossible graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) eqColorList(Cons(c1, cs1), Nil) -> False eqColorList(Nil, Cons(c2, cs2)) -> False eqColorList(Nil, Nil) -> True eqColor(Yellow, NoColor) -> False eqColor(Yellow, Yellow) -> True eqColor(Yellow, Blue) -> False eqColor(Yellow, Red) -> False eqColor(Blue, NoColor) -> False eqColor(Blue, Yellow) -> False eqColor(Blue, Blue) -> True eqColor(Blue, Red) -> False eqColor(Red, NoColor) -> False eqColor(Red, Yellow) -> False eqColor(Red, Blue) -> False eqColor(Red, Red) -> True notEmpty(Cons(x, xs)) -> True notEmpty(Nil) -> False isPossible(CN(cl, n)) -> True isPossible(NotPossible) -> False getNodeName(N(name, adjs)) -> name getNodeFromCN(CN(cl, n)) -> n getColorListFromCN(CN(cl, n)) -> cl getAdjs(N(n, ns)) -> ns eqColor(NoColor, b) -> False reverse(xs) -> revapp(xs, Nil) colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) The (relative) TRS S consists of the following rules: and(False, False) -> False and(True, False) -> False and(False, True) -> False and(True, True) -> True !EQ(S(x), S(y)) -> !EQ(x, y) !EQ(0, S(y)) -> False !EQ(S(x), 0) -> False !EQ(0, 0) -> True colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, CN(cl, n)) -> colorrest[Ite][True][Let][Ite](True, cs, ncs, colorednodes, rest, CN(cl, n)) colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, NotPossible) -> colorrest[Ite][True][Let][Ite](False, cs, ncs, colorednodes, rest, NotPossible) possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, cs1, colorednodes, rest) colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) Rewrite Strategy: INNERMOST ---------------------------------------- (8) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (9) BOUNDS(n^1, INF) ---------------------------------------- (10) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) revapp(Nil, rest) -> rest possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) possible(color, Nil, colorednodes) -> True colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorrest[Ite][True][Let](cs, ncs, colorednodes, Cons(x, xs), colornode(ncs, x, colorednodes)) colorrest(cs, ncs, colorednodes, Nil) -> colorednodes colorof(node, Nil) -> NoColor colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) colornode(Nil, node, colorednodes) -> NotPossible graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) eqColorList(Cons(c1, cs1), Nil) -> False eqColorList(Nil, Cons(c2, cs2)) -> False eqColorList(Nil, Nil) -> True eqColor(Yellow, NoColor) -> False eqColor(Yellow, Yellow) -> True eqColor(Yellow, Blue) -> False eqColor(Yellow, Red) -> False eqColor(Blue, NoColor) -> False eqColor(Blue, Yellow) -> False eqColor(Blue, Blue) -> True eqColor(Blue, Red) -> False eqColor(Red, NoColor) -> False eqColor(Red, Yellow) -> False eqColor(Red, Blue) -> False eqColor(Red, Red) -> True notEmpty(Cons(x, xs)) -> True notEmpty(Nil) -> False isPossible(CN(cl, n)) -> True isPossible(NotPossible) -> False getNodeName(N(name, adjs)) -> name getNodeFromCN(CN(cl, n)) -> n getColorListFromCN(CN(cl, n)) -> cl getAdjs(N(n, ns)) -> ns eqColor(NoColor, b) -> False reverse(xs) -> revapp(xs, Nil) colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) The (relative) TRS S consists of the following rules: and(False, False) -> False and(True, False) -> False and(False, True) -> False and(True, True) -> True !EQ(S(x), S(y)) -> !EQ(x, y) !EQ(0, S(y)) -> False !EQ(S(x), 0) -> False !EQ(0, 0) -> True colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, CN(cl, n)) -> colorrest[Ite][True][Let][Ite](True, cs, ncs, colorednodes, rest, CN(cl, n)) colorrest[Ite][True][Let](cs, ncs, colorednodes, rest, NotPossible) -> colorrest[Ite][True][Let][Ite](False, cs, ncs, colorednodes, rest, NotPossible) possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, cs1, colorednodes, rest) colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) Rewrite Strategy: INNERMOST