Determinizing Asynchronous Automata

Abstract

A concurrent version of a finite-state automaton is a set of processes that cooperate in processing letters of the input. Each letter read prompts some of the processes to synchronize and decide on a joint move according to a non-deterministic transition relation. Such automata are known as asynchronous automata.

The question whether these automata can be determinized while retaining the synchronization structure has already been answered is the positive, but indirectly, by Zielonka's Theorem. Unfortunately, this construction does not give an optimal solution.

In this paper we present an elementary proof, which generalizes the classic subset construction for finite-state automata. The proof uses in an essential way an earlier finite-state construction by Mukund and Sohoni for maintaining each process's latest knowledge about other processes.

Our construction is only double-exponential and thus is the first essentially to match the lower bound.

In conjunction with earlier results of Ochmanski and Pighizzini, our construction provides a new (and in a sense ''classical'') proof of Zielonka's theorem that every recognizable trace language is accepted by a deterministic asynchronous automaton whose structure precisely captures the independence relation of the given trace alphabet.