Informace o publikaci
One-Counter Markov Decision Processes
| Autoři | |
|---|---|
| Rok publikování | 2010 |
| Druh | Článek ve sborníku |
| Konference | Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | Link to SODA 2010 electronic proceedings |
| Obor | Informatika |
| Klíčová slova | Markov decision proces; probability; one counter MDP; reachability; termination |
| Popis | V článku jsou studovány Markovovy rozhodovací procesy generované procesy s jedním neomezeným čítačem. Uvažovaná výherní kritéria zahrnují dosažitelnost a různé limitní vlastnosti běhů. V článku je dokázáno, že některé varianty těchto problémů jsou efektivně řešitelné v polynomiálním čase. O jiných je ukázáno, že jsou PSPACE těžké a je podán algoritmus s exponenciální časovou složitostí. |
| Související projekty: |