# Questions tagged [probabilistic-automata]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
142 views

### How can I find the PhD thesis of C.A. Ellis?

I've searched for this article all over the web but couldn't find it. can anyone help me? Ellis, C.A. 1969. Probabilistic languages and automata. Rept. no. 355. Dept. Comp. Sc. University of Illinois, ...
51 views

### Palindrome language and Finite Automata Machines [closed]

I'm a grad student in math. I'm unaware of available literature in theoretical computer science, so require suggestions for books. Here are the two topics I'm interested in exploring. 1) A complete ...
343 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 ...
76 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 ...
73 views

### Vector representation of probabilistic automaton

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 ...
455 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 ...
777 views

### What is the relationship between the number of states in Quantum Finite Automata and the number of non-regular languages they can recognize?

It is has been shown that Quantum Finite Automata can recognize at least some non-regular languages. What is the relationship between the number of states in a qfa and the number of non-regular ...
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 ...
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 ...
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 ...