Skip to main content

Questions tagged [probabilistic-automata]

The tag has no usage guidance.

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10 votes
0 answers
164 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 ...
Michaël Cadilhac's user avatar
7 votes
0 answers
158 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 ...
kbkb's user avatar
  • 171
5 votes
0 answers
169 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 = \{a\...
Michaël Cadilhac's user avatar
2 votes
0 answers
86 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 ...
hr0nix's user avatar
  • 81
2 votes
0 answers
785 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 ...
David Drane's user avatar
1 vote
0 answers
78 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 ...
Suzan Cioc's user avatar
0 votes
0 answers
129 views

Computational power of probabilistic automata

I am a bit confused about the proper role of probabilistic automata (PA) in the theory of computation. Informally, I can imagine they can accept more than finite automata (FA) as they, for instance, ...
Barney's user avatar
  • 151