van Heerdt, G;
Hsu, J;
Ouaknine, J;
Silva, A;
(2018)
Convex Language Semantics for Nondeterministic Probabilistic Automata.
In: Fischer, B and Uustalu, T, (eds.)
Theoretical Aspects of Computing – ICTAC 2018. ICTAC 2018. Lecture Notes in Computer Science.
(pp. pp. 472-492).
Springer: Cham.
Preview |
Text
main.pdf - Accepted Version Download (412kB) | Preview |
Abstract
We explore language semantics for automata combining probabilistic and nondeterministic behaviors. We first show that there are precisely two natural semantics for probabilistic automata with nondeterminism. For both choices, we show that these automata are strictly more expressive than deterministic probabilistic automata, and we prove that the problem of checking language equivalence is undecidable by reduction from the threshold problem. However, we provide a discounted metric that can be computed to arbitrarily high precision.
| Type: | Proceedings paper |
|---|---|
| Title: | Convex Language Semantics for Nondeterministic Probabilistic Automata |
| Event: | Theoretical Aspects of Computing – ICTAC 2018. |
| ISBN-13: | 9783030025076 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-030-02508-3_25 |
| Publisher version: | https://doi.org/10.1007/978-3-030-02508-3_25 |
| 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. |
| 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/10061791 |
Archive Staff Only
 |
View Item |
