License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.30
URN: urn:nbn:de:0030-drops-84142
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8414/
Go to the corresponding LIPIcs Volume Portal

Gimbert, Hugo

On the Control of Asynchronous Automata

pdf-format:
LIPIcs-FSTTCS-2017-30.pdf (0.6 MB)

Abstract

The decidability of the distributed version of the Ramadge and Wonham controller synthesis problem,
where both the plant and the controllers are modeled as asynchronous automata
and the controllers have causal memory
is a challenging open problem.
There exist three classes of plants for which the existence of a correct controller with causal memory has been shown decidable: when the dependency graph of actions is series-parallel,
when the processes are connectedly communicating and when the dependency graph of processes is a tree.
We design a class of plants, called decomposable games,
with a decidable controller synthesis problem.
This provides
a unified proof of the three existing decidability results
as well as new examples of decidable plants.

BibTeX - Entry

@InProceedings{gimbert:LIPIcs:2018:8414,
  author =	{Hugo Gimbert},
  title =	{{On the Control of Asynchronous Automata}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Satya Lokam and R. Ramanujam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8414},
  URN =		{urn:nbn:de:0030-drops-84142},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.30},
  annote =	{Keywords: Asynchronous automata,  Controller synthesis}
}

Keywords: Asynchronous automata, Controller synthesis
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI