A space-efficient simulation algorithm on probabilistic automata

ISCAS OpenIR

	A space-efficient simulation algorithm on probabilistic automata
	Zhang, LJ; Jansen, DN
	2016
发表期刊	INFORMATION AND COMPUTATION
ISSN	0890-5401
卷号	249 页码:138-159
摘要	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.
收录类别	SCI
关键词	Probabilistic Automata Simulation Partition Refinement Decision Algorithm
部门归属	Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China. Radboud Univ Nijmegen, Model Based Syst Dev, Nijmegen, Netherlands.
语种	英语
WOS记录号	WOS:000381688200007
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/17310
专题	中国科学院软件研究所
推荐引用方式 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.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
1-s2.0-S089054011630（735KB）			开放获取	使用许可	请求全文