# Questions tagged [probabilistic-automata]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
298 views

### Introduction to probabilistic automata

Where can I find an introduction to probabilistic automata and what they recognize (certain functions from words to $[0,1]$)? Is there a standard term for such functions which are recognized by ...
145 views

### A language outside the Boolean closure of stochastic languages

Stochastic languages, that is, those accepted by probabilistic automata, are known to not be closed under intersection, union, concatenation, and morphism, even on unary languages. I have two ...
150 views

### Size complexity of probabilistic two-way automata for a Boolean function

I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the ...
426 views

### Simplification of weighted NFA

What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then ...
166 views

### Behaviour of Labelled Markov Processes

Labelled Markov Processes (LMP) seem to be a generalization of Probabilistic Automata (PA) studied by Segala to the case of the general state space. Namely, any LMP is given by a be a finite set of ...
142 views

### $\omega$-regular properties of a 2-state Markov Chain

Let $X$ be a Markov Chain on a state space $\{0,1\}$ with a transition matrix P = \left( \begin{align} 1-p & &p \\ q & &1-q \end{align} \right) with both $p,q \in (0,1)$ so in ...
165 views

74 views

### WFSA over hyperreals

Are there any works where authors tried to define weighted finite state automata over hyperreals (or a similar object allowing for infinite and infinitesimal values) in an attempt to make automata ...
Suppose we have $N$ states $q_i$, $0\leq i<N$ Suppose we have $N\times N$ probability matrix $p_{ij}$, $0\leq i<N$, $0\leq j<N$, And suppose a machine, which is being in state $q_i$ then ...