Conference item icon

Conference item

Trace refinement in labelled Markov decision processes

Abstract:

Given two labelled Markov decision processes (MDPs), the trace-refinement problem asks whether for all strategies of the first MDP there exists a strategy of the second MDP such that the induced labelled Markov chains are trace-equivalent. We show that this problem is decidable in polynomial time if the second MDP is a Markov chain. The algorithm is based on new results on a particular notion of bisimulation between distributions over the states. However, we show that the general trace-refine...

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

Actions


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
European Joint Conferences on Theory and Practice of Software (ETAPS) Publisher's website
Host title:
19th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS)
Publication date:
2015-01-01
Source identifiers:
581558
Pubs id:
pubs:581558
UUID:
uuid:c0797cde-6c63-4587-b97b-2a6ad09410f8
Local pid:
pubs:581558
Deposit date:
2016-01-10

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