Polynomial Synthesis of Asynchronous Automata
<|reference_start|>Polynomial Synthesis of Asynchronous Automata: Zielonka's theorem shows that each regular set of Mazurkiewicz traces can be implemented as a system of synchronized processes with a distributed control structure called asynchronous automaton. This paper gives a polynomial algorithm for the synthesis of a non-deterministic asynchronous automaton from a regular Mazurkiewicz trace language. This new construction is based on an unfolding approach that improves the complexity of Zielonka's and Pighizzini's techniques in terms of the number of states.<|reference_end|>
@article{baudru2005polynomial,
    title={Polynomial Synthesis of Asynchronous Automata},
    author={Nicolas Baudru (LIF), R'emi Morin (LIF)},
    journal={arXiv preprint arXiv:cs/0506096},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0506096},
    primaryClass={cs.CC cs.LO}
}