A Simpler Alternative

Minimizing Transition Systems Modulo Alternating Simulation Equivalence

Conference paper (2022)

Authors

G. de Albuquerque Gleizer Team Tamas Keviczky - Mechanical, Maritime and Materials Engineering
K.N. Madnani Team Manuel Mazo Jr - Mechanical, Maritime and Materials Engineering
M. Mazo Team Manuel Mazo Jr - Mechanical, Maritime and Materials Engineering
Research Group
Team Manuel Mazo Jr (Mechanical, Maritime and Materials Engineering) (TU Delft)
Copyright: © 2022 G. de Albuquerque Gleizer, K.N. Madnani, M. Mazo
DOI: https://doi.org/10.1145/3501710.3519534
More Info
expand_more

Published Date

2022

Language

English

Faculty

Mechanical, Maritime and Materials Engineering

Department

Delft Center for Systems and Control

Research Group

Team Manuel Mazo Jr

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.