文章基本信息

标题：Trace Refinement in Labelled Markov Decision Processes
本地全文：下载
作者：Shirmohammadi, Mahsa ; Kiefer, Stefan ; Fijalkow, Nathanaël 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2020
卷号：16
期号：2
页码：1-28
语种：English
出版社：Technical University of Braunschweig
摘要：Given two labelled Markov decision processes (MDPs), the trace-refinementproblem asks whether for all strategies of the first MDP there exists astrategy of the second MDP such that the induced labelled Markov chains aretrace-equivalent. We show that this problem is decidable in polynomial time ifthe second MDP is a Markov chain. The algorithm is based on new results on aparticular notion of bisimulation between distributions over the states.However, we show that the general trace-refinement problem is undecidable, evenif the first MDP is a Markov chain. Decidability of those problems was statedas open in 2008. We further study the decidability and complexity of thetrace-refinement problem provided that the strategies are restricted to bememoryless.
关键词：Computer Science ;Logic in Computer Science