 |
Discrete Mathematics & Theoretical Computer Science |
vol. 22 no. 3, Computational Logic and Applications (CLA'19)
1. Unary profile of lambda terms with restricted De Bruijn indices
In this paper we present an average-case analysis of closed lambda terms with restricted values of De Bruijn indices in the model where each occurrence of a variable contributes one to the size. Given a fixed integer k, a lambda term in which all De Bruijn indices are bounded by k has the following shape: It starts with k De Bruijn levels, forming the so-called hat of the term, to which some number of k-colored Motzkin trees are attached. By means of analytic combinatorics, we show that the size of this hat is constant on average and that the average number of De Bruijn levels of k-colored Motzkin trees of size n is asymptotically Θ(√ n). Combining these two facts, we conclude that the maximal non-empty De Bruijn level in a lambda term with restrictions on De Bruijn indices and of size n is, on average, also of order √ n. On this basis, we provide the average unary profile of such lambda terms.
Section:
Special issues
2. Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency
In this paper we address the problem of understanding Concurrency Theory from a combinatorial point of view. We are interested in quantitative results and algorithmic tools to refine our understanding of the classical combinatorial explosion phenomenon arising in concurrency. This paper is essentially focusing on the the notion of synchronization from the point of view of combinatorics. As a first step, we address the quantitative problem of counting the number of executions of simple processes interacting with synchronization barriers. We elaborate a systematic decomposition of processes that produces a symbolic integral formula to solve the problem. Based on this procedure, we develop a generic algorithm to generate process executions uniformly at random. For some interesting sub-classes of processes we propose very efficient counting and random sampling algorithms. All these algorithms have one important characteristic in common: they work on the control graph of processes and thus do not require the explicit construction of the state-space.
Section:
Special issues