Journal article icon

Journal article

Game characterization of probabilistic bisimilarity, and applications to pushdown automata

Abstract:

We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and nondeterministic branching, generalising the classical notion of pushdown automata (without epsilon-transitions). We first show a general characterization of probabilistic bisimilarity in terms of two-player games, which naturally reduces checking bisimilarity of probabilistic labelled transition systems to checking bisimilarity of standard ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.23638/LMCS-14(4:13)2018

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St John's College
Role:
Author
ORCID:
0000-0003-4173-6877
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More from this funder
Name:
Royal Society
Funding agency for:
Kiefer, S
Grant:
UF120396
More from this funder
Name:
Grant Agency of the Czech Republic
Funding agency for:
Forejt, V
Grant:
GACR:15-13784S
Publisher:
International Federation of Computational Logic
Journal:
Logical Methods in Computer Science (LMCS) More from this journal
Volume:
14
Issue:
4
Article number:
13
Publication date:
2018-11-15
Acceptance date:
2018-10-08
DOI:
EISSN:
1860-5974
ISSN:
1860-5974
Keywords:
Pubs id:
pubs:936824
UUID:
uuid:0695ce49-60d5-48fa-9159-7b3acae75dd7
Local pid:
pubs:936824
Source identifiers:
936824
Deposit date:
2018-11-03

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP