Trace refinement in labelled Markov decision processes
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...
| المؤلفون الرئيسيون: | , , |
|---|---|
| التنسيق: | Journal article |
| اللغة: | English |
| منشور في: |
Logical Methods in Computer Science
2020
|
| _version_ | 1826283611454701568 |
|---|---|
| author | Fijalkow, N Kiefer, S Shirmohammadi, M |
| author_facet | Fijalkow, N Kiefer, S Shirmohammadi, M |
| author_sort | Fijalkow, N |
| collection | OXFORD |
| description | 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-refinement problem is undecidable, even if the first MDP is a Markov chain. Decidability of those problems was stated as open in 2008. We further study the decidability and complexity of the trace-refinement problem provided that the strategies are restricted to be memoryless. |
| first_indexed | 2024-03-07T01:01:28Z |
| format | Journal article |
| id | oxford-uuid:89e1915f-bd6e-4281-971b-6133f078a040 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:01:28Z |
| publishDate | 2020 |
| publisher | Logical Methods in Computer Science |
| record_format | dspace |
| spelling | oxford-uuid:89e1915f-bd6e-4281-971b-6133f078a0402022-03-26T22:27:33ZTrace refinement in labelled Markov decision processesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:89e1915f-bd6e-4281-971b-6133f078a040EnglishSymplectic ElementsLogical Methods in Computer Science2020Fijalkow, NKiefer, SShirmohammadi, MGiven 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-refinement problem is undecidable, even if the first MDP is a Markov chain. Decidability of those problems was stated as open in 2008. We further study the decidability and complexity of the trace-refinement problem provided that the strategies are restricted to be memoryless. |
| spellingShingle | Fijalkow, N Kiefer, S Shirmohammadi, M Trace refinement in labelled Markov decision processes |
| title | Trace refinement in labelled Markov decision processes |
| title_full | Trace refinement in labelled Markov decision processes |
| title_fullStr | Trace refinement in labelled Markov decision processes |
| title_full_unstemmed | Trace refinement in labelled Markov decision processes |
| title_short | Trace refinement in labelled Markov decision processes |
| title_sort | trace refinement in labelled markov decision processes |
| work_keys_str_mv | AT fijalkown tracerefinementinlabelledmarkovdecisionprocesses AT kiefers tracerefinementinlabelledmarkovdecisionprocesses AT shirmohammadim tracerefinementinlabelledmarkovdecisionprocesses |