An adaptive parallel algorithm for finite language decomposition

The computationally hard problem of finite language decomposition is investigated. A finite language L is decomposable if there are two languages L 1 and L 2 such that L = L 1 L 2 . Otherwise, L is prime. The main contribution of the paper is an adaptive parallel algorithm for finding all decomposit...

Full description

Saved in:
Bibliographic Details
Published in:Applied intelligence (Dordrecht, Netherlands) Netherlands), 2022-02, Vol.52 (3), p.3029-3050
Main Authors: Jastrzęb, Tomasz, Czech, Zbigniew J., Wieczorek, Wojciech
Format: Article
Language:English
Subjects:
Adaptive algorithms
Algorithms
Artificial Intelligence
Computer Science
Data acquisition
Decomposition
Languages
Machines
Manufacturing
Mechanical Engineering
Processes
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The computationally hard problem of finite language decomposition is investigated. A finite language L is decomposable if there are two languages L 1 and L 2 such that L = L 1 L 2 . Otherwise, L is prime. The main contribution of the paper is an adaptive parallel algorithm for finding all decompositions L 1 L 2 of L . The algorithm is based on an exhaustive search and incorporates several original methods for pruning the search space. Moreover, the algorithm is adaptive since it changes its behavior based on the runtime acquired data related to its performance. Comprehensive computational experiments on more than 4000 benchmark languages generated over alphabets of various sizes have been carried out. The experiments showed that by using the power of parallel computing the decompositions of languages containing more than 200000 words can be found. Decompositions of languages of that size have not been reported in the literature so far.
ISSN:0924-669X
1573-7497
DOI:10.1007/s10489-021-02488-y