Determinizing Asynchronous Automata on Infinite Inputs
Nils Klarlund November 1995 |

## Abstract:Asynchrono us automata are a natural distributed machine model
for recognizing To handle Subsequently, Diekert and Muscholl solved the complementation problem by showing that with a Muller acceptance condition, deterministic automata suffice for recognizing -regular trace languages. However, a direct determinization procedure, extending the classical subset construction, has proved elusive. In this paper, we present a direct determinization procedure for Büchi asynchronous automata, which generalizes Safra's construction for sequential Büchi automata. As in the sequential case, the blow-up in the state space is essentially that of the underlying subset construction.
Available as |

Last modified: 2003-06-08 by webmaster.