Here you find some words on the subjects I am actually interested in:
-
Concurrent programs have in the general case a complex control structure although many formalisms
impose an acyclic control graph. We are interested in two related albeit distinct questions about
such computation DAGs: the number of its computation paths and the uniform random generation of such paths.
These questions are very difficult for general DAGs, and we thus study interesting sub-classes.
-
Write a random boolean expression on given sets of boolean variables and of connectors:
we obtain a boolean function. How random is this boolean function?
E.g., what is the probability that we obtain a tautology? A literal? Any specified function?
Is the probability of obtaining a given function related to the complexity of the function?
Does the Shannon effect, i.e. the fact that ``almost all'' functions have maximal complexity,
still hold for this probability distribution?
-
We are interested in two distinct types of structures: tree structures and their associated DAGs
induced by sharing all the identical subtrees. Two classical questions arise in this context.
Sample uniformly a large tree and compact it into a DAG: what is the typical size of the DAGs?
This question is our main interest in the context of binary tries.
Another approach deals directly with a class of compacted objects. Among all DAGs of the same size,
what are the typical measures (e.g. the in or out-degree distribution, the profile...).
What about the enumeration if we restrict to important subclasses of DAGs,
like binary decision diagrams (an efficient way of representing boolean functions in practice) ?
|
|