English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
dependencies with alternatives
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-07-01 (04:25)
From: skaller <skaller@u...>
Subject: dependencies with alternatives
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