Decidability and Complexity Analysis of Forbidden State Problems for Discrete Event Systems
Resource
International Journal of Foundations of Computer Science, 19(4), 999-1013
Journal
International Journal of Foundations of Computer Science
Journal Volume
19
Journal Issue
4
Pages
999-1013
Date Issued
2008-01
Author(s)
Abstract
The conventional forbidden state problem for discrete event systems is concerned with the issue of synthesizing a maximally permissive control policy to prevent a discrete event system from reaching any forbidden state during the course of its computation. In this paper, we regard the forbidden state problem as a decision problem, and investigate the decidability/complexity issue of the problem under two new types of control policies, namely, non-blocking and fair policies, for finite state systems and Petri nets.
SDGs
Type
journal article