# Tag Info

9

The first paper by Rabin (1963) gives the basics what you are looking for. The class of languages recognized by probabilistic automata (with cutpoint) is called stochastic languages. Let $P$ be a probabilistic automaton defined on the alphabet $\Sigma$ and $f_P(w)$ be the accepting probability of $P$ on the input $w \in \Sigma^*$. Then, $P$ with ...

7

You can find a pdf with the thesis in the following way: Find the wikipedia page for Clarence Ellis; On the wikipedia page find the link to his thesis "Probabilistic languages and automata"; Click on this link to find the corresponding archive.org page; Download the thesis at archive.org.

3

By simplification I understand either minimization or determinization. I'll try to sum up what I know about both problems, in the quite general setting of weighted automata over arbitrary semiring. The original works were done by Marcel-Paul Schützenberger (who introduced them), and you'll find a nice account of what is known about them in the book Elements ...

2

Stefan Kiefer has some work on minimization of probabilistic automata. This should probably put you on the right track: https://arxiv.org/abs/1404.6673.

2

Mayr and Clemente have shown that it is often possible to simplify NFAs. Their techniques rely on pruning the underlying labelled transition system via local approximations of trace inclusions. As far as I can tell, this technique would still apply in the weighted case. See also a related question. Richard Mayr and Lorenzo Clemente, Advanced automata ...

1

Actually there is an algorithm for approximated determinization of a weighted NFA, by Aminoff Kupferman and Lampert, where the approximation factor can be determined beforehand (if I remember correctly). See here.

1

I am not sure whether $A_f$ is an $\omega$-regular event, but for any $\delta>0$ we can pick some $\omega$-regular $A_\delta$ such that $|\mathsf P(A_\delta) - \mathsf P_\delta(A_\delta)| \geq 1-\delta$. This follows from the fact that $\omega$-regular events form an algebra that generates a $\sigma$-algebra where $A_f$ does belong to.

Only top voted, non community-wiki answers of a minimum length are eligible