Institutional Repository
| A space-efficient simulation algorithm on probabilistic automata | |
| Zhang, LJ; Jansen, DN | |
| 2016 | |
| Source | INFORMATION AND COMPUTATION
 |
| ISSN | 0890-5401 |
| Volume | 249Pages:138-159 |
| English Abstract | 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). (C) 2016 Elsevier Inc. All rights reserved.; 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). (C) 2016 Elsevier Inc. All rights reserved. |
| Indexed Type | SCI |
| Keyword | Probabilistic Automata Simulation Partition Refinement Decision Algorithm |
| Department | Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China. Radboud Univ Nijmegen, Model Based Syst Dev, Nijmegen, Netherlands. |
| Language | 英语 |
| WOS ID | WOS:000381688200007 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/17310 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Zhang, LJ,Jansen, DN. A space-efficient simulation algorithm on probabilistic automata[J]. INFORMATION AND COMPUTATION,2016,249:138-159. |
| APA | Zhang, LJ,&Jansen, DN.(2016).A space-efficient simulation algorithm on probabilistic automata.INFORMATION AND COMPUTATION,249,138-159. |
| MLA | Zhang, LJ,et al."A space-efficient simulation algorithm on probabilistic automata".INFORMATION AND COMPUTATION 249(2016):138-159. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| 1-s2.0-S089054011630（735KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment