Department of Electrical Engineering, Princeton University, Princeton, NJ 08544, U.S.A.
Abstract:
We consider a system defined as the product of a finite set of periodic systems on cyclic groups. It is of interest to determine if certain subgroups and unions of subgroups of the state set are reachable from a specified initial state, and in particular to determine the computational complexity of verifying such reachability. These questions are motivated by certain problems that arise in the modelling and control of discrete event systems and certain forms of periodic scheduling. Our main result is that deciding whether or not the union of a certain set of subgroups is reachable or not is NP-complete.