A Parallel Algorithm for Decomposition of Finite Languages

摘要

The paper deals with the problem of finite languages decomposition, which is believed to be computationally hard. Our objective is to propose an improved parallel algorithm finding all non-trivial decompositions of a finite language L, provided that they exist. The paper introduces a novel method of pruning a solution space by defining locally significant states of an automaton A accepting language L. It also proposes an adaptive way for adjusting the algorithm parameters, which has not been studied yet in the past. The performance of the algorithm is experimentally verified on a set of large languages and the results are reported. The algorithm proves to be successful in finding the decompositions of selected languages in a reasonable amount of time.