details

property	value
status	timeout (wallclock)
benchmark	graphcolour2Size_typed.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
space	Frederiksen_Others

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	301.00909996 seconds
cpu usage	1072.39133172
max memory	1.6110665728E10

stage attributes

unavailable

output

/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), ?) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). (0) CpxRelTRS (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 520 ms] (2) CpxRelTRS (3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CpxRelTRS (5) SlicingProof [LOWER BOUND(ID), 0 ms] (6) CpxRelTRS (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 10 ms] (8) typed CpxTrs (9) OrderProof [LOWER BOUND(ID), 0 ms] (10) typed CpxTrs (11) RewriteLemmaProof [LOWER BOUND(ID), 18.1 s] (12) BEST (13) proven lower bound (14) LowerBoundPropagationProof [FINISHED, 0 ms] (15) BOUNDS(n^1, INF) (16) typed CpxTrs (17) RewriteLemmaProof [LOWER BOUND(ID), 106 ms] (18) typed CpxTrs (19) RewriteLemmaProof [LOWER BOUND(ID), 444 ms] (20) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: colorof(node, Cons(CN(cl, N(name, adjs)), xs)) -> colorof[Ite][True][Ite](!EQ(name, node), node, Cons(CN(cl, N(name, adjs)), xs)) eqColorList(Cons(Yellow, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Yellow, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Yellow, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Blue, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(Blue, cs1), Cons(Red, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(NoColor, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Yellow, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Blue, cs2)) -> and(False, eqColorList(cs1, cs2)) eqColorList(Cons(Red, cs1), Cons(Red, cs2)) -> and(True, eqColorList(cs1, cs2)) eqColorList(Cons(NoColor, cs1), Cons(b, cs2)) -> and(False, eqColorList(cs1, cs2)) revapp(Cons(x, xs), rest) -> revapp(xs, Cons(x, rest)) revapp(Nil, rest) -> rest possible(color, Cons(x, xs), colorednodes) -> possible[Ite][True][Ite](eqColor(color, colorof(x, colorednodes)), color, Cons(x, xs), colorednodes) possible(color, Nil, colorednodes) -> True colorrest(cs, ncs, colorednodes, Cons(x, xs)) -> colorednoderest(cs, ncs, x, colorednodes, Cons(x, xs)) colorrest(cs, ncs, colorednodes, Nil) -> colorednodes colorof(node, Nil) -> NoColor colornode(Cons(x, xs), N(n, ns), colorednodes) -> colornode[Ite][True][Ite](possible(x, ns, colorednodes), Cons(x, xs), N(n, ns), colorednodes) colornode(Nil, node, colorednodes) -> NotPossible 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) colorednoderest(cs, Nil, node, colorednodes, rest) -> Nil graphcolour(Cons(x, xs), cs) -> reverse(colorrest(cs, cs, Cons(colornode(cs, x, Nil), Nil), xs)) eqColorList(Cons(c1, cs1), Nil) -> False eqColorList(Nil, Cons(c2, cs2)) -> False eqColorList(Nil, Nil) -> True eqColor(Yellow, NoColor) -> False eqColor(Yellow, Yellow) -> True eqColor(Yellow, Blue) -> False eqColor(Yellow, Red) -> False eqColor(Blue, NoColor) -> False eqColor(Blue, Yellow) -> False eqColor(Blue, Blue) -> True eqColor(Blue, Red) -> False eqColor(Red, NoColor) -> False eqColor(Red, Yellow) -> False eqColor(Red, Blue) -> False eqColor(Red, Red) -> True notEmpty(Cons(x, xs)) -> True notEmpty(Nil) -> False getNodeName(N(name, adjs)) -> name getNodeFromCN(CN(cl, n)) -> n getColorListFromCN(CN(cl, n)) -> cl getAdjs(N(n, ns)) -> ns eqColor(NoColor, b) -> False reverse(xs) -> revapp(xs, Nil) colorrestthetrick(cs1, cs, ncs, colorednodes, rest) -> colorrestthetrick[Ite](eqColorList(cs1, ncs), cs1, cs, ncs, colorednodes, rest) The (relative) TRS S consists of the following rules: and(False, False) -> False and(True, False) -> False popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to Runti Compl Inner Rewri 22807