Recognizable trace languages, distributed automata and the distribution problem (Q1323363)

We introduce new finite state ``parallel machines'', the \((\mathbb{N}\)- )distributed automata, for trace languages. We prove that these machines give a new characterization of recognizable trace languages: a trace language is recognizable if and only if it is recognized by a \((\mathbb{N}\)- )distributed automaton. At last, we show how the classical problem of distribution of uninterpreted tasks on several processors can be straightforward modelized by recognizable trace languages and solved using \((\mathbb{N}\)-)distributed automata.