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

From 2024 until 2027, with some of my collaborators, we are supported by the ANR and the FWF in the context of Directed Acyclic Graphs Analysis. Please, visit the project websiteto get more details!