NDLI: On Tractable Instances of Modular Supervisory Control

Content Provider	IEEE Xplore Digital Library
Author	Gummadi, R. Singh, N. Sreenivas, R.S.
Copyright Year	1963
Abstract	An instance of a modular supervisory control problem involves a plant automaton, described either as a monolithic, finite-state automaton (SUP1M), or as the synchronous product of several finite-state automata (SUPMM), along with a set of finite state, specification automata on a common alphabet. The marked language of the synchronous product of these automata represents the desired specification. A supervisory policy that solves the instance selectively disables certain events, based on the past history of event-occurrences, such that the marked behavior of the supervised system is a non-empty subset of the desired specification. Testing the existence of a supervisory policy for a variety of in stances of modular supervisory control is PSPACE-complete [1]. This problem remains intractable even when the plant is a monolithic finite state automaton and the specification automata are restricted to have only two states with a specific structure [2]. We refer to this intractable class as SU P1Ω in this paper. After introducing complement sets for events in a plant automaton, we identify a subclass of SUP1Ω that can be solved in polynomial time. Using this class as the base, inspired by a family of subclasses of SAT (cf. section 4.2, [3]) that can be solved in polynomial time [4], we develop a family of subclasses of SUP1Ω that can be solved in polynomial time. The results of this paper are also used to identify a polynomial time hierarchy for certain intractable subclasses of SUPMM identified in this paper.
Sponsorship	IEEE Control Systems Society
Starting Page	1621
Ending Page	1635
Page Count	15
File Size	677429
File Format	PDF
ISSN	00189286
Volume Number	56
Issue Number	7
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-07-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Automata Supervisory control Doped fiber amplifiers Polynomials Mathematical model supervisory control Discrete event systems
Content Type	Text
Resource Type	Article
Subject	Control and Systems Engineering Electrical and Electronic Engineering Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Some tractable supervisory control problems for discrete-event systems modeled by Buchi automata

Efficient Abstractions for the Supervisory Control of Modular Discrete Event Systems

Modular Supervisory Control and Hierarchical Supervisory Control of Fuzzy Discrete-Event Systems

On deadlock-free modular supervisory control of discrete-event systems

How Economic Inequality Has Increased by Tax Cuts? Power-Based Modular Supervisory Control of Discrete Event Systems

Decentralized supervisory control with conditional decisions: supervisor realization

The computational complexity of decentralized discrete-event control problems

A Framework for Compositional Synthesis of Modular Nonblocking Supervisors

Optimal Nonblocking Directed Control of Discrete Event Systems

On Tractable Instances of Modular Supervisory Control

Similar Documents

Some tractable supervisory control problems for discrete-event systems modeled by Buchi automata

Efficient Abstractions for the Supervisory Control of Modular Discrete Event Systems

Modular Supervisory Control and Hierarchical Supervisory Control of Fuzzy Discrete-Event Systems

On deadlock-free modular supervisory control of discrete-event systems

How Economic Inequality Has Increased by Tax Cuts? Power-Based Modular Supervisory Control of Discrete Event Systems

Decentralized supervisory control with conditional decisions: supervisor realization

The computational complexity of decentralized discrete-event control problems

A Framework for Compositional Synthesis of Modular Nonblocking Supervisors

Optimal Nonblocking Directed Control of Discrete Event Systems

On Tractable Instances of Modular Supervisory Control