English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Compositional Synthesis of Finite State Abstractions

MPS-Authors
/persons/resource/persons144534

Majumdar,  Rupak
Group R. Majumdar, Max Planck Institute for Software Systems, Max Planck Society;

/persons/resource/persons204254

Mallik,  Kaushik
Group R. Majumdar, Max Planck Institute for Software Systems, Max Planck Society;

/persons/resource/persons188484

Schmuck,  Anne-Kathrin
Group R. Majumdar, Max Planck Institute for Software Systems, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:1612.08515.pdf
(Preprint), 265KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Majumdar, R., Mallik, K., & Schmuck, A.-K. (2016). Compositional Synthesis of Finite State Abstractions. Retrieved from http://arxiv.org/abs/1612.08515.


Cite as: https://hdl.handle.net/11858/00-001M-0000-002C-EB9C-5
Abstract
Controller synthesis techniques for continuous systems with respect to temporal logic specifications typically use a finite-state symbolic abstraction of the system model. Constructing this abstraction for the entire system is computationally expensive, and does not exploit natural decompositions of many systems into interacting components. We describe a methodology for compositional symbolic abstraction to help scale controller synthesis for temporal logic to larger systems. We introduce a new relation, called (approximate) disturbance bisimulation, as the basis for compositional symbolic abstractions. Disturbance bisimulation strengthens the standard approximate alternating bisimulation relation used in control, and extends naturally to systems which are composed of sub-components possibly connected in feedback; disturbance bisimulation handles the feedback signals as disturbances. After proving this composability of disturbance bisimulation for metric systems, we show how one can construct finite-state abstractions compositionally for each component, so that the abstractions are simultaneously disturbance bisimilar to their continuous counterparts. Combining these two results, we can compositionally abstract a network system in a modular way while ensuring that the final composed abstraction is distrubance bisimilar to the original system. We discuss how we get a compositional controller synthesis methodology for networks of such systems against local temporal specifications as a by-product of our construction.