Exponential Blow-up in Asynchronous Automata

Abstract

Zielonka introduced the concept of asynchronous automata to model some distributed systems [1]. Asynchronous automata are characterized by the languages they accept- regular trace languages [2][3][4]. A minimal DFA accepting a regular trace language is called a Diamond DFA. The characterization of asynchronous automata follows from algorithms converting Diamond DFAs to asynchronous automata accepting the same language [2][3][4]. A natural subject of interest is the lower and upper bounds on the size of minimal asynchronous automata accepting regular trace languages with respect to size of corresponding Diamond DFA and number of processes. The thesis studies upper bounds presented in [2][3][4]. A lower bound on locally rejecting asynchronous automata is studied from [4]. The lower bound result involves a set of regular trace languages- Path_n (n ∈ N).

The thesis contributes by providing lower and upper bounds on minimal ϵ-non-deterministic asynchronous automata accepting Path_n and by providing lower and upper bounds on minimal register asynchronous automata accepting Path_n. The thesis also contains an algorithm converting any asynchronous automata accepting Path_n to a locally rejecting asynchronous automata accepting Path_n.