The complexity of some reachability problems for a system on a finite group

Christian Golaszewski, Peter J. Ramadge

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)431-435
Number of pages5
JournalSystems and Control Letters
Issue number5
StatePublished - Jun 1989

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • General Computer Science
  • Mechanical Engineering
  • Electrical and Electronic Engineering


  • Discrete systems
  • complexity
  • groups
  • reachability


Dive into the research topics of 'The complexity of some reachability problems for a system on a finite group'. Together they form a unique fingerprint.

Cite this