An algorithm for the decomposition of finite languages
Wojciech Wieczorek · Logic Journal of IGPL · 2009
In this paper, an algorithm for the decomposition of a finite language is presented. The goal is to represent a finite language as a product (catenation) of two languages. This problem is thought to be intractable, although its NP-hardness has not been proven. The algorithm is based on checking through some subsets of the states of a minimal acyclic DFA. We also investigate two additional algorithms: the first is based on the use of integer linear programming, and the second is based on finding cliques in a graph. It appears that the latter approaches are inappropriate in terms of time consumption. The experiments have been performed for dozens of languages, and our results are reported.