The set of binary decision diagrams , an efficient data structure representing Boolean functions, is extensively used in many distinct contexts like model verification, machine learning, cryptography, and resolution of combinatorial problems. The most famous variant, called reduced ordered binary decision diagram ( robdd ), can be viewed as the result of a specific compaction of a complete decision tree. A great property is that, once an order over the Boolean variables is fixed, each Boolean function is represented by exactly one robdd . In this article, we aim at computing the exact distribution of the Boolean functions in \( k \) variables according to the robdd size . Recall the number of Boolean functions with \( k \) variables is equal to \(2^{2^{k}}\!,\) which is of double exponential growth with respect to the number of variables. The maximal size of an robdd with \( k \) variables is \(M_{k}\approx 2^{k}/k\) . In this article, we develop the first polynomial algorithm to derive the distribution of Boolean functions over \( k \) variables with respect to robdd size denoted by \( n \) . It performs \(O(k\;n^{3}\log n)\) arithmetic operations on integers and necessitates to store \(O(n^{2})\) integers in memory storage; note that the maximal size of integers involved in the computations is \(O(k\;2^{k})\) bits. Our new approach relies on a decomposition of robdd s layer by layer and on an enumerative inclusion-exclusion argument.

For three decades binary decision diagrams, a data structure efficiently representing Boolean functions, have been widely used in many distinct contexts like model verification, machine learning, cryptography and also resolution of combinatorial problems. The most famous variant, called reduced ordered binary decision diagram (robdd for short), can be viewed as the result of a compaction procedure on the full decision tree. A useful property is that once an order over the Boolean variables is fixed, each Boolean function is represented by exactly one robdd. In this paper we aim at computing the {exact distribution of the Boolean functions in k variables according to the robdd size}, where the robdd size is equal to the number of decision nodes of the underlying directed acyclic graph (dag) structure. Recall the number of Boolean functions with k variables is equal to 2^{2^k}, which is of double exponential growth with respect to the number of variables. The maximal size of a robdd with k variables is M_k ≈ 2^k / k. Apart from the natural combinatorial explosion observed, another difficulty for computing the distribution according to size is to take into account dependencies within the dag structure of robdds. In this paper, we develop the first polynomial algorithm to derive the distribution of Boolean functions over k variables with respect to robdd size denoted by n. The algorithm computes the (enumerative) generating function of robdds with k variables up to size n. It performs O(k n⁴) arithmetical operations on integers and necessitates storing O((k+n) n²) integers with bit length O(nlog n). Our new approach relies on a decomposition of robdds layer by layer and on an inclusion-exclusion argument.

We propose an approach combining layer freezing and fine-tuning steps alternatively to train a neural network over multiple and diverse datasets in the context of cancer detection from medical images. Our method explicitly splits the network into two distinct but complementary components: the feature extractor and the decision maker. While the former remains constant throughout training, a different decision maker is used on each new dataset. This enables end-to-end training of the feature extractor on heterogeneous datasets (here MRIs and CT scans) and organs (here prostate, lung and brain). The feature extractor learns features across all images, with two major benefits: (i) extended training data pool, and (ii) enforced generalization across different data. We show the effectiveness of our method by detecting cancerous masses in the SPIE-AAPM-NCI Prostate MR Classification data. Our training process integrates the SPIE-AAPM-NCI Lung CT Classification dataset as well as the Kaggle Brain MRI dataset, each paired with a separate decision maker, improving the AUC of the base network architecture on the Prostate MR dataset by 0.12 (18% relative increase) versus training on the prostate dataset alone. We also compare against standard end-to-end Transfer Learning over the same datasets for reference, which only improves the results by 0.04 (6% relative increase).

The paper studies the behaviour of selection algorithms that are based on dichotomy principles. On the entry formed by an ordered list L and a searched element x not in L, they return the interval of the list L the element x belongs to. We focus here on the case of words, where dichotomy principles lead to a selection algorithm designed by Crochemore, Hancart and Lecroq, which appears to be "quasi-optimal". We perform a probabilistic analysis of this algorithm that exhibits its quasi-optimality on average.

For some text algorithms, the real measure for the complexity analysis is not the string itself but its structure stored in its prefix table or equivalently border table. In this paper, we define the combinatorial class of prefix lists, namely a sequence of integers together with their size, and an injection ψ from the class of prefix tables to the class of prefix lists. We call a valid prefix list the image by ψ of a prefix table. In particular, we describe algorithms converting a prefix/border table to a prefix list and inverse linear algorithms from computing from a prefix list L = ψ(P) two words respectively in a minimal size alphabet and on a maximal size alphabet with P as prefix table. We then give a new upper bound on the number of prefix tables for strings of length n (on any alphabet) which is of order (1 + ϕ)n (with $\varphi=\frac{1+\sqrt{5}}{2}$ the golden mean) and also present a corresponding lower bound.

We describe a general framework for realistic analysis of sorting and searching algorithms, and we apply it to the average-case analysis of five basic algorithms: three sorting algorithms (QuickSort, InsertionSort, BubbleSort) and two selection algorithms (QuickMin and SelectionMin). Usually, the analysis deals with the mean number of key comparisons, but, here, we view keys as words produced by the same source, which are compared via their symbols in the lexicographic order. The "realistic" cost of the algorithm is now the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to providee stimates for the mean number of symbol comparisons used by the algorithm. For sorting algorithms, and with respect to key comparisons, the average-case complexity of QuickSort is asymptotic to 2n log n, InsertionSort to n^2/4 and BubbleSort to n^2/2. With respect to symbol comparisons, we prove that their average-case complexity becomes Theta(n log^2n), Theta(n^2), Theta (n^2 log n). For selection algorithms, and with respect to key comparisons, the average-case complexity of QuickMin is asymptotic to 2n, of SelectionMin is n - 1. With respect to symbol comparisons, we prove that their average-case complexity remains Theta(n). In these five cases, we describe the dominant constants which exhibit the probabilistic behaviour of the source (namely, entropy, and various notions of coincidence) with respect to the algorithm.

Optimal prefix codes are studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameterq, 0qqcannot be optimal for any other value ofq. This is in sharp contrast to the one-dimensional (1-D) case, where codes are optimal for positive-length intervals of the parameterq. Thus, in the 2-D case, it is infeasible to give a compact characterization of optimal codes for all values of the parameterq, as was done in the 1-D case. Instead, optimal codes are characterized for a discrete sequence of values ofqthat provides good coverage of the unit interval. Specifically, optimal prefix codes are described forq= 2-1/k(k≥ 1), covering the rangeq≥ [1/2], andq= 2-k(k> 1), covering the rangeq<; [1/2]. The described codes produce the expected reduction in redundancy with respect to the 1-D case, while maintaining low-complexity coding operations.

In this article, we provide the multivariate generating function counting texts according to their length and to the number of occurrences of words from a finite set. The application of the inclusion-exclusion principle to word counting due to Goulden and Jackson [1979, 1983] is used to derive the result. Unlike some other techniques which suppose that the set of words is reduced (i.e., where no two words are factor of one another), the finite set can be chosen arbitrarily. Noonan and Zeilberger [1999] already provided a Maple package treating the nonreduced case, without giving an expression of the generating function or a detailed proof. We provide a complete proof validating the use of the inclusion-exclusion principle. Some formulæ for expected values, variance, and covariance for number of occurrences when considering two arbitrary sets of finite words are given as an application of our methodology.

We address the problem of verification by model checking of the basic population protocol (PP) model of Angluin et al. This problem has received special attention in the last two years and new tools have been proposed to deal with it. We show that the problem can be solved by using the existing model-checking tools, e.g., Spin and Prism. In order to do so, we apply the counter abstraction to get an abstraction of the PP model which can be efficiently verified by the existing model-checking tools. Moreover, this abstraction preserves the correct stabilization property of PP models. To deal with the fairness assumed by the PP models, we provide two new recipes. The first one gives sufficient conditions under which the PP model fairness can be replaced by the weak fairness implemented in Spin. We show that this recipe can be applied to several PP models. In the second recipe, we show how to use probabilistic model-checking and, in particular, Prism to take completely in consideration the fairness of the PP models. The correctness of this recipe is based on existing theorems involving finite discrete Markov chains.

The Prefix table of a string reports for each position the maximal length of its prefixes starting here. The Prefix table and its dual Suffix table are basic tools used in the design of the most efficient string-matching and pattern extraction algorithms. These tables can be computed in linear time independently of the alphabet size. We give an algorithmic characterisation of a Prefix table (it can be adapted to a Suffix table). Namely, the algorithm tests if an integer table of size $n$ is the Prefix table of some word and, if successful, it constructs the lexicographically smallest string having it as a Prefix table. We show that the alphabet of the string can be bounded to $\log_2 n$ letters. The overall algorithm runs in $O(n)$ time.

Lossless compression is studied for pairs of independent integer-valued symbols emitted by a source with a geometric probability distribution of parameter q /spl isin/ (0,1). Optimal prefix codes are described for q = 1/2/sup k/ (k > 1) and q = 1/k/spl radic/2 (k > 0). The codes described differ from previously characterized cases related to the geometric distribution in that their corresponding trees are of unbounded width, and in that an infinite set of distinct optimal codes is required to cover any interval (0, /spl epsi/), /spl epsi/ > 0, of values of q.

Lossless compression is studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameter q, 0k(k > 1) and q = 1/knthroot2 (k > 0). These codes retain some of the low-complexity and low-latency advantage of symbol by symbol coding of geometric distributions, which is widely used in practice, while improving on the inherent redundancy of the approach. From a combinatorial standpoint, the codes described differ from previously characterized cases related to the geometric distribution in that their corresponding trees are of unbounded width, and in that an infinite set of distinct optimal codes is required to cover any interval (0,epsi), epsi > 0, of values of q