کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426977 | 686409 | 2016 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A space-efficient simulation algorithm on probabilistic automata
ترجمه فارسی عنوان
یک الگوریتم شبیه سازی فضای کارآمد در اتوماتای احتمالاتی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اتوماتای احتمالاتی؛ شبیه سازی؛ پالایش پارتیشن؛ الگوریتم تصمیم گیری
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In the context of probabilistic automata, time-efficient algorithms for simulation have been proposed lately. The space complexity thereof is quadratic in the size of the transition relation, thus space requirements often become the practical bottleneck. In this paper, we propose a space-efficient algorithm for computing simulation based on partition refinement. Experimental evidence is given showing that not only the space efficiency is improved drastically: The experiments often require orders of magnitude less time. In practice, they are even faster than the (asymptotically) optimal algorithm by Crafa and Ranzato (2012).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 249, August 2016, Pages 138–159
Journal: Information and Computation - Volume 249, August 2016, Pages 138–159
نویسندگان
Lijun Zhang, David N. Jansen,