A Simpler Alternative: Minimizing Transition Systems Modulo Alternating Simulation Equivalence

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

25 Downloads (Pure)

Abstract

This paper studies the reduction (abstraction) of finite-state transition systems for control synthesis problems. We revisit the notion of alternating simulation equivalence (ASE), a more relaxed condition than alternating bisimulations, to relate systems and their abstractions. As with alternating bisimulations, ASE preserves the property that the existence of a controller for the abstraction is necessary and sufficient for a controller to exist for the original system. Moreover, being a less stringent condition, ASE can reduce systems further to produce smaller abstractions. We provide an algorithm that produces minimal AS equivalent abstractions. The theoretical results are then applied to obtain (un)schedulability certificates of periodic event-triggered control systems sharing a communication channel. A numerical example illustrates the results.

Original languageEnglish
Title of host publicationProceedings of the 25th ACM International Conference on Hybrid Systems (HSCC 2022)
Subtitle of host publicationComputation and Control, Part of CPS-IoT Week 2022
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages11
ISBN (Electronic)978-1-4503-9196-2
DOIs
Publication statusPublished - 2022
Event25th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2022, held as part of the 15th Cyber Physical Systems and Internet-of-Things Week, CPS-IoT Week 2022 - Virtual, Online, Italy
Duration: 4 May 20226 May 2022

Conference

Conference25th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2022, held as part of the 15th Cyber Physical Systems and Internet-of-Things Week, CPS-IoT Week 2022
Country/TerritoryItaly
CityVirtual, Online
Period4/05/226/05/22

Keywords

  • Alternating Simulation
  • Controller Synthesis
  • Event Triggered Control
  • Minimization
  • Scheduling.

Fingerprint

Dive into the research topics of 'A Simpler Alternative: Minimizing Transition Systems Modulo Alternating Simulation Equivalence'. Together they form a unique fingerprint.

Cite this