Giovanni in Paris

Multiautomata are collections of independent finite two-way deterministic automata that read synchronously the same input and are occasionally capable of broadcasting their current states. The reception of such a message affects the run of the automata by resetting them to some deterministically predetermined new state. An input is accepted if a specific automaton, say the first one of the collection, enters an accepting state. We consider the case where the input is on a unary alphabet which can be viewed as an integer. We show that if the number of messages broadcast during the computation is finite, then the set of inputs recognised is a regular language.