Optimal Zielonka-Type Construction of Deterministic Asynchronous AutomataReport as inadecuate

Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata - Download this document for free, or read online. Document in PDF available to download.

1 IPAL - Image & Pervasive Access Lab 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : Asynchronous automata are parallel compositions of finite-state processes synchronizing over shared variables. A deep theorem due to Zielonka says that every regular trace language can be represented by a deterministic asynchronous automaton. In this paper we improve the construction, in that the size of the obtained asynchronous automaton is polynomial in the size of a given DFA and simply exponential in the number of processes. We show that our construction is optimal within the class of automata produced by Zielonka-type constructions. In particular, we provide the first non trivial lower bound on the size of asynchronous automata.

Author: Blaise Genest - Hugo Gimbert - Anca Muscholl - Igor Walukiewicz -

Source: https://hal.archives-ouvertes.fr/


Related documents