A theory of probabilistic automata, part 1

Since Edward Moore, finite automata theory has been inspired by physics, in particular by quantum complementarity. We review automaton complementarity, reversible automata and the connections to generalized urn models. Recent developments in quantum information theory may have appropriate formalizations in the automaton context.

The goal of the present paper is to provide a systematic and comprehensive study of rational stochastic languages over a semiring K \in {Q, Q +, R, R+}. A rational stochastic language is a probability distribution over a free monoid \Sigma^* which is rational over K, that is which can be generated by a multiplicity automata with parameters in K. We study the relations between the classes of rational stochastic languages S rat K (\Sigma). We define the notion of residual of a ...

This paper introduces and investigates decision problems for numberless probabilistic automata, i.e. probabilistic automata where the support of each probabilistic transitions is specified, but the exact values of the probabilities are not. A numberless probabilistic automaton can be instantiated into a probabilistic automaton by specifying the exact values of the non-zero probabilistic transitions. We show that the two following properties of numberless probabilistic autom...

This paper grew out of three tutorial lectures on automatic structures given by the first author at the Logic Colloquium 2007. We discuss variants of automatic structures related to several models of computation: word automata, tree automata, Buchi automata, and Rabin automata. Word automata process finite strings, tree automata process finite labeled trees, Buchi automata process infinite strings, and Rabin automata process infinite binary labeled trees. Automatic structures...

In this paper, we systematize the modeling of probabilistic systems for the purpose of analyzing them with model counting techniques. Starting from unbiased coin flips, we show how to model biased coins, correlated coins, and distributions over finite sets. From there, we continue with modeling sequential systems, such as Markov chains, and revisit the relationship between weighted and unweighted model counting. Thereby, this work provides a conceptual framework for deriving ...

We present the first study of non-deterministic weighted automata under probabilistic semantics. In this semantics words are random events, generated by a Markov chain, and functions computed by weighted automata are random variables. We consider the probabilistic questions of computing the expected value and the cumulative distribution for such random variables. The exact answers to the probabilistic questions for non-deterministic automata can be irrational and are uncomp...

The 14th International Conference Automata and Formal Languages (AFL 2014) was held in Szeged, Hungary, from the 27th to the 29th of May, 2014. The conference was organized by the Department of Foundations of Computer Science of the University of Szeged. Topics of interest covered the theory and applications of automata and formal languages and related areas.

It is undecidable whether the language recognized by a probabilistic finite automaton is empty. Several other undecidability results, in particular regarding problems about matrix products, are based on this important theorem. We present three proofs of this theorem from the literature in a self-contained way, and we derive some strengthenings. For example, we show that the problem remains undecidable for a fixed probabilistic finite automaton with 11 states, where only the s...

This is a book on weighted tree automata. We present the basic definitions and some of the important results in a coherent form with full proofs. The concept of weighted tree automata is part of Automata Theory and it touches the area of Universal Algebra. It originated from two sources: weighted string automata and finite-state tree automata.

We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, B\"uchi, coB\"uchi, and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs for probabilistic finite automata and present a complete characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems for probabilistic automata on infinite words...