Kaminski, BL;
Katoen, J-P;
(2015)
On the Hardness of Almost-Sure Termination.
In: Italiano, GF and Pighizzini, G and Sannella, DT, (eds.)
International Symposium on Mathematical Foundations of Computer Science MFCS 2015: Mathematical Foundations of Computer Science 2015.
(pp. pp. 307-318).
Springer, Berlin, Heidelberg
Preview |
Text
typeinst.pdf - Accepted Version Download (426kB) | Preview |
Abstract
This paper considers the computational hardness of computing expected outcomes and deciding (universal) (positive) almost–sure termination of probabilistic programs. It is shown that computing lower and upper bounds of expected outcomes is Σ01 – and Σ02 –complete, respectively. Deciding (universal) almost–sure termination as well as deciding whether the expected outcome of a program equals a given rational value is shown to be Π02 –complete. Finally, it is shown that deciding (universal) positive almost–sure termination is Σ02 –complete ( Π03 –complete).
| Type: | Proceedings paper |
|---|---|
| Title: | On the Hardness of Almost-Sure Termination |
| Event: | 40th International Symposium on Mathematical Foundations of Computer Science (MFCS) |
| Location: | Milan, ITALY |
| Dates: | 24 August 2015 - 28 August 2015 |
| ISBN-13: | 978-3-662-48056-4 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-662-48057-1_24 |
| Publisher version: | https://doi.org/10.1007/978-3-662-48057-1_24 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Probabilistic programs, Expected outcomes, Almost–sure termination, Positive almost–sure termination, Computational hardness |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10089699 |
Loading...
Loading...Loading...| 1. |  United States | 7 |
| 2. |  Russian Federation | 2 |
| 3. |  Germany | 2 |
| 4. |  Austria | 1 |
| 5. |  China | 1 |
| 6. |  Honduras | 1 |
Archive Staff Only
 |
View Item |
