The probabilistic-automata tag has no wiki summary.
1
vote
0answers
73 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 ...
2
votes
0answers
56 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 ...
4
votes
2answers
128 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 ...
6
votes
0answers
98 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 ...
5
votes
0answers
133 views
The regularity of Markov chains with a threshold
(This question has been asked on math.se, with no response.)
I am studying Paz's "Introduction to Probabilistic Automata" and there is an exercise I cannot solve:
Ex. 11, p. 170: Let $\Sigma = ...
4
votes
1answer
199 views
Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions
If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( ...
5
votes
0answers
112 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 ...
