کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10331878 686963 2015 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Reachability problems for Markov chains
ترجمه فارسی عنوان
مشکلات دست یابی برای زنجیره مارکوف
کلمات کلیدی
روش های رسمی، مشکل اسکولم مشکل مثبت بررسی مدل احتمالاتی، زنجیره مارکوف،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the following decision problem: given a finite Markov chain with distinguished source and target states, and given a rational number r, does there exist an integer n such that the probability to reach the target from the source in n steps is r? This problem, which is not known to be decidable, lies at the heart of many model checking questions on Markov chains. We provide evidence of the hardness of the problem by giving a reduction from the Skolem Problem: a number-theoretic decision problem whose decidability has been open for many decades.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 155-158
نویسندگان
, , , ,