Constructing Optimal Zielonka Automaton
Institute for INFOCOMM Research, Singapore.
The well-known algorithm of Zielonka (and all its variants and improvements) describes how to transform automatically a sequential automaton into a deterministic asynchronous automaton with local rejection, simply called Zielonka Automaton in the following. In this work, we improve yet again the construction of Zielonka automata from deterministic finite state automaton. Our construction improves the well-known construction in that the size of the asynchronous automaton is simply exponential only in the number of processes, and polynomial size if the number of processes is fixed. In contrast, original Zielonka's algorithm gives an asynchronous automaton that is doubly exponential in the number of processes (and simply exponential in the size of the automaton), one improvement gives a Zielonka automaton of size doubly exponential in the number of processes, and another improvement gives a Zielonka automaton of size exponential in the size of the automaton. We prove that this construction is optimal in that the exponential blow-up in the number of processes and alphabet size is unavoidable, giving the first known lower bound on Zielonka (Asynchronous) automata.
Joint work with Hugo Gimbert, Anca Muscholl and Igor Walukiewicz.