Conference icon

Conference

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
Version:
Accepted Manuscript

Actions


Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
European Joint Conferences on Theory and Practice of Software (ETAPS) Publisher's website
Publication date:
2015-01-01
URN:
uuid:c0797cde-6c63-4587-b97b-2a6ad09410f8
Source identifiers:
581558
Local pid:
pubs:581558

Terms of use


Metrics


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