* dependencies with alternatives
@ 2006-07-01 4:25 skaller
0 siblings, 0 replies; only message in thread
From: skaller @ 2006-07-01 4:25 UTC (permalink / raw)
To: caml-list
More a math than ocaml question but .. we know with a dependency graph
we can find the transitive closure of a set of nodes.
This set represents the conjunction of initial requirements:
"this package requires package A, package B, AND package C".
What happens if a new constructor for alternatives is introduced?
Assume first inclusive or (introducing exclusive or seems equivalent
to introducing negation, i.e. conflicts).
As far as I can see this problem doesn't have a unique solution,
we're looking for a minimal set of nodes such that at least
one alternative of each (reachable) alternation is reachable
from the root. It's looking remarkably like an Earley style
algorithm is actually needed to compute such a minimal set.
If conflicts are introduced, it seems even harder.
The model for this thing is no longer a graph, rather at least
a graph labelled with the constructor (all-of, one-of) is required.
Any hints on this?
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2006-07-01 4:25 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-07-01 4:25 dependencies with alternatives skaller
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).