Abstract | ||
---|---|---|
This short note aims at proving that the isolation problem is undecidable for probabilistic automata with only one probabilistic transition. This problem is known to be undecidable for general probabilistic automata, without restriction on the number of probabilistic transitions. In this note, we develop a simulation technique that allows to simulate any probabilistic automaton with one having only one probabilistic transition. |
Year | Venue | Keywords |
---|---|---|
2011 | Clinical Orthopaedics and Related Research | automata theory,probabilistic automata,formal language |
Field | DocType | Volume |
Quantum finite automata,Discrete mathematics,Automata theory,Mobile automaton,Probabilistic CTL,Probabilistic analysis of algorithms,Theoretical computer science,Probabilistic logic,Probabilistic automaton,Mathematics,Undecidable problem | Journal | abs/1104.3 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nathanaël Fijalkow | 1 | 61 | 19.71 |
Hugo Gimbert | 2 | 249 | 21.31 |
Youssouf Oualhadj | 3 | 60 | 6.99 |