Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.445
URN: urn:nbn:de:0030-drops-33435
URL: https://drops.dagstuhl.de/opus/volltexte/2011/3343/
Fu, Hongfei ; Katoen, Joost-Pieter
Deciding Probabilistic Simulation between Probabilistic Pushdown Automata and Finite-State Systems
| pdf-format: |
|
Abstract
This paper studies the decidability and computational complexity of checking probabilistic simulation pre-order between probabilistic pushdown automata (pPDA) and (probabilistic)finite-state systems.We show that checking classical and combined probabilistic similarity are EXPTIME-complete in both directions and become polynomial if both the number of control states of the pPDA and the size of the finite-state system are fixed. These results show that checking probabilistic similarity is as hard as checking similarity
in the standard, i.e., non-probabilistic setting.
BibTeX - Entry
@InProceedings{fu_et_al:LIPIcs:2011:3343,
author = {Hongfei Fu and Joost-Pieter Katoen},
title = {{Deciding Probabilistic Simulation between Probabilistic Pushdown Automata and Finite-State Systems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages = {445--456},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-34-7},
ISSN = {1868-8969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3343},
URN = {urn:nbn:de:0030-drops-33435},
doi = {10.4230/LIPIcs.FSTTCS.2011.445},
annote = {Keywords: infinite-state systems, probabilistic simulation, probabilistic pushdown automata}
}
| Keywords: | infinite-state systems, probabilistic simulation, probabilistic pushdown automata | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) | |
| Issue date: | 2011 | |
| Date of publication: | 01.12.2011 |
