# 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 ...

4

You can still argue by counting. No matter how randomness is used, there is a way to fix the randomness in such a way that the function is computed correctly deterministically on at least $\frac{2}{3}2^n$ inputs. Thus assuming any function can be computed with error at most $\frac{1}{3}$ by some circuit in size $S$, any function can be described by a circuit ...

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

I assume that you are asking for the construction of the probability space for a given LMP. Although, I do not have a particular reference for this construction, there are a few closely related constructions that might help you. The usual way (in my oppinion) would be to construct the probability spaces via Borel $\sigma$-algebras. The following book is a ...

2

[Comment space was too short] I think it depends on what you mean by behaviour. Probabilistic automata follow in the tradition of finite automata, so their behaviour is defined in terms of their language or traces. Labelled Markov Processes follow in the tradition of process algebra, where it is known that processes can be compared using a variety of ...

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