1 Search Results for "Dinca, Ionut"


Document
Implementing Realistic Asynchronous Automata

Authors: S. Akshay, Ionut Dinca, Blaise Genest, and Alin Stefanescu

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)


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.

Cite as

S. Akshay, Ionut Dinca, Blaise Genest, and Alin Stefanescu. Implementing Realistic Asynchronous Automata. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 213-224, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{akshay_et_al:LIPIcs.FSTTCS.2013.213,
  author =	{Akshay, S. and Dinca, Ionut and Genest, Blaise and Stefanescu, Alin},
  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 =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.213},
  URN =		{urn:nbn:de:0030-drops-43742},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.213},
  annote =	{Keywords: Asynchronous automata, Zielonka construction, Implementability}
}
  • Refine by Author
  • 1 Akshay, S.
  • 1 Dinca, Ionut
  • 1 Genest, Blaise
  • 1 Stefanescu, Alin

  • Refine by Classification

  • Refine by Keyword
  • 1 Asynchronous automata
  • 1 Implementability
  • 1 Zielonka construction

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail