Name
Abstract | ||
|---|---|---|
We provide a Kleene Theorem for (Rabin) probabilistic automata over finite words. Probabilistic automata generalize deterministic finite automata and assign to a word an acceptance probability. We provide probabilistic expressions with probabilistic choice, guarded choice, concatenation, and a star operator. We prove that probabilistic expressions and probabilistic automata are expressively equivalent. Our result actually extends to two-way probabilistic automata with pebbles and corresponding expressions. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-33386-6_31 | ATVA |
Keywords | Field | DocType |
kleene theorem,probabilistic choice,probabilistic kleene theorem,acceptance probability,finite word,expressively equivalent,probabilistic expression,deterministic finite automaton,probabilistic automaton,guarded choice,corresponding expression,probabilistic automata | Quantum finite automata,Discrete mathematics,Automata theory,Nested word,Computer science,Probabilistic CTL,Probabilistic analysis of algorithms,Probabilistic logic,Probabilistic argumentation,Probabilistic automaton | Conference |
Citations | PageRank | References |
1 | 0.36 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Benedikt Bollig | 1 | 427 | 35.02 |
| Paul Gastin | 2 | 1165 | 75.66 |
| Benjamin Monmege | 3 | 77 | 11.97 |
| Marc Zeitoun | 4 | 288 | 24.51 |