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

Christian Golaszewski; Peter J. Ramadge

doi:10.1016/0167-6911(89)90079-0

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

Christian Golaszewski, Peter J. Ramadge

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	431-435
Number of pages	5
Journal	Systems and Control Letters
Volume	12
Issue number	5
DOIs	https://doi.org/10.1016/0167-6911(89)90079-0
State	Published - Jun 1989

All Science Journal Classification (ASJC) codes

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

Keywords

Discrete systems
complexity
groups
reachability

Access to Document

10.1016/0167-6911(89)90079-0

Cite this

@article{b2a4e5b06cae49cbabeb03df841b3889,

title = "The complexity of some reachability problems for a system on a finite group",

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.",

keywords = "Discrete systems, complexity, groups, reachability",

author = "Christian Golaszewski and Ramadge, {Peter J.}",

note = "Funding Information: The state set of Gi is the cyclic group of integers under addition mod ni, and its state trajectory is periodic with period n i. Let G(p, n) be the prod- * Research supported in part by the National Science Founda-tion through grant ECS-8715217 and by an IBM Faculty Development Award.",

year = "1989",

month = jun,

doi = "10.1016/0167-6911(89)90079-0",

language = "English (US)",

volume = "12",

pages = "431--435",

journal = "Systems and Control Letters",

issn = "0167-6911",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

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

AU - Golaszewski, Christian

AU - Ramadge, Peter J.

N1 - Funding Information: The state set of Gi is the cyclic group of integers under addition mod ni, and its state trajectory is periodic with period n i. Let G(p, n) be the prod- * Research supported in part by the National Science Founda-tion through grant ECS-8715217 and by an IBM Faculty Development Award.

PY - 1989/6

Y1 - 1989/6

N2 - 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.

AB - 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.

KW - Discrete systems

KW - complexity

KW - groups

KW - reachability

UR - http://www.scopus.com/inward/record.url?scp=0024680459&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024680459&partnerID=8YFLogxK

U2 - 10.1016/0167-6911(89)90079-0

DO - 10.1016/0167-6911(89)90079-0

M3 - Article

AN - SCOPUS:0024680459

SN - 0167-6911

VL - 12

SP - 431

EP - 435

JO - Systems and Control Letters

JF - Systems and Control Letters

IS - 5

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this