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) ?