{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:24:25Z","timestamp":1740122665386,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T00:00:00Z","timestamp":1624665600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T00:00:00Z","timestamp":1624665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2016\/21\/B\/ST6\/02158"],"award-info":[{"award-number":["2016\/21\/B\/ST6\/02158"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007835","name":"Politechnika \u015al&aogon;ska","doi-asserted-by":"publisher","award":["SUT grant for maintaining and developing research potential"],"award-info":[{"award-number":["SUT grant for maintaining and developing research potential"]}],"id":[{"id":"10.13039\/501100007835","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Intell"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The computationally hard problem of finite language decomposition is investigated. A finite language <jats:italic>L<\/jats:italic> is decomposable if there are two languages <jats:italic>L<\/jats:italic><jats:sub>1<\/jats:sub> and <jats:italic>L<\/jats:italic><jats:sub>2<\/jats:sub> such that <jats:italic>L<\/jats:italic> = <jats:italic>L<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>L<\/jats:italic><jats:sub>2<\/jats:sub>. Otherwise, <jats:italic>L<\/jats:italic> is prime. The main contribution of the paper is an adaptive parallel algorithm for finding all decompositions <jats:italic>L<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>L<\/jats:italic><jats:sub>2<\/jats:sub> of <jats:italic>L<\/jats:italic>. 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.<\/jats:p>","DOI":"10.1007\/s10489-021-02488-y","type":"journal-article","created":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T00:02:13Z","timestamp":1624665733000},"page":"3029-3050","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An adaptive parallel algorithm for finite language decomposition"],"prefix":"10.1007","volume":"52","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7854-9058","authenticated-orcid":false,"given":"Tomasz","family":"Jastrz\u0119b","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6521-9420","authenticated-orcid":false,"given":"Zbigniew J.","family":"Czech","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3191-9151","authenticated-orcid":false,"given":"Wojciech","family":"Wieczorek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,26]]},"reference":[{"key":"2488_CR1","unstructured":"Sieder P (2019) A lower bound for primality of finite languages. CoRR arXiv:1902.06253"},{"issue":"2","key":"2488_CR2","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s11704-010-0154-8","volume":"4","author":"M Marin","year":"2010","unstructured":"Marin M, Kutsia T (2010) On the computation of quotients and factors of regular languages. Front Comput Sci China 4(2):173\u2013184","journal-title":"Front Comput Sci China"},{"key":"2488_CR3","doi-asserted-by":"crossref","unstructured":"Afonin S, Golomazov D (2009) Minimal union-free decompositions of regular languages. In: Language and Automata Theory and Applications, Third International Conference, LATA 2009. Proceedings, Tarragona, pp 83\u201392","DOI":"10.1007\/978-3-642-00982-2_7"},{"key":"2488_CR4","doi-asserted-by":"crossref","unstructured":"Wieczorek W, Nowakowski A (2015) Grammatical inference for the construction of opening books. In: 2015 Second International Conference on Computer Science, Computer Engineering, and Social Media (CSCESM). IEEE, pp 19\u201322","DOI":"10.1109\/CSCESM.2015.7331821"},{"key":"2488_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ifacol.2018.06.273","volume":"51","author":"HJ Bravo","year":"2018","unstructured":"Bravo HJ, Pena PN, Alves LVR, Takahashi RHC (2018) Factorization-based approach for computing a minimum makespan controllable sublanguage. IFAC-PapersOnLine 51:19\u201324","journal-title":"IFAC-PapersOnLine"},{"issue":"5","key":"2488_CR6","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1142\/S0129054111008647","volume":"22","author":"YS Han","year":"2011","unstructured":"Han Y S, Salomaa K (2011) Overlap-free languages and solid codes. Int J Found Comput Sci 22(5):1197\u20131209","journal-title":"Int J Found Comput Sci"},{"issue":"4","key":"2488_CR7","first-page":"351","volume":"29","author":"KV Hung","year":"2013","unstructured":"Hung K V (2013) A prime decomposition algorithm for supercodes. J Comput Sci Cybern 29 (4):351\u2013357","journal-title":"J Comput Sci Cybern"},{"issue":"6","key":"2488_CR8","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1142\/S0129054103002151","volume":"14","author":"J Czyzowicz","year":"2003","unstructured":"Czyzowicz J, Fraczak W, Pelc A, Rytter W (2003) Linear-time prime decomposition of regular prefix codes. Int J Found Comput Sci 14(6):1019\u20131032","journal-title":"Int J Found Comput Sci"},{"issue":"2","key":"2488_CR9","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1142\/S0129054106003887","volume":"17","author":"Y-S Han","year":"2006","unstructured":"Han Y-S, Wang Y, Wood D (2006) Infix-free regular expressions and languages. Int J Found Comput Sci 17(2):379\u2013393","journal-title":"Int J Found Comput Sci"},{"issue":"4","key":"2488_CR10","first-page":"441","volume":"81","author":"Y-S Han","year":"2007","unstructured":"Han Y-S, Wood D (2007) Outfix-free regular languages and prime outfix-free decomposition. Fund Inf 81(4):441\u2013457","journal-title":"Fund Inf"},{"key":"2488_CR11","doi-asserted-by":"crossref","unstructured":"Domaratzki M, Salomaa K (2011) On language decompositions and primality. In: Calude C S, Rozenberg G, Salomaa A (eds) Language and Automata Theory and Applications, LNCS, vol 6570. Springer, Berlin, pp 63\u201375","DOI":"10.1007\/978-3-642-19391-0_5"},{"key":"2488_CR12","doi-asserted-by":"crossref","unstructured":"Salomaa A, Salomaa K, Yu S (2008) Length codes, products of languages and primality. In: Martin-Vide C, Otto F, Fernau H (eds) Language and Automata Theory and Applications, LNCS, vol 5196. Springer, Berlin, pp 476\u2013486","DOI":"10.1007\/978-3-540-88282-4_43"},{"issue":"1-2","key":"2488_CR13","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2007.01.013","volume":"376","author":"Y-S Han","year":"2007","unstructured":"Han Y-S, Salomaa A, Salomaa K, Wood D, Yu S (2007) On the existence of prime decompositions. Theor Comput Sci 376(1-2):60\u201369","journal-title":"Theor Comput Sci"},{"key":"2488_CR14","first-page":"339","volume":"15","author":"A Mateescu","year":"2002","unstructured":"Mateescu A, Salomaa A, Yu S (2002) Factorizations of languages and commutativity conditions. Acta Cybern 15:339\u2013351","journal-title":"Acta Cybern"},{"key":"2488_CR15","doi-asserted-by":"crossref","unstructured":"Salomaa A, Yu S (2000) On the decomposition of finite languages. In: Rozenberg G, Thomas W (eds) Developments in Language Theory: Foundations, Applications and Perspectives. World Scientific Publishing, Singapore, pp 22\u201331","DOI":"10.1142\/9789812792464_0003"},{"key":"2488_CR16","unstructured":"Mateescu A, Salomaa A, Yu S (1998) On the decomposition of finite languages. Turku Centre for Computer Science"},{"issue":"3","key":"2488_CR17","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1093\/jigpal\/jzp032","volume":"18","author":"W Wieczorek","year":"2009","unstructured":"Wieczorek W (2009) An algorithm for the decomposition of finite languages. Log J IGPL 18 (3):355\u2013366","journal-title":"Log J IGPL"},{"key":"2488_CR18","unstructured":"Wieczorek W (2009) Metaheuristics for the decomposition of finite languages. In: K\u0142opotek M A, Przepi\u00f3rkowski A, Wierzcho\u0144 S T, Trojanowski K (eds) Recent Advances in Intelligent Information Systems. Akademicka Oficyna Wydawnicza EXIT, Warszawa, pp 495\u2013505"},{"issue":"4","key":"2488_CR19","first-page":"5","volume":"35","author":"T Jastrza\u0327b","year":"2014","unstructured":"Jastrza\u0327b T, Czech Z J (2014) A parallel algorithm for the decomposition of finite languages. Studia Informatica 35(4):5\u201316","journal-title":"Studia Informatica"},{"key":"2488_CR20","unstructured":"Jastrza\u0327b T, Czech Z J, Wieczorek W (2015) A parallel algorithm for decomposition of finite languages. In: Joubert G R, Leather H, Parsons M, Peters F J, Sawyer M (eds) Parallel Computing: On the Road to Exascale. IOS Press, Netherlands, pp 401\u2013410"},{"key":"2488_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139194655","volume-title":"Grammatical inference: Learning automata and grammars","author":"C de la Higuera","year":"2010","unstructured":"de la Higuera C (2010) Grammatical inference: Learning automata and grammars. Cambridge University Press, New York"},{"key":"2488_CR22","unstructured":"Hopcroft J E, Motwani R, Ullman J D (2013) Introduction to automata theory, languages, and computation, 3rd ed. Pearson international, Addison-Wesley"},{"key":"2488_CR23","doi-asserted-by":"crossref","unstructured":"Martens W, Niewerth M, Schwentick T (2010) Schema design for XML repositories: complexity and tractability. In: Paredaens J, van Gucht D (eds) Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, New York, pp 239\u2013250","DOI":"10.1145\/1807085.1807117"},{"key":"2488_CR24","unstructured":"Niewerth M (2015) Data definition language for xml repository management systems. Ph.D. Thesis, Technischen Universitat Dortmund an der Fakultat Informatik"},{"key":"2488_CR25","doi-asserted-by":"crossref","unstructured":"Wieczorek W (2017) Grammatical inference: Algorithms, routines and applications, vol 673. Studies in Computational Intelligence. Springer","DOI":"10.1007\/978-3-319-46801-3"},{"key":"2488_CR26","doi-asserted-by":"crossref","unstructured":"Wieczorek W (2010) A local search algorithm for grammatical inference. In: Sempere J M, Garc\u00eda P (eds) Grammatical Inference: Theoretical Results and Applications, LNCS, vol 6339. Springer, Berlin, pp 217\u2013229","DOI":"10.1007\/978-3-642-15488-1_18"},{"issue":"4","key":"2488_CR27","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1515\/fcds-2016-0016","volume":"41","author":"W Wieczorek","year":"2016","unstructured":"Wieczorek W (2016) Inductive synthesis of cover-grammars with the help of ant colony optimization. Found Comput Decis Sci 41(4):297\u2013315","journal-title":"Found Comput Decis Sci"},{"key":"2488_CR28","unstructured":"Runge T, Schaefer I, Cleophas L, Watson B W (2017) Many-MADFAct: Concurrently constructing MADFAs. In: Holub J, Zd\u00e1rek J (eds) Proceedings of the Prague Stringology Conference 2017, Prague, pp 126\u2013142"}],"container-title":["Applied Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-021-02488-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10489-021-02488-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-021-02488-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,10]],"date-time":"2022-02-10T05:23:11Z","timestamp":1644470591000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10489-021-02488-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,26]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["2488"],"URL":"https:\/\/doi.org\/10.1007\/s10489-021-02488-y","relation":{},"ISSN":["0924-669X","1573-7497"],"issn-type":[{"type":"print","value":"0924-669X"},{"type":"electronic","value":"1573-7497"}],"subject":[],"published":{"date-parts":[[2021,6,26]]},"assertion":[{"value":"29 April 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The source code of the algorithms and selected benchmark languages used in the experiments are available on the GitHub website and service (https:\/\/github.com\/tjastrzab\/ai).","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code and data availability"}},{"value":"The authors declare that they have no conflict of interest.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}