Distributed Artificial Intelligence: A Case Study of Implementations of a Parallel Algorithm Computing All Homomorphisms of Finite Automata
Bolesław Mikołajczak · Intelligent Information Systems · 2000
This paper is composed of two main parts: a description of a parallel algorithm computing the set of all state homomorphisms between two finite deterministic complete automata; experimental results of algorithm’s performance evaluation in several programming environments including transputer-based reconfigurable multicomputer architectures and distributed shared memory environment of Linda. We deal with two parallelization paradigms: data parallelism and process parallelism. The parallel algorithm computing all state homomorphisms of deterministic complete finite automata is composed of the following steps: selection of autonomous factors, computation of connected components, computation of graph-theoretic characteristics of connected components (set of generators, cycles, lengths of cycles, tails, and distances between vertices), and computation of the shapes of connected components (cycles, trees, and quasi-trees). Computations of connected components, graph-theoretic characteristics of connected components, and shapes of connected components are performed in parallel for both automata. Several necessary conditions are checked to reduce the exponential explosion in the number of candidate mappings. These conditions are: the cycle length divisibility condition, the vertex level condition, the vertex distance condition, and the function condition.