The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete

doi:10.1016/j.automatica.2017.03.023

CSpace

	The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete
	Zhang, Kuize 1,2,3
	2017-07-01
发表期刊	AUTOMATICA
ISSN	0005-1098
卷号	81 页码:217-220
摘要	In Shu and Lin, 2011, exponential time (actually polynomial space) algorithms for determining the weak detectability and weak periodic detectability of nondeterministic discrete event systems (DESs) are designed. In this paper, we prove that the problems of determining the weak detectability and weak periodic detectability of deterministic DESs are both PSPACE-hard (hence PSPACE-complete). Then as corollaries, the problems of determining the weak detectability and weak periodic detectability of nondeterministic DESs are also PSPACE-hard (hence PSPACE-complete). (C) 2017 Elsevier Ltd. All rights reserved.
关键词	Discrete event system Finite automaton Weak (periodic) detectability PSPACE-hardness
DOI	10.1016/j.automatica.2017.03.023
语种	英语
资助项目	National Natural Science Foundation of China[61603109] ; Natural Science Foundation of Heilongjiang Province of China[LC2016023]
WOS研究方向	Automation & Control Systems ; Engineering
WOS类目	Automation & Control Systems ; Engineering, Electrical & Electronic
WOS记录号	WOS:000403513900025
出版者	PERGAMON-ELSEVIER SCIENCE LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/25801
专题	中国科学院数学与系统科学研究院
通讯作者	Zhang, Kuize
作者单位	1.Harbin Engn Univ, Coll Automat, Harbin 150001, Peoples R China 2.Chinese Acad Sci, Inst Syst Sci, Beijing 100190, Peoples R China 3.Tech Univ Munich, Dept Elect & Comp Engn, D-80333 Munich, Germany
推荐引用方式 GB/T 7714	Zhang, Kuize. The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete[J]. AUTOMATICA,2017,81:217-220.
APA	Zhang, Kuize.(2017).The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete.AUTOMATICA,81,217-220.
MLA	Zhang, Kuize."The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete".AUTOMATICA 81(2017):217-220.