BROADCAST AUTOMATA: A COMPUTATIONAL MODEL FOR MASSIVELY PARALLEL SYMBOLIC PROCESSING

Abstract

This paper presents a suitable formalism for the Broadcast Automata System, a model of massively parallel computation, introduced by the authors for prototyping of scientific applications. The model consists of a collection of identical entities, modelled as finite state automata, a global synchroniser providing coordination between the automata and a broadcast communication system, to which each automaton is connected, granting information exchange among the automata. The formalism is based on an extension of the classical formalism for finite state automata. The application to a case study concerning the recognition of first order propositional formulae is illustrated and the correctness proof is sketched.