Lossless Event Compression of Discrete Event Systems

• 成果类型: Article
• 署名作者: Cao, Lin; Shu, Shaolong; Lin, Feng; Zhou, Lei
• 署名单位: Tongji University; Wayne State University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3003068
• 发表日期: 2021
• 页码: 2312-2318
• 关键词: Discrete-event systems; Protocols; Automata; Dictionaries; Sensor systems; computational complexity; big data; discrete event systems; lossless event compression; MONOTONICITY; storage resource; Recoverability

摘要

This article investigates the lossless event compression problem of discrete event systems which is, given a discrete event system and a source string generated by it, to find a minimal recoverable compressed string by removing as many events as possible. In order for the problem to be well post, two compression protocols are introduced. One requires that the last event is always kept. The other requires that, for any loop substring, at least one event is kept. We say a compressed string is recoverable if we can uniquely determine the source string based on the knowledge of the given discrete event system. We first construct an automaton to present all the possible source strings for a given compressed string. Based on the automaton, an algorithm is proposed to check whether the given compressed string is recoverable or not. We then propose an algorithm to calculate a minimal recoverable compressed string for a source string. The compressed string satisfies monotonicity which can significantly reduce the computational complexity of the algorithm. Finally, we use a practical example to illustrate these results.