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

Christian Golaszewski, Peter Jeffrey Ramadge

Research output: Contribution to journalArticle

3 Scopus citations

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.

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

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science(all)
  • Mechanical Engineering
  • Electrical and Electronic Engineering

Fingerprint 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