A theory of probabilistic automata, part 1

In [1], we introduced the weakly synchronizing languages for probabilistic automata. In this report, we show that the emptiness problem of weakly synchronizing languages for probabilistic automata is undecidable. This implies that the decidability result of [1-3] for the emptiness problem of weakly synchronizing language is incorrect.

We consider the state-minimisation problem for weighted and probabilistic automata. We provide a numerically stable polynomial-time minimisation algorithm for weighted automata, with guaranteed bounds on the numerical error when run with floating-point arithmetic. Our algorithm can also be used for "lossy" minimisation with bounded error. We show an application in image compression. In the second part of the paper we study the complexity of the minimisation problem for probab...

This text is an extended version of the chapter 'Automata and rational expressions' in the AutoMathA Handbook that will appear soon, published by the European Science Foundation and edited by JeanEricPin.

This is a reissue of the book Tree Automata by F. G\'ecseg and M. Steinby originally published in 1984 by Akad\'emiai Kiad\'o, Budapest. Some mistakes have been corrected and a few obscure passages have been clarified. Moreover, some more recent contributions and current lines of research are reviewed in an appendix that also contains several new references.

A definition of a probabilistic automaton is formulated in which its prime decomposition follows as a direct consequence of Krohn-Rhodes theorem. We first characterize the local structure of probabilistic automata. The prime decomposition is presented as a framework to study the global structure of probabilistic automata. We prove that the representation theory of a probabilistic automaton is determined by that of the finite groups in its holonomy decomposition.

In the following pages we discuss infinite sequences defined on a finite alphabet, and more specially those which are generated by finite automata. We have divided our paper into seven parts which are more or less self-contained. Needless to say, we feel that the order we propose is the most natural one. References appear at the end of each one of the parts which implies some redundancy. Extra references are listed at the very end of our paper.

Probabilistic B\"uchi automata are a natural generalization of PFA to infinite words, but have been studied in-depth only rather recently and many interesting questions are still open. PBA are known to accept, in general, a class of languages that goes beyond the regular languages. In this work we extend the known classes of restricted PBA which are still regular, strongly relying on notions concerning ambiguity in classical omega-automata. Furthermore, we investigate the exp...

This text aims to provide a self-contained, comprehensive, and reasonably detailed presentation of the theory of Stallings automata and some of its main applications.

Given a Probabilistic Finite Automata (PFA), a set of states S, and an error threshold e > 0, our algorithm approximates the infimum probability (quantifying over all infinite words) that the automata reaches S. Our result contrasts with the known result that the approximation problem is undecidable if we consider the supremum instead of the infimum. Since we study the probability of reaching a set of states, instead of the probability of ending in an accepting state, our wor...

We consider the value 1 problem for probabilistic automata over finite words: it asks whether a given probabilistic automaton accepts words with probability arbitrarily close to 1. This problem is known to be undecidable. However, different algorithms have been proposed to partially solve it; it has been recently shown that the Markov Monoid algorithm, based on algebra, is the most correct algorithm so far. The first contribution of this paper is to give a characterisation of...