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.2013.213
URN: urn:nbn:de:0030-drops-43742
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4374/
Go to the corresponding LIPIcs Volume Portal

Akshay, S. ; Dinca, Ionut ; Genest, Blaise ; Stefanescu, Alin

Implementing Realistic Asynchronous Automata

pdf-format:
15.pdf (0.6 MB)

Abstract

Zielonka's theorem, established 25 years ago, states that any regular
language closed under commutation is the language of an asynchronous
automaton (a tuple of automata, one per process, exchanging information when performing common actions). Since then, constructing asynchronous automata has been simplified and improved ([Cori/Métivier/Zielonka,1993],[Klarlund/Mukund/Sohoni,1994], [Diekert/Rozenberg,1995], [Genest/Muscholl,2006], [Genest/Gimbert/Muscholl/Walukiewicz,2010], [Baudru/Morin, 2006], [Baudru,2009], [Pighizzini,1993], [Stefanescu/Esparza/Muscholl,2003]).

We first survey these constructions and conclude that the synthesized
systems are not realistic in the following sense: existing constructions are either plagued by deadends, non deterministic guesses, or the acceptance condition or choice of actions are not distributed. We tackle this problem by giving (effectively testable) necessary and sufficient conditions which ensure that deadends can be avoided, acceptance condition and choices of action can be distributed, and determinism can be maintained. Finally, we implement our constructions, giving promising results when compared with the few other existing prototypes synthesizing asynchronous automata.

BibTeX - Entry

@InProceedings{akshay_et_al:LIPIcs:2013:4374,
  author =	{S. Akshay and Ionut Dinca and Blaise Genest and Alin Stefanescu},
  title =	{{Implementing Realistic Asynchronous Automata}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{213--224},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4374},
  URN =		{urn:nbn:de:0030-drops-43742},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.213},
  annote =	{Keywords: Asynchronous automata, Zielonka construction, Implementability}
}

Keywords: Asynchronous automata, Zielonka construction, Implementability
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

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