1076.08/292.00 WORST_CASE(Omega(n^1), ?) 1076.08/292.02 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1076.08/292.02 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1076.08/292.02 1076.08/292.02 1076.08/292.02 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1076.08/292.02 1076.08/292.02 (0) CpxRelTRS 1076.08/292.02 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 613 ms] 1076.08/292.02 (2) CpxRelTRS 1076.08/292.02 (3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1076.08/292.02 (4) CpxRelTRS 1076.08/292.02 (5) SlicingProof [LOWER BOUND(ID), 15 ms] 1076.08/292.02 (6) CpxRelTRS 1076.08/292.02 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1076.08/292.02 (8) typed CpxTrs 1076.08/292.02 (9) OrderProof [LOWER BOUND(ID), 0 ms] 1076.08/292.02 (10) typed CpxTrs 1076.08/292.02 (11) RewriteLemmaProof [LOWER BOUND(ID), 20.2 s] 1076.08/292.02 (12) BEST 1076.08/292.02 (13) proven lower bound 1076.08/292.02 (14) LowerBoundPropagationProof [FINISHED, 0 ms] 1076.08/292.02 (15) BOUNDS(n^1, INF) 1076.08/292.02 (16) typed CpxTrs 1076.08/292.02 (17) RewriteLemmaProof [LOWER BOUND(ID), 94 ms] 1076.08/292.02 (18) typed CpxTrs 1076.08/292.02 (19) RewriteLemmaProof [LOWER BOUND(ID), 443 ms] 1076.08/292.02 (20) typed CpxTrs 1076.08/292.02 1076.08/292.02 1076.08/292.02 ---------------------------------------- 1076.08/292.02 1076.08/292.02 (0) 1076.08/292.02 Obligation: 1076.08/292.02 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1076.08/292.02 1076.08/292.02 1076.08/292.02 The TRS R consists of the following rules: 1076.08/292.02 1076.08/292.02 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.08/292.02 revapp(Nil, rest) -> rest 1076.08/292.02 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.08/292.02 possible(color, Nil, colorednodes) -> True 1076.08/292.02 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.08/292.02 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.08/292.02 colorof(node, Nil) -> NoColor 1076.08/292.02 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.08/292.02 colornode(Nil, node, colorednodes) -> NotPossible 1076.08/292.02 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.08/292.02 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.08/292.02 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.08/292.02 eqColorList(Cons(c1, cs1), Nil) -> False 1076.08/292.02 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.08/292.02 eqColorList(Nil, Nil) -> True 1076.08/292.02 eqColor(Yellow, NoColor) -> False 1076.08/292.02 eqColor(Yellow, Yellow) -> True 1076.08/292.02 eqColor(Yellow, Blue) -> False 1076.08/292.02 eqColor(Yellow, Red) -> False 1076.08/292.02 eqColor(Blue, NoColor) -> False 1076.08/292.02 eqColor(Blue, Yellow) -> False 1076.08/292.02 eqColor(Blue, Blue) -> True 1076.08/292.02 eqColor(Blue, Red) -> False 1076.08/292.02 eqColor(Red, NoColor) -> False 1076.08/292.02 eqColor(Red, Yellow) -> False 1076.08/292.02 eqColor(Red, Blue) -> False 1076.08/292.02 eqColor(Red, Red) -> True 1076.08/292.02 notEmpty(Cons(x, xs)) -> True 1076.08/292.02 notEmpty(Nil) -> False 1076.08/292.02 getNodeName(N(name, adjs)) -> name 1076.08/292.02 getNodeFromCN(CN(cl, n)) -> n 1076.08/292.02 getColorListFromCN(CN(cl, n)) -> cl 1076.08/292.02 getAdjs(N(n, ns)) -> ns 1076.08/292.02 eqColor(NoColor, b) -> False 1076.08/292.02 reverse(xs) -> revapp(xs, Nil) 1076.08/292.02 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.08/292.02 1076.08/292.02 The (relative) TRS S consists of the following rules: 1076.08/292.02 1076.08/292.02 and(False, False) -> False 1076.08/292.02 and(True, False) -> False 1076.08/292.02 and(False, True) -> False 1076.08/292.02 and(True, True) -> True 1076.08/292.02 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.08/292.02 !EQ(0, S(y)) -> False 1076.08/292.02 !EQ(S(x), 0) -> False 1076.08/292.02 !EQ(0, 0) -> True 1076.08/292.02 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.08/292.02 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.08/292.02 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.08/292.02 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.08/292.02 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.08/292.02 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.08/292.02 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](cs, ncs, node, colorednodes, Cons(x, xs), colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.08/292.02 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.08/292.02 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.08/292.02 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.08/292.02 1076.08/292.02 Rewrite Strategy: INNERMOST 1076.08/292.02 ---------------------------------------- 1076.08/292.02 1076.08/292.02 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 1076.08/292.02 proved termination of relative rules 1076.08/292.02 ---------------------------------------- 1076.08/292.02 1076.08/292.02 (2) 1076.08/292.02 Obligation: 1076.08/292.02 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1076.08/292.02 1076.08/292.02 1076.08/292.02 The TRS R consists of the following rules: 1076.08/292.02 1076.08/292.02 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.08/292.02 revapp(Nil, rest) -> rest 1076.08/292.02 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.08/292.02 possible(color, Nil, colorednodes) -> True 1076.08/292.02 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.08/292.02 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.08/292.02 colorof(node, Nil) -> NoColor 1076.08/292.02 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.08/292.02 colornode(Nil, node, colorednodes) -> NotPossible 1076.08/292.02 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.08/292.02 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.08/292.02 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.08/292.02 eqColorList(Cons(c1, cs1), Nil) -> False 1076.08/292.02 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.08/292.02 eqColorList(Nil, Nil) -> True 1076.08/292.02 eqColor(Yellow, NoColor) -> False 1076.08/292.02 eqColor(Yellow, Yellow) -> True 1076.08/292.02 eqColor(Yellow, Blue) -> False 1076.08/292.02 eqColor(Yellow, Red) -> False 1076.08/292.02 eqColor(Blue, NoColor) -> False 1076.08/292.02 eqColor(Blue, Yellow) -> False 1076.08/292.02 eqColor(Blue, Blue) -> True 1076.08/292.02 eqColor(Blue, Red) -> False 1076.08/292.02 eqColor(Red, NoColor) -> False 1076.08/292.02 eqColor(Red, Yellow) -> False 1076.08/292.02 eqColor(Red, Blue) -> False 1076.08/292.02 eqColor(Red, Red) -> True 1076.08/292.02 notEmpty(Cons(x, xs)) -> True 1076.08/292.02 notEmpty(Nil) -> False 1076.08/292.02 getNodeName(N(name, adjs)) -> name 1076.08/292.02 getNodeFromCN(CN(cl, n)) -> n 1076.08/292.02 getColorListFromCN(CN(cl, n)) -> cl 1076.08/292.02 getAdjs(N(n, ns)) -> ns 1076.08/292.02 eqColor(NoColor, b) -> False 1076.08/292.02 reverse(xs) -> revapp(xs, Nil) 1076.08/292.02 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.08/292.02 1076.08/292.02 The (relative) TRS S consists of the following rules: 1076.08/292.02 1076.08/292.02 and(False, False) -> False 1076.08/292.02 and(True, False) -> False 1076.08/292.02 and(False, True) -> False 1076.08/292.02 and(True, True) -> True 1076.08/292.02 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.08/292.02 !EQ(0, S(y)) -> False 1076.08/292.02 !EQ(S(x), 0) -> False 1076.08/292.02 !EQ(0, 0) -> True 1076.08/292.02 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.08/292.02 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.08/292.02 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.08/292.02 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.08/292.02 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.08/292.02 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.08/292.02 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](cs, ncs, node, colorednodes, Cons(x, xs), colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.08/292.02 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.08/292.02 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.08/292.02 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.08/292.02 1076.08/292.02 Rewrite Strategy: INNERMOST 1076.08/292.02 ---------------------------------------- 1076.08/292.02 1076.08/292.02 (3) RenamingProof (BOTH BOUNDS(ID, ID)) 1076.08/292.02 Renamed function symbols to avoid clashes with predefined symbol. 1076.08/292.02 ---------------------------------------- 1076.08/292.02 1076.08/292.02 (4) 1076.08/292.02 Obligation: 1076.08/292.02 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1076.08/292.02 1076.08/292.02 1076.08/292.02 The TRS R consists of the following rules: 1076.08/292.02 1076.08/292.02 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.08/292.02 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.08/292.02 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.08/292.02 revapp(Nil, rest) -> rest 1076.08/292.02 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.08/292.02 possible(color, Nil, colorednodes) -> True 1076.08/292.02 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.08/292.02 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.08/292.02 colorof(node, Nil) -> NoColor 1076.08/292.02 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.08/292.02 colornode(Nil, node, colorednodes) -> NotPossible 1076.08/292.02 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.08/292.02 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.08/292.02 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.08/292.02 eqColorList(Cons(c1, cs1), Nil) -> False 1076.08/292.02 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.08/292.02 eqColorList(Nil, Nil) -> True 1076.08/292.02 eqColor(Yellow, NoColor) -> False 1076.08/292.02 eqColor(Yellow, Yellow) -> True 1076.08/292.02 eqColor(Yellow, Blue) -> False 1076.08/292.02 eqColor(Yellow, Red) -> False 1076.08/292.02 eqColor(Blue, NoColor) -> False 1076.08/292.02 eqColor(Blue, Yellow) -> False 1076.08/292.02 eqColor(Blue, Blue) -> True 1076.08/292.02 eqColor(Blue, Red) -> False 1076.08/292.02 eqColor(Red, NoColor) -> False 1076.08/292.02 eqColor(Red, Yellow) -> False 1076.08/292.02 eqColor(Red, Blue) -> False 1076.08/292.02 eqColor(Red, Red) -> True 1076.08/292.02 notEmpty(Cons(x, xs)) -> True 1076.08/292.02 notEmpty(Nil) -> False 1076.08/292.02 getNodeName(N(name, adjs)) -> name 1076.08/292.02 getNodeFromCN(CN(cl, n)) -> n 1076.08/292.02 getColorListFromCN(CN(cl, n)) -> cl 1076.08/292.02 getAdjs(N(n, ns)) -> ns 1076.08/292.02 eqColor(NoColor, b) -> False 1076.08/292.02 reverse(xs) -> revapp(xs, Nil) 1076.08/292.02 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.08/292.02 1076.08/292.02 The (relative) TRS S consists of the following rules: 1076.08/292.02 1076.08/292.02 and(False, False) -> False 1076.08/292.02 and(True, False) -> False 1076.08/292.02 and(False, True) -> False 1076.08/292.02 and(True, True) -> True 1076.08/292.02 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.08/292.02 !EQ(0', S(y)) -> False 1076.08/292.02 !EQ(S(x), 0') -> False 1076.08/292.02 !EQ(0', 0') -> True 1076.08/292.02 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.08/292.02 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.08/292.02 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.08/292.02 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.08/292.02 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.08/292.02 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.08/292.02 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](cs, ncs, node, colorednodes, Cons(x, xs), colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.08/292.02 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.08/292.02 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.08/292.02 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.08/292.02 1076.08/292.02 Rewrite Strategy: INNERMOST 1076.08/292.02 ---------------------------------------- 1076.08/292.02 1076.08/292.02 (5) SlicingProof (LOWER BOUND(ID)) 1076.08/292.02 Sliced the following arguments: 1076.08/292.02 colorednoderest[Ite][True][Ite][True][Let]/0 1076.08/292.02 colorednoderest[Ite][True][Ite][True][Let]/1 1076.08/292.02 colorednoderest[Ite][True][Ite][True][Let]/2 1076.08/292.02 colorednoderest[Ite][True][Ite][True][Let]/3 1076.08/292.02 colorednoderest[Ite][True][Ite][True][Let]/4 1076.08/292.02 1076.08/292.02 ---------------------------------------- 1076.08/292.02 1076.08/292.02 (6) 1076.08/292.02 Obligation: 1076.08/292.02 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1076.08/292.02 1076.08/292.02 1076.08/292.02 The TRS R consists of the following rules: 1076.08/292.02 1076.08/292.02 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.08/292.02 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.16/292.02 revapp(Nil, rest) -> rest 1076.16/292.02 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.16/292.02 possible(color, Nil, colorednodes) -> True 1076.16/292.02 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.16/292.02 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.16/292.02 colorof(node, Nil) -> NoColor 1076.16/292.02 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.16/292.02 colornode(Nil, node, colorednodes) -> NotPossible 1076.16/292.02 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.16/292.02 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.16/292.02 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.16/292.02 eqColorList(Cons(c1, cs1), Nil) -> False 1076.16/292.02 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.16/292.02 eqColorList(Nil, Nil) -> True 1076.16/292.02 eqColor(Yellow, NoColor) -> False 1076.16/292.02 eqColor(Yellow, Yellow) -> True 1076.16/292.02 eqColor(Yellow, Blue) -> False 1076.16/292.02 eqColor(Yellow, Red) -> False 1076.16/292.02 eqColor(Blue, NoColor) -> False 1076.16/292.02 eqColor(Blue, Yellow) -> False 1076.16/292.02 eqColor(Blue, Blue) -> True 1076.16/292.02 eqColor(Blue, Red) -> False 1076.16/292.02 eqColor(Red, NoColor) -> False 1076.16/292.02 eqColor(Red, Yellow) -> False 1076.16/292.02 eqColor(Red, Blue) -> False 1076.16/292.02 eqColor(Red, Red) -> True 1076.16/292.02 notEmpty(Cons(x, xs)) -> True 1076.16/292.02 notEmpty(Nil) -> False 1076.16/292.02 getNodeName(N(name, adjs)) -> name 1076.16/292.02 getNodeFromCN(CN(cl, n)) -> n 1076.16/292.02 getColorListFromCN(CN(cl, n)) -> cl 1076.16/292.02 getAdjs(N(n, ns)) -> ns 1076.16/292.02 eqColor(NoColor, b) -> False 1076.16/292.02 reverse(xs) -> revapp(xs, Nil) 1076.16/292.02 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.16/292.02 1076.16/292.02 The (relative) TRS S consists of the following rules: 1076.16/292.02 1076.16/292.02 and(False, False) -> False 1076.16/292.02 and(True, False) -> False 1076.16/292.02 and(False, True) -> False 1076.16/292.02 and(True, True) -> True 1076.16/292.02 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.16/292.02 !EQ(0', S(y)) -> False 1076.16/292.02 !EQ(S(x), 0') -> False 1076.16/292.02 !EQ(0', 0') -> True 1076.16/292.02 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.16/292.02 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.16/292.02 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.16/292.02 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.16/292.02 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.16/292.02 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.16/292.02 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.16/292.02 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.16/292.02 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.16/292.02 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.16/292.02 1076.16/292.02 Rewrite Strategy: INNERMOST 1076.16/292.02 ---------------------------------------- 1076.16/292.02 1076.16/292.02 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1076.16/292.02 Infered types. 1076.16/292.02 ---------------------------------------- 1076.16/292.02 1076.16/292.02 (8) 1076.16/292.02 Obligation: 1076.16/292.02 Innermost TRS: 1076.16/292.02 Rules: 1076.16/292.02 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.16/292.02 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.02 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.02 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.16/292.02 revapp(Nil, rest) -> rest 1076.16/292.02 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.16/292.02 possible(color, Nil, colorednodes) -> True 1076.16/292.02 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.16/292.02 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.16/292.02 colorof(node, Nil) -> NoColor 1076.16/292.02 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.16/292.02 colornode(Nil, node, colorednodes) -> NotPossible 1076.16/292.02 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.16/292.02 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.16/292.02 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.16/292.02 eqColorList(Cons(c1, cs1), Nil) -> False 1076.16/292.02 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.16/292.02 eqColorList(Nil, Nil) -> True 1076.16/292.02 eqColor(Yellow, NoColor) -> False 1076.16/292.02 eqColor(Yellow, Yellow) -> True 1076.16/292.02 eqColor(Yellow, Blue) -> False 1076.16/292.02 eqColor(Yellow, Red) -> False 1076.16/292.02 eqColor(Blue, NoColor) -> False 1076.16/292.02 eqColor(Blue, Yellow) -> False 1076.16/292.02 eqColor(Blue, Blue) -> True 1076.16/292.02 eqColor(Blue, Red) -> False 1076.16/292.02 eqColor(Red, NoColor) -> False 1076.16/292.02 eqColor(Red, Yellow) -> False 1076.16/292.02 eqColor(Red, Blue) -> False 1076.16/292.02 eqColor(Red, Red) -> True 1076.16/292.02 notEmpty(Cons(x, xs)) -> True 1076.16/292.02 notEmpty(Nil) -> False 1076.16/292.02 getNodeName(N(name, adjs)) -> name 1076.16/292.02 getNodeFromCN(CN(cl, n)) -> n 1076.16/292.02 getColorListFromCN(CN(cl, n)) -> cl 1076.16/292.02 getAdjs(N(n, ns)) -> ns 1076.16/292.02 eqColor(NoColor, b) -> False 1076.16/292.02 reverse(xs) -> revapp(xs, Nil) 1076.16/292.02 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.16/292.02 and(False, False) -> False 1076.16/292.02 and(True, False) -> False 1076.16/292.02 and(False, True) -> False 1076.16/292.02 and(True, True) -> True 1076.16/292.02 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.16/292.02 !EQ(0', S(y)) -> False 1076.16/292.02 !EQ(S(x), 0') -> False 1076.16/292.02 !EQ(0', 0') -> True 1076.16/292.02 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.16/292.02 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.16/292.02 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.16/292.02 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.16/292.02 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.16/292.02 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.16/292.02 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.16/292.02 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.16/292.02 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.16/292.02 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.16/292.02 1076.16/292.02 Types: 1076.16/292.02 colorof :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 Cons :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.02 CN :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 N :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 colorof[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 !EQ :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.02 eqColorList :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.02 Yellow :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 NoColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 and :: False:True -> False:True -> False:True 1076.16/292.02 False :: False:True 1076.16/292.02 True :: False:True 1076.16/292.02 Blue :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 Red :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 revapp :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.02 Nil :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.02 possible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.02 possible[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.02 eqColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.02 colorrest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.02 colorednoderest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.02 colornode :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 colornode[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 NotPossible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 colorednoderest[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.02 graphcolour :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.02 reverse :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.02 notEmpty :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.02 getNodeName :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 getNodeFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.02 getColorListFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.02 getAdjs :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick[Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 S :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 0' :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite][True][Let] :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'1_0 :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 hole_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]2_0 :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_False:True3_0 :: False:True 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0 :: Nat -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0 :: Nat -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (9) OrderProof (LOWER BOUND(ID)) 1076.16/292.03 Heuristically decided to analyse the following defined symbols: 1076.16/292.03 colorof, !EQ, eqColorList, revapp, possible, colorrest, colorednoderest, colornode, colorrestthetrick 1076.16/292.03 1076.16/292.03 They will be analysed ascendingly in the following order: 1076.16/292.03 !EQ < colorof 1076.16/292.03 colorof < possible 1076.16/292.03 eqColorList < colorrestthetrick 1076.16/292.03 possible < colorednoderest 1076.16/292.03 possible < colornode 1076.16/292.03 colorrest = colorednoderest 1076.16/292.03 colorrest < colorrestthetrick 1076.16/292.03 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (10) 1076.16/292.03 Obligation: 1076.16/292.03 Innermost TRS: 1076.16/292.03 Rules: 1076.16/292.03 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.16/292.03 revapp(Nil, rest) -> rest 1076.16/292.03 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.16/292.03 possible(color, Nil, colorednodes) -> True 1076.16/292.03 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.16/292.03 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.16/292.03 colorof(node, Nil) -> NoColor 1076.16/292.03 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.16/292.03 colornode(Nil, node, colorednodes) -> NotPossible 1076.16/292.03 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.16/292.03 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.16/292.03 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.16/292.03 eqColorList(Cons(c1, cs1), Nil) -> False 1076.16/292.03 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.16/292.03 eqColorList(Nil, Nil) -> True 1076.16/292.03 eqColor(Yellow, NoColor) -> False 1076.16/292.03 eqColor(Yellow, Yellow) -> True 1076.16/292.03 eqColor(Yellow, Blue) -> False 1076.16/292.03 eqColor(Yellow, Red) -> False 1076.16/292.03 eqColor(Blue, NoColor) -> False 1076.16/292.03 eqColor(Blue, Yellow) -> False 1076.16/292.03 eqColor(Blue, Blue) -> True 1076.16/292.03 eqColor(Blue, Red) -> False 1076.16/292.03 eqColor(Red, NoColor) -> False 1076.16/292.03 eqColor(Red, Yellow) -> False 1076.16/292.03 eqColor(Red, Blue) -> False 1076.16/292.03 eqColor(Red, Red) -> True 1076.16/292.03 notEmpty(Cons(x, xs)) -> True 1076.16/292.03 notEmpty(Nil) -> False 1076.16/292.03 getNodeName(N(name, adjs)) -> name 1076.16/292.03 getNodeFromCN(CN(cl, n)) -> n 1076.16/292.03 getColorListFromCN(CN(cl, n)) -> cl 1076.16/292.03 getAdjs(N(n, ns)) -> ns 1076.16/292.03 eqColor(NoColor, b) -> False 1076.16/292.03 reverse(xs) -> revapp(xs, Nil) 1076.16/292.03 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.16/292.03 and(False, False) -> False 1076.16/292.03 and(True, False) -> False 1076.16/292.03 and(False, True) -> False 1076.16/292.03 and(True, True) -> True 1076.16/292.03 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.16/292.03 !EQ(0', S(y)) -> False 1076.16/292.03 !EQ(S(x), 0') -> False 1076.16/292.03 !EQ(0', 0') -> True 1076.16/292.03 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.16/292.03 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.16/292.03 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.16/292.03 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.16/292.03 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.16/292.03 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.16/292.03 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.16/292.03 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.16/292.03 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.16/292.03 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.16/292.03 1076.16/292.03 Types: 1076.16/292.03 colorof :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Cons :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 CN :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 N :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorof[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 !EQ :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 eqColorList :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 Yellow :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NoColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 and :: False:True -> False:True -> False:True 1076.16/292.03 False :: False:True 1076.16/292.03 True :: False:True 1076.16/292.03 Blue :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Red :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 revapp :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 Nil :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 possible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 possible[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 eqColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 colorrest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorednoderest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colornode :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colornode[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NotPossible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 graphcolour :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 reverse :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 notEmpty :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 getNodeName :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getNodeFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getColorListFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 getAdjs :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick[Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 S :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 0' :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite][True][Let] :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'1_0 :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 hole_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]2_0 :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_False:True3_0 :: False:True 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0 :: Nat -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0 :: Nat -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 1076.16/292.03 1076.16/292.03 Generator Equations: 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0) <=> Yellow 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(+(x, 1)) <=> CN(Nil, gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(x)) 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0) <=> Nil 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(x, 1)) <=> Cons(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(x)) 1076.16/292.03 1076.16/292.03 1076.16/292.03 The following defined symbols remain to be analysed: 1076.16/292.03 !EQ, colorof, eqColorList, revapp, possible, colorrest, colorednoderest, colornode, colorrestthetrick 1076.16/292.03 1076.16/292.03 They will be analysed ascendingly in the following order: 1076.16/292.03 !EQ < colorof 1076.16/292.03 colorof < possible 1076.16/292.03 eqColorList < colorrestthetrick 1076.16/292.03 possible < colorednoderest 1076.16/292.03 possible < colornode 1076.16/292.03 colorrest = colorednoderest 1076.16/292.03 colorrest < colorrestthetrick 1076.16/292.03 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (11) RewriteLemmaProof (LOWER BOUND(ID)) 1076.16/292.03 Proved the following rewrite lemma: 1076.16/292.03 eqColorList(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(1, n33_0)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n33_0)) -> False, rt in Omega(1 + n33_0) 1076.16/292.03 1076.16/292.03 Induction Base: 1076.16/292.03 eqColorList(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(1, 0)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0)) ->_R^Omega(1) 1076.16/292.03 False 1076.16/292.03 1076.16/292.03 Induction Step: 1076.16/292.03 eqColorList(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(1, +(n33_0, 1))), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(n33_0, 1))) ->_R^Omega(1) 1076.16/292.03 and(True, eqColorList(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(1, n33_0)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n33_0))) ->_IH 1076.16/292.03 and(True, False) ->_R^Omega(0) 1076.16/292.03 False 1076.16/292.03 1076.16/292.03 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (12) 1076.16/292.03 Complex Obligation (BEST) 1076.16/292.03 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (13) 1076.16/292.03 Obligation: 1076.16/292.03 Proved the lower bound n^1 for the following obligation: 1076.16/292.03 1076.16/292.03 Innermost TRS: 1076.16/292.03 Rules: 1076.16/292.03 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.16/292.03 revapp(Nil, rest) -> rest 1076.16/292.03 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.16/292.03 possible(color, Nil, colorednodes) -> True 1076.16/292.03 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.16/292.03 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.16/292.03 colorof(node, Nil) -> NoColor 1076.16/292.03 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.16/292.03 colornode(Nil, node, colorednodes) -> NotPossible 1076.16/292.03 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.16/292.03 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.16/292.03 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.16/292.03 eqColorList(Cons(c1, cs1), Nil) -> False 1076.16/292.03 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.16/292.03 eqColorList(Nil, Nil) -> True 1076.16/292.03 eqColor(Yellow, NoColor) -> False 1076.16/292.03 eqColor(Yellow, Yellow) -> True 1076.16/292.03 eqColor(Yellow, Blue) -> False 1076.16/292.03 eqColor(Yellow, Red) -> False 1076.16/292.03 eqColor(Blue, NoColor) -> False 1076.16/292.03 eqColor(Blue, Yellow) -> False 1076.16/292.03 eqColor(Blue, Blue) -> True 1076.16/292.03 eqColor(Blue, Red) -> False 1076.16/292.03 eqColor(Red, NoColor) -> False 1076.16/292.03 eqColor(Red, Yellow) -> False 1076.16/292.03 eqColor(Red, Blue) -> False 1076.16/292.03 eqColor(Red, Red) -> True 1076.16/292.03 notEmpty(Cons(x, xs)) -> True 1076.16/292.03 notEmpty(Nil) -> False 1076.16/292.03 getNodeName(N(name, adjs)) -> name 1076.16/292.03 getNodeFromCN(CN(cl, n)) -> n 1076.16/292.03 getColorListFromCN(CN(cl, n)) -> cl 1076.16/292.03 getAdjs(N(n, ns)) -> ns 1076.16/292.03 eqColor(NoColor, b) -> False 1076.16/292.03 reverse(xs) -> revapp(xs, Nil) 1076.16/292.03 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.16/292.03 and(False, False) -> False 1076.16/292.03 and(True, False) -> False 1076.16/292.03 and(False, True) -> False 1076.16/292.03 and(True, True) -> True 1076.16/292.03 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.16/292.03 !EQ(0', S(y)) -> False 1076.16/292.03 !EQ(S(x), 0') -> False 1076.16/292.03 !EQ(0', 0') -> True 1076.16/292.03 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.16/292.03 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.16/292.03 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.16/292.03 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.16/292.03 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.16/292.03 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.16/292.03 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.16/292.03 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.16/292.03 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.16/292.03 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.16/292.03 1076.16/292.03 Types: 1076.16/292.03 colorof :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Cons :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 CN :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 N :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorof[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 !EQ :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 eqColorList :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 Yellow :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NoColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 and :: False:True -> False:True -> False:True 1076.16/292.03 False :: False:True 1076.16/292.03 True :: False:True 1076.16/292.03 Blue :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Red :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 revapp :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 Nil :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 possible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 possible[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 eqColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 colorrest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorednoderest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colornode :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colornode[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NotPossible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 graphcolour :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 reverse :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 notEmpty :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 getNodeName :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getNodeFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getColorListFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 getAdjs :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick[Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 S :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 0' :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite][True][Let] :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'1_0 :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 hole_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]2_0 :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_False:True3_0 :: False:True 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0 :: Nat -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0 :: Nat -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 1076.16/292.03 1076.16/292.03 Generator Equations: 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0) <=> Yellow 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(+(x, 1)) <=> CN(Nil, gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(x)) 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0) <=> Nil 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(x, 1)) <=> Cons(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(x)) 1076.16/292.03 1076.16/292.03 1076.16/292.03 The following defined symbols remain to be analysed: 1076.16/292.03 eqColorList, revapp, possible, colorrest, colorednoderest, colornode, colorrestthetrick 1076.16/292.03 1076.16/292.03 They will be analysed ascendingly in the following order: 1076.16/292.03 eqColorList < colorrestthetrick 1076.16/292.03 possible < colorednoderest 1076.16/292.03 possible < colornode 1076.16/292.03 colorrest = colorednoderest 1076.16/292.03 colorrest < colorrestthetrick 1076.16/292.03 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (14) LowerBoundPropagationProof (FINISHED) 1076.16/292.03 Propagated lower bound. 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (15) 1076.16/292.03 BOUNDS(n^1, INF) 1076.16/292.03 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (16) 1076.16/292.03 Obligation: 1076.16/292.03 Innermost TRS: 1076.16/292.03 Rules: 1076.16/292.03 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.16/292.03 revapp(Nil, rest) -> rest 1076.16/292.03 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.16/292.03 possible(color, Nil, colorednodes) -> True 1076.16/292.03 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.16/292.03 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.16/292.03 colorof(node, Nil) -> NoColor 1076.16/292.03 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.16/292.03 colornode(Nil, node, colorednodes) -> NotPossible 1076.16/292.03 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.16/292.03 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.16/292.03 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.16/292.03 eqColorList(Cons(c1, cs1), Nil) -> False 1076.16/292.03 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.16/292.03 eqColorList(Nil, Nil) -> True 1076.16/292.03 eqColor(Yellow, NoColor) -> False 1076.16/292.03 eqColor(Yellow, Yellow) -> True 1076.16/292.03 eqColor(Yellow, Blue) -> False 1076.16/292.03 eqColor(Yellow, Red) -> False 1076.16/292.03 eqColor(Blue, NoColor) -> False 1076.16/292.03 eqColor(Blue, Yellow) -> False 1076.16/292.03 eqColor(Blue, Blue) -> True 1076.16/292.03 eqColor(Blue, Red) -> False 1076.16/292.03 eqColor(Red, NoColor) -> False 1076.16/292.03 eqColor(Red, Yellow) -> False 1076.16/292.03 eqColor(Red, Blue) -> False 1076.16/292.03 eqColor(Red, Red) -> True 1076.16/292.03 notEmpty(Cons(x, xs)) -> True 1076.16/292.03 notEmpty(Nil) -> False 1076.16/292.03 getNodeName(N(name, adjs)) -> name 1076.16/292.03 getNodeFromCN(CN(cl, n)) -> n 1076.16/292.03 getColorListFromCN(CN(cl, n)) -> cl 1076.16/292.03 getAdjs(N(n, ns)) -> ns 1076.16/292.03 eqColor(NoColor, b) -> False 1076.16/292.03 reverse(xs) -> revapp(xs, Nil) 1076.16/292.03 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.16/292.03 and(False, False) -> False 1076.16/292.03 and(True, False) -> False 1076.16/292.03 and(False, True) -> False 1076.16/292.03 and(True, True) -> True 1076.16/292.03 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.16/292.03 !EQ(0', S(y)) -> False 1076.16/292.03 !EQ(S(x), 0') -> False 1076.16/292.03 !EQ(0', 0') -> True 1076.16/292.03 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.16/292.03 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.16/292.03 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.16/292.03 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.16/292.03 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.16/292.03 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.16/292.03 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.16/292.03 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.16/292.03 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.16/292.03 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.16/292.03 1076.16/292.03 Types: 1076.16/292.03 colorof :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Cons :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 CN :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 N :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorof[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 !EQ :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 eqColorList :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 Yellow :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NoColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 and :: False:True -> False:True -> False:True 1076.16/292.03 False :: False:True 1076.16/292.03 True :: False:True 1076.16/292.03 Blue :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Red :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 revapp :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 Nil :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 possible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 possible[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 eqColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 colorrest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorednoderest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colornode :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colornode[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NotPossible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 graphcolour :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 reverse :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 notEmpty :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 getNodeName :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getNodeFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getColorListFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 getAdjs :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick[Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 S :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 0' :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite][True][Let] :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'1_0 :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 hole_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]2_0 :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_False:True3_0 :: False:True 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0 :: Nat -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0 :: Nat -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 1076.16/292.03 1076.16/292.03 Lemmas: 1076.16/292.03 eqColorList(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(1, n33_0)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n33_0)) -> False, rt in Omega(1 + n33_0) 1076.16/292.03 1076.16/292.03 1076.16/292.03 Generator Equations: 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0) <=> Yellow 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(+(x, 1)) <=> CN(Nil, gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(x)) 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0) <=> Nil 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(x, 1)) <=> Cons(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(x)) 1076.16/292.03 1076.16/292.03 1076.16/292.03 The following defined symbols remain to be analysed: 1076.16/292.03 revapp, possible, colorrest, colorednoderest, colornode, colorrestthetrick 1076.16/292.03 1076.16/292.03 They will be analysed ascendingly in the following order: 1076.16/292.03 possible < colorednoderest 1076.16/292.03 possible < colornode 1076.16/292.03 colorrest = colorednoderest 1076.16/292.03 colorrest < colorrestthetrick 1076.16/292.03 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1076.16/292.03 Proved the following rewrite lemma: 1076.16/292.03 revapp(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4056158_0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(b)) -> gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(n4056158_0, b)), rt in Omega(1 + n4056158_0) 1076.16/292.03 1076.16/292.03 Induction Base: 1076.16/292.03 revapp(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(b)) ->_R^Omega(1) 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(b) 1076.16/292.03 1076.16/292.03 Induction Step: 1076.16/292.03 revapp(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(n4056158_0, 1)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(b)) ->_R^Omega(1) 1076.16/292.03 revapp(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4056158_0), Cons(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(b))) ->_IH 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(+(b, 1), c4056159_0)) 1076.16/292.03 1076.16/292.03 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (18) 1076.16/292.03 Obligation: 1076.16/292.03 Innermost TRS: 1076.16/292.03 Rules: 1076.16/292.03 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.16/292.03 revapp(Nil, rest) -> rest 1076.16/292.03 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.16/292.03 possible(color, Nil, colorednodes) -> True 1076.16/292.03 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.16/292.03 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.16/292.03 colorof(node, Nil) -> NoColor 1076.16/292.03 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.16/292.03 colornode(Nil, node, colorednodes) -> NotPossible 1076.16/292.03 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.16/292.03 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.16/292.03 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.16/292.03 eqColorList(Cons(c1, cs1), Nil) -> False 1076.16/292.03 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.16/292.03 eqColorList(Nil, Nil) -> True 1076.16/292.03 eqColor(Yellow, NoColor) -> False 1076.16/292.03 eqColor(Yellow, Yellow) -> True 1076.16/292.03 eqColor(Yellow, Blue) -> False 1076.16/292.03 eqColor(Yellow, Red) -> False 1076.16/292.03 eqColor(Blue, NoColor) -> False 1076.16/292.03 eqColor(Blue, Yellow) -> False 1076.16/292.03 eqColor(Blue, Blue) -> True 1076.16/292.03 eqColor(Blue, Red) -> False 1076.16/292.03 eqColor(Red, NoColor) -> False 1076.16/292.03 eqColor(Red, Yellow) -> False 1076.16/292.03 eqColor(Red, Blue) -> False 1076.16/292.03 eqColor(Red, Red) -> True 1076.16/292.03 notEmpty(Cons(x, xs)) -> True 1076.16/292.03 notEmpty(Nil) -> False 1076.16/292.03 getNodeName(N(name, adjs)) -> name 1076.16/292.03 getNodeFromCN(CN(cl, n)) -> n 1076.16/292.03 getColorListFromCN(CN(cl, n)) -> cl 1076.16/292.03 getAdjs(N(n, ns)) -> ns 1076.16/292.03 eqColor(NoColor, b) -> False 1076.16/292.03 reverse(xs) -> revapp(xs, Nil) 1076.16/292.03 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.16/292.03 and(False, False) -> False 1076.16/292.03 and(True, False) -> False 1076.16/292.03 and(False, True) -> False 1076.16/292.03 and(True, True) -> True 1076.16/292.03 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.16/292.03 !EQ(0', S(y)) -> False 1076.16/292.03 !EQ(S(x), 0') -> False 1076.16/292.03 !EQ(0', 0') -> True 1076.16/292.03 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.16/292.03 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.16/292.03 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.16/292.03 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.16/292.03 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.16/292.03 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.16/292.03 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.16/292.03 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.16/292.03 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.16/292.03 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.16/292.03 1076.16/292.03 Types: 1076.16/292.03 colorof :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Cons :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 CN :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 N :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorof[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 !EQ :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 eqColorList :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 Yellow :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NoColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 and :: False:True -> False:True -> False:True 1076.16/292.03 False :: False:True 1076.16/292.03 True :: False:True 1076.16/292.03 Blue :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Red :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 revapp :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 Nil :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 possible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 possible[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 eqColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 colorrest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorednoderest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colornode :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colornode[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NotPossible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 graphcolour :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 reverse :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 notEmpty :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 getNodeName :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getNodeFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getColorListFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 getAdjs :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick[Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 S :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 0' :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite][True][Let] :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'1_0 :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 hole_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]2_0 :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_False:True3_0 :: False:True 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0 :: Nat -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0 :: Nat -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 1076.16/292.03 1076.16/292.03 Lemmas: 1076.16/292.03 eqColorList(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(1, n33_0)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n33_0)) -> False, rt in Omega(1 + n33_0) 1076.16/292.03 revapp(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4056158_0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(b)) -> gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(n4056158_0, b)), rt in Omega(1 + n4056158_0) 1076.16/292.03 1076.16/292.03 1076.16/292.03 Generator Equations: 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0) <=> Yellow 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(+(x, 1)) <=> CN(Nil, gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(x)) 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0) <=> Nil 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(x, 1)) <=> Cons(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(x)) 1076.16/292.03 1076.16/292.03 1076.16/292.03 The following defined symbols remain to be analysed: 1076.16/292.03 possible, colorrest, colorednoderest, colornode, colorrestthetrick 1076.16/292.03 1076.16/292.03 They will be analysed ascendingly in the following order: 1076.16/292.03 possible < colorednoderest 1076.16/292.03 possible < colornode 1076.16/292.03 colorrest = colorednoderest 1076.16/292.03 colorrest < colorrestthetrick 1076.16/292.03 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1076.16/292.03 Proved the following rewrite lemma: 1076.16/292.03 possible(gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4058116_0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0)) -> True, rt in Omega(1 + n4058116_0) 1076.16/292.03 1076.16/292.03 Induction Base: 1076.16/292.03 possible(gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0)) ->_R^Omega(1) 1076.16/292.03 True 1076.16/292.03 1076.16/292.03 Induction Step: 1076.16/292.03 possible(gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(n4058116_0, 1)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0)) ->_R^Omega(1) 1076.16/292.03 possible[Ite][True][Ite](eqColor(gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), colorof(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0))), gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), Cons(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4058116_0)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0)) ->_R^Omega(1) 1076.16/292.03 possible[Ite][True][Ite](eqColor(gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), NoColor), gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), Cons(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4058116_0)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0)) ->_R^Omega(1) 1076.16/292.03 possible[Ite][True][Ite](False, gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), Cons(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4058116_0)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0)) ->_R^Omega(0) 1076.16/292.03 possible(gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4058116_0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0)) ->_IH 1076.16/292.03 True 1076.16/292.03 1076.16/292.03 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1076.16/292.03 ---------------------------------------- 1076.16/292.03 1076.16/292.03 (20) 1076.16/292.03 Obligation: 1076.16/292.03 Innermost TRS: 1076.16/292.03 Rules: 1076.16/292.03 colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) 1076.16/292.03 eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) 1076.16/292.03 revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) 1076.16/292.03 revapp(Nil, rest) -> rest 1076.16/292.03 possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) 1076.16/292.03 possible(color, Nil, colorednodes) -> True 1076.16/292.03 colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) 1076.16/292.03 colorrest(cs, ncs, colorednodes, Nil) -> colorednodes 1076.16/292.03 colorof(node, Nil) -> NoColor 1076.16/292.03 colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) 1076.16/292.03 colornode(Nil, node, colorednodes) -> NotPossible 1076.16/292.03 colorednoderest(cs, Cons(x, xs), N(n, ns), colorednodes, rest) -> colorednoderest[Ite][True][Ite](possible(x, ns, colorednodes), cs, Cons(x, xs), N(n, ns), colorednodes, rest) 1076.16/292.03 colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil 1076.16/292.03 graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) 1076.16/292.03 eqColorList(Cons(c1, cs1), Nil) -> False 1076.16/292.03 eqColorList(Nil, Cons(c2, cs2)) -> False 1076.16/292.03 eqColorList(Nil, Nil) -> True 1076.16/292.03 eqColor(Yellow, NoColor) -> False 1076.16/292.03 eqColor(Yellow, Yellow) -> True 1076.16/292.03 eqColor(Yellow, Blue) -> False 1076.16/292.03 eqColor(Yellow, Red) -> False 1076.16/292.03 eqColor(Blue, NoColor) -> False 1076.16/292.03 eqColor(Blue, Yellow) -> False 1076.16/292.03 eqColor(Blue, Blue) -> True 1076.16/292.03 eqColor(Blue, Red) -> False 1076.16/292.03 eqColor(Red, NoColor) -> False 1076.16/292.03 eqColor(Red, Yellow) -> False 1076.16/292.03 eqColor(Red, Blue) -> False 1076.16/292.03 eqColor(Red, Red) -> True 1076.16/292.03 notEmpty(Cons(x, xs)) -> True 1076.16/292.03 notEmpty(Nil) -> False 1076.16/292.03 getNodeName(N(name, adjs)) -> name 1076.16/292.03 getNodeFromCN(CN(cl, n)) -> n 1076.16/292.03 getColorListFromCN(CN(cl, n)) -> cl 1076.16/292.03 getAdjs(N(n, ns)) -> ns 1076.16/292.03 eqColor(NoColor, b) -> False 1076.16/292.03 reverse(xs) -> revapp(xs, Nil) 1076.16/292.03 colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) 1076.16/292.03 and(False, False) -> False 1076.16/292.03 and(True, False) -> False 1076.16/292.03 and(False, True) -> False 1076.16/292.03 and(True, True) -> True 1076.16/292.03 !EQ(S(x), S(y)) -> !EQ(x, y) 1076.16/292.03 !EQ(0', S(y)) -> False 1076.16/292.03 !EQ(S(x), 0') -> False 1076.16/292.03 !EQ(0', 0') -> True 1076.16/292.03 colorof[Ite][True][Ite](True, node, Cons(CN(Cons(x, xs), n), xs')) -> x 1076.16/292.03 possible[Ite][True][Ite](False, color, Cons(x, xs), colorednodes) -> possible(color, xs, colorednodes) 1076.16/292.03 colorrestthetrick[Ite](False, Cons(x, xs), cs, ncs, colorednodes, rest) -> colorrestthetrick(xs, cs, ncs, colorednodes, rest) 1076.16/292.03 colorof[Ite][True][Ite](False, node, Cons(x, xs)) -> colorof(node, xs) 1076.16/292.03 colornode[Ite][True][Ite](False, Cons(x, xs), node, colorednodes) -> colornode(xs, node, colorednodes) 1076.16/292.03 colorednoderest[Ite][True][Ite](False, cs, Cons(x, xs), node, colorednodes, rest) -> colorednoderest(cs, xs, node, colorednodes, rest) 1076.16/292.03 colorednoderest[Ite][True][Ite](True, cs, ncs, node, colorednodes, Cons(x, xs)) -> colorednoderest[Ite][True][Ite][True][Let](colorrest(cs, cs, Cons(CN(ncs, node), colorednodes), xs)) 1076.16/292.03 possible[Ite][True][Ite](True, color, adjs, colorednodes) -> False 1076.16/292.03 colorrestthetrick[Ite](True, cs1, cs, ncs, colorednodes, rest) -> colorrest(cs, ncs, colorednodes, rest) 1076.16/292.03 colornode[Ite][True][Ite](True, cs, node, colorednodes) -> CN(cs, node) 1076.16/292.03 1076.16/292.03 Types: 1076.16/292.03 colorof :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Cons :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 CN :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 N :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorof[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 !EQ :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 eqColorList :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 Yellow :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NoColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 and :: False:True -> False:True -> False:True 1076.16/292.03 False :: False:True 1076.16/292.03 True :: False:True 1076.16/292.03 Blue :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 Red :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 revapp :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 Nil :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 possible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 possible[Ite][True][Ite] :: False:True -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 eqColor :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> False:True 1076.16/292.03 colorrest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorednoderest :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colornode :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colornode[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 NotPossible :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 graphcolour :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 reverse :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 notEmpty :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> False:True 1076.16/292.03 getNodeName :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getNodeFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 getColorListFromCN :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 getAdjs :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 colorrestthetrick[Ite] :: False:True -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 S :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 0' :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 colorednoderest[Ite][True][Ite][True][Let] :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'1_0 :: N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 hole_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]2_0 :: Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 hole_False:True3_0 :: False:True 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0 :: Nat -> N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0' 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0 :: Nat -> Cons:Nil:colorednoderest[Ite][True][Ite][True][Let] 1076.16/292.03 1076.16/292.03 1076.16/292.03 Lemmas: 1076.16/292.03 eqColorList(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(1, n33_0)), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n33_0)) -> False, rt in Omega(1 + n33_0) 1076.16/292.03 revapp(gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4056158_0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(b)) -> gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(n4056158_0, b)), rt in Omega(1 + n4056158_0) 1076.16/292.03 possible(gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(n4058116_0), gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0)) -> True, rt in Omega(1 + n4058116_0) 1076.16/292.03 1076.16/292.03 1076.16/292.03 Generator Equations: 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(0) <=> Yellow 1076.16/292.03 gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(+(x, 1)) <=> CN(Nil, gen_N:CN:Yellow:NoColor:Blue:Red:NotPossible:S:0'4_0(x)) 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(0) <=> Nil 1076.16/292.03 gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(+(x, 1)) <=> Cons(Yellow, gen_Cons:Nil:colorednoderest[Ite][True][Ite][True][Let]5_0(x)) 1076.16/292.03 1076.16/292.03 1076.16/292.03 The following defined symbols remain to be analysed: 1076.16/292.03 colornode, colorrest, colorednoderest, colorrestthetrick 1076.16/292.03 1076.16/292.03 They will be analysed ascendingly in the following order: 1076.16/292.03 colorrest = colorednoderest 1076.16/292.03 colorrest < colorrestthetrick 1076.30/292.13 EOF