We continue developing the information theory of structured data. In this article, we study models generating d -ary trees ( d ≥ 2) and trees with unrestricted degree. We first compute the entropy which gives us the fundamental lower bound on compression of such trees. Then we present efficient compression algorithms based on arithmetic encoding that achieve the entropy within a constant number of bits. A naïve implementation of these algorithms has a prohibitive time complexity of O ( n d ) elementary arithmetic operations (each corresponding to a number f ( n , d ) of bit operations), but our efficient algorithms run in O ( n 2 ) of these operations, where n is the number of nodes. It turns out that extending source coding (i.e., compression) from sequences to advanced data structures such as degree-unconstrained trees is mathematically quite challenging and leads to recurrences that find ample applications in the information theory of general structures (e.g., to analyze the information content of degree-unconstrained non-plane trees).

Recently, the need for efficient representations of data conveyed by graphical structures has emerged in many different contexts. While compressing such data one must consider two types of information. The first type is the information carried by the labels embedded in the structure. The second type is the information conveyed by the structure itself. In this extended abstract we address the latter type, namely we study the information carried by the structure of Uniform Random Intersection Graphs (URIGs). Random Intersection Graphs emerge in many scenarios, e.g., they correspond to the topology of many social networks and secure wireless networks, and they are induced in the clusterization process. We analyze algebraic properties of an automorphism group of the underlying structure of URIGs and derive a precise asymptotic formula for their structural entropy for various values of model parameters.

We continue developing the information theory of advanced data structures. In our previous work, we introduced structural entropy of unlabeled graphs and designed lossless compression algorithms for binary trees (with structure-correlated vertex names). In this paper, we consider d-ary trees (d ≥ 2) and trees with unrestricted degree for which we compute the entropy (the first step to design optimal compression algorithms). It turns out that extending from binary trees to general trees is mathematically quite challenging and leads to new recurrences that find ample applications in the information theory of structures.

John Tromp introduced the so-called 'binary lambda calculus' as a way to encode lambda terms in terms of binary words. Later, Grygiel and Lescanne conjectured that the number of binary lambda terms with $m$ free indices and of size $n$ (encoded as binary words of length $n$) is $o(n^{-3/2} τ^{-n})$ for $τ\approx 1.963448\ldots$. We generalize the proposed notion of size and show that for several classes of lambda terms, including binary lambda terms with $m$ free indices, the number of terms of size $n$ is $Θ(n^{-3/2} ρ^{-n})$ with some class dependent constant $ρ$, which in particular disproves the above mentioned conjecture. A way to obtain lower and upper bounds for the constant near the leading term is presented and numerical results for a few previously introduced classes of lambda terms are given.

We consider access scheduling to a shared radio channel in networks where a set of stations tries to get exclusive rights to transmit over a shared radio channel. A frequent strategy to solve this problem is that each station independently tosses an asymmetric coin and transmits in case of tails. The trials are executed some number of times and the first station that sends alone in a trial gets the right to broadcast over the shared channel. We consider here a multi-channel case: during onetime slot a station may transmit on k different channels.In this case trials can be arranged in two slightly different ways. The first method is that in each trial a station decides whether to participate in it; if it is so, then the station decides independently for each channel whether to transmit on it. According to the second method a station makes one decision whether to send and if the decision is positive it chooses a single channel for transmission. The second method guarantees a limited energy cost for each station but,as we show, turns out to be inferior regarding success probability. We consider these algorithms for a realistic number of stations. We analyze subtle differences between both algorithms regarding success probability.

We investigate a problem of maintaining a target population of mobile agents in a distributed system. The purpose of the agents is to perform certain activities, so the goal is to avoid overpopulation (leading to waste of resources) as well as underpopulation (resulting in a poor service). We assume that there must be no centralized control over the number of agents, since it might result in system's vulnerability. We analyze a simple protocol in which each node keeps at most one copy of an agent and if there is a single agent in a node, a new agent is born with a certain probability p. At each time step the agents migrate independently at random to chosen locations. We show that during a protocol execution the number of agents stabilizes around a level depending on p. We derive analytically simple formulas that determine probability p based on the target fraction of nodes holding an agent. The previous proposals of this type were based on experimental data only.