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

doi:10.1016/j.automatica.2017.03.023

	The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete
	Zhang, Kuize 1,2,3
刊名	AUTOMATICA
	2017-07-01
卷号	81 页码:217-220
关键词	Discrete event system Finite automaton Weak (periodic) detectability PSPACE-hardness
ISSN号	0005-1098
DOI	10.1016/j.automatica.2017.03.023
英文摘要	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.
语种	英语
出版者	PERGAMON-ELSEVIER SCIENCE LTD
WOS记录号	WOS:000403513900025
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/25800]
专题	中国科学院数学与系统科学研究院
通讯作者	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.