We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language L is accepted by a Las Vegas automaton having r states such that the probability for a definite answer to occur is at least p, then r ≥ np, where n is the number of the states of the minimal deterministic automaton accepting L. Earlier this result has been obtained in [2] by using a reduction...

Stochastic interdependence of a probability distribution on a product space is measured by its Kullback–Leibler distance from the exponential family of product distributions (called multi-information). Here we investigate low-dimensional exponential families that contain the maximizers of stochastic interdependence in their closure. Based on a detailed description of the structure of probability distributions with globally maximal multi-information we obtain our main result: The exponential family...

Partially-additive monoids (pams) were introduced by Arbib and Manes ([1]) in order to provide an algebraic approach to the semantic of recursion in theoretical computer science. Here we extend the range of application of pams for capturing information theory concepts as componibility and sequential continuity, which arise naturally in this framework.

In this paper, we obtain all possible general solutions of the sum form functional equations $$\begin{array}{cc}\hfill \sum _{i=1}^k\sum _{j=1}^{\ell }f\left(p_i{q}_j\right)=& \sum _{i=1}^{k}g\left(p_i\right)\sum _{j=1}^{\ell }h\left(q_j\right)\hfill \\ \hfill \text{and}\sum _{i=1}^k\sum _{j=1}^{\ell }F\left(p_i{q}_j\right)=& \sum _{i=1}^{k}G\left(p_i\right)+\sum _{j=1}^{\ell }H\left(q_j\right)+\lambda \sum _{i=1}^{k}G\left(p_i\right)\sum _{j=1}^{\ell }H\left(q_j\right)\hfill \end{array}$$ valid for all complete probability distributions $(p_1,...,p_k)$, $(q_1,...,q_{\ell })$, $k\ge 3$, $\ell \ge 3$ fixed integers; $\lambda \in ℝ$, $\lambda \ne 0$ and $F$, $G$, $H$, $f$, $g$, $h$ are real valued mappings each having the domain $I=[0,1]$, the unit closed interval.