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!
cited_by
cites cdi_FETCH-LOGICAL-c314t-4b81585e2e87f7639f75ddc6ce26a5bd69a4887bff83f64b69e809d3cd8d67133
container_end_page 3050
container_issue 3
container_start_page 3029
container_title Applied intelligence (Dordrecht, Netherlands)
container_volume 52
creator Jastrzęb, Tomasz
Czech, Zbigniew J.
Wieczorek, Wojciech
description 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.
doi_str_mv 10.1007/s10489-021-02488-y
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2627004613</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2627004613</sourcerecordid><originalsourceid>FETCH-LOGICAL-c314t-4b81585e2e87f7639f75ddc6ce26a5bd69a4887bff83f64b69e809d3cd8d67133</originalsourceid><addsrcrecordid>eNp9kMtKxDAUhoMoOF5ewFXAdTS35rJzGLzBgBsFdyFtkpqh09SkI8zbW6eCOxeHs_m__xw-AK4IviEYy9tCMFcaYUqm4Uqh_RFYkEoyJLmWx2CBNeVICP1-Cs5K2WCMGcNkAe6WPbTODmP88nCw2Xad76Dt2pTj-LGFIWUYYh9HDzvbtzvbeuh8k7ZDKnGMqb8AJ8F2xV_-7nPw9nD_unpC65fH59VyjRpG-Ih4rUilKk-9kkEKpoOsnGtE46mwVe2EttPbsg5BsSB4LbRXWDvWOOWEJIydg-u5d8jpc-fLaDZpl_vppKGCSoy5OKTonGpyKiX7YIYctzbvDcHmx5SZTZnJlDmYMvsJYjNUpnDf-vxX_Q_1DfjrbI8</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2627004613</pqid></control><display><type>article</type><title>An adaptive parallel algorithm for finite language decomposition</title><source>ABI/INFORM Global (ProQuest)</source><source>Springer Nature</source><creator>Jastrzęb, Tomasz ; Czech, Zbigniew J. ; Wieczorek, Wojciech</creator><creatorcontrib>Jastrzęb, Tomasz ; Czech, Zbigniew J. ; Wieczorek, Wojciech</creatorcontrib><description>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.</description><identifier>ISSN: 0924-669X</identifier><identifier>EISSN: 1573-7497</identifier><identifier>DOI: 10.1007/s10489-021-02488-y</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Adaptive algorithms ; Algorithms ; Artificial Intelligence ; Computer Science ; Data acquisition ; Decomposition ; Languages ; Machines ; Manufacturing ; Mechanical Engineering ; Processes</subject><ispartof>Applied intelligence (Dordrecht, Netherlands), 2022-02, Vol.52 (3), p.3029-3050</ispartof><rights>The Author(s) 2021</rights><rights>The Author(s) 2021. This work is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c314t-4b81585e2e87f7639f75ddc6ce26a5bd69a4887bff83f64b69e809d3cd8d67133</cites><orcidid>0000-0003-3191-9151 ; 0000-0002-6521-9420 ; 0000-0002-7854-9058</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2627004613/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2627004613?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11686,27922,27923,36058,44361,74665</link.rule.ids></links><search><creatorcontrib>Jastrzęb, Tomasz</creatorcontrib><creatorcontrib>Czech, Zbigniew J.</creatorcontrib><creatorcontrib>Wieczorek, Wojciech</creatorcontrib><title>An adaptive parallel algorithm for finite language decomposition</title><title>Applied intelligence (Dordrecht, Netherlands)</title><addtitle>Appl Intell</addtitle><description>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.</description><subject>Adaptive algorithms</subject><subject>Algorithms</subject><subject>Artificial Intelligence</subject><subject>Computer Science</subject><subject>Data acquisition</subject><subject>Decomposition</subject><subject>Languages</subject><subject>Machines</subject><subject>Manufacturing</subject><subject>Mechanical Engineering</subject><subject>Processes</subject><issn>0924-669X</issn><issn>1573-7497</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp9kMtKxDAUhoMoOF5ewFXAdTS35rJzGLzBgBsFdyFtkpqh09SkI8zbW6eCOxeHs_m__xw-AK4IviEYy9tCMFcaYUqm4Uqh_RFYkEoyJLmWx2CBNeVICP1-Cs5K2WCMGcNkAe6WPbTODmP88nCw2Xad76Dt2pTj-LGFIWUYYh9HDzvbtzvbeuh8k7ZDKnGMqb8AJ8F2xV_-7nPw9nD_unpC65fH59VyjRpG-Ih4rUilKk-9kkEKpoOsnGtE46mwVe2EttPbsg5BsSB4LbRXWDvWOOWEJIydg-u5d8jpc-fLaDZpl_vppKGCSoy5OKTonGpyKiX7YIYctzbvDcHmx5SZTZnJlDmYMvsJYjNUpnDf-vxX_Q_1DfjrbI8</recordid><startdate>20220201</startdate><enddate>20220201</enddate><creator>Jastrzęb, Tomasz</creator><creator>Czech, Zbigniew J.</creator><creator>Wieczorek, Wojciech</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>C6C</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>8AL</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PSYQQ</scope><scope>PTHSS</scope><scope>Q9U</scope><orcidid>https://orcid.org/0000-0003-3191-9151</orcidid><orcidid>https://orcid.org/0000-0002-6521-9420</orcidid><orcidid>https://orcid.org/0000-0002-7854-9058</orcidid></search><sort><creationdate>20220201</creationdate><title>An adaptive parallel algorithm for finite language decomposition</title><author>Jastrzęb, Tomasz ; Czech, Zbigniew J. ; Wieczorek, Wojciech</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c314t-4b81585e2e87f7639f75ddc6ce26a5bd69a4887bff83f64b69e809d3cd8d67133</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Adaptive algorithms</topic><topic>Algorithms</topic><topic>Artificial Intelligence</topic><topic>Computer Science</topic><topic>Data acquisition</topic><topic>Decomposition</topic><topic>Languages</topic><topic>Machines</topic><topic>Manufacturing</topic><topic>Mechanical Engineering</topic><topic>Processes</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Jastrzęb, Tomasz</creatorcontrib><creatorcontrib>Czech, Zbigniew J.</creatorcontrib><creatorcontrib>Wieczorek, Wojciech</creatorcontrib><collection>SpringerOpen</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Computing Database (Alumni Edition)</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Global (ProQuest)</collection><collection>Computing Database</collection><collection>Engineering Database</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>ProQuest One Psychology</collection><collection>Engineering Collection</collection><collection>ProQuest Central Basic</collection><jtitle>Applied intelligence (Dordrecht, Netherlands)</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Jastrzęb, Tomasz</au><au>Czech, Zbigniew J.</au><au>Wieczorek, Wojciech</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>An adaptive parallel algorithm for finite language decomposition</atitle><jtitle>Applied intelligence (Dordrecht, Netherlands)</jtitle><stitle>Appl Intell</stitle><date>2022-02-01</date><risdate>2022</risdate><volume>52</volume><issue>3</issue><spage>3029</spage><epage>3050</epage><pages>3029-3050</pages><issn>0924-669X</issn><eissn>1573-7497</eissn><abstract>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.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s10489-021-02488-y</doi><tpages>22</tpages><orcidid>https://orcid.org/0000-0003-3191-9151</orcidid><orcidid>https://orcid.org/0000-0002-6521-9420</orcidid><orcidid>https://orcid.org/0000-0002-7854-9058</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0924-669X
ispartof Applied intelligence (Dordrecht, Netherlands), 2022-02, Vol.52 (3), p.3029-3050
issn 0924-669X
1573-7497
language eng
recordid cdi_proquest_journals_2627004613
source ABI/INFORM Global (ProQuest); Springer Nature
subjects Adaptive algorithms
Algorithms
Artificial Intelligence
Computer Science
Data acquisition
Decomposition
Languages
Machines
Manufacturing
Mechanical Engineering
Processes
title An adaptive parallel algorithm for finite language decomposition
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-13T12%3A04%3A33IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=An%20adaptive%20parallel%20algorithm%20for%20finite%20language%20decomposition&rft.jtitle=Applied%20intelligence%20(Dordrecht,%20Netherlands)&rft.au=Jastrz%C4%99b,%20Tomasz&rft.date=2022-02-01&rft.volume=52&rft.issue=3&rft.spage=3029&rft.epage=3050&rft.pages=3029-3050&rft.issn=0924-669X&rft.eissn=1573-7497&rft_id=info:doi/10.1007/s10489-021-02488-y&rft_dat=%3Cproquest_cross%3E2627004613%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c314t-4b81585e2e87f7639f75ddc6ce26a5bd69a4887bff83f64b69e809d3cd8d67133%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2627004613&rft_id=info:pmid/&rfr_iscdi=true