Journal article
Convex language semantics for nondeterministic probabilistic automata
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 387.5KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-030-02508-3_25
Authors
- Publisher:
- Springer
- Journal:
- Lecture Notes in Computer Science More from this journal
- Volume:
- 11187 LNCS
- Pages:
- 472-492
- Publication date:
- 2018-10-15
- Acceptance date:
- 2018-07-09
- DOI:
- EISSN:
-
1611-3349
- ISSN:
-
0302-9743
- Keywords:
- Pubs id:
-
pubs:857998
- UUID:
-
uuid:931052c5-4d57-4691-98b7-6d6dc190704f
- Local pid:
-
pubs:857998
- Source identifiers:
-
857998
- Deposit date:
-
2019-03-21
Terms of use
- Copyright holder:
- Springer
- Copyright date:
- 2018
- Notes:
- © Springer Nature Switzerland AG 2018. This is the Accepted Manuscript version of the article. The final version is available online from Springer at: https://doi.org/10.1007/978-3-030-02508-3_25
If you are the owner of this record, you can report an update to it here: Report update to this record