A parallel algorithm for the decomposition of finite languages

Tomasz Jastrząb, Zbigniew J Czech


A finite language is said to be decomposable, if it can be written as
a catenation of two non-empty languages. In this paper a parallel algorithm for finding the decomposition of finite languages is proposed. The effectiveness of the algorithm is assessed based on the experimental results provided for selected languages.


parallel algorithms; finite languages; finite languages decomposition

Full Text:



Ciura M., and Deorowicz S.: Experimental Study of Finite Automata Storing Static Lexicons. [in:] Technical Report, Silesian Technical University, Gliwice 1999.

Czech Z. J.: Równoległy algorytm dekompozycji języków skończonych. [in:] Waku-licz-Deja A. (ed.): Systemy wspomagania decyzji. Instytut Informatyki Uniwersytetu Śląskiego, Sosnowiec 2010, p. 289÷295.

de la Higuera C.: A bibliographical study of grammatical inference. Pattern Recogni-tion, vol. 38 is. 9, 2005, p. 1332÷1348.

Mateescu A., Salomaa A., and Yu S.: On the Decomposition of Finite Languages. [in:] Technical Report, Turku Centre for Computer Science, 1998.

Salomaa A., Salomaa K., and Yu S.: Length Codes, Products of Languages and Primal-ity. [in:] Martín-Vide C., Otto F., and Fernau H. (eds.): Language and Automata The-ory and Applications. LNCS 5196, Springer, Berlin 2008, p. 476÷486.

Salomaa A., Yu S.: On the Decomposition of Finite Languages. [in:] Rozenberg G., and Thomas W. (eds.): Developments in Language Theory: Foundations, Applications and Perspectives, World Scientific Publishing, Singapore 2000, p. 22÷31.

Watson B.W.: A Fast and Simple Algorithm for Constructing Minimal Acyclic Deter-ministic Finite Automata. Journal of Universal Computer Science, vol. 8 no. 2, 2002, p. 363÷367.

Wieczorek W.: A Local Search Algorithm for Grammatical Inference. [in:] Sempere J.M., and García P. (eds.): Grammatical Inference: Theoretical Results and Applica-tions. LNCS 6339, Springer, Berlin 2010, p. 217÷229.

Wieczorek W.: An algorithm for the decomposition of finite languages. Logic Journal of the IGPL, vol. 18 is. 3, 2009, p. 355÷366.

Wieczorek W.: Metaheuristics for the Decomposition of Finite Languages. [in:] Kłopo-tek M.A., Przepiórkowski A., Wierzchoń S.T., and Trojanowski K. (eds.): Recent Ad-vances in Intelligent Information Systems, Akademicka Oficyna Wydawnicza EXIT, 2009, p. 495÷505.

Yu S.: Regular languages. [in:] Rozenberg G., and Salomaa A. (eds.): Handbook of Formal Languages: Volume 1., Word, Language, Grammar. Springer, 1997.

DOI: http://dx.doi.org/10.21936/si2014_v35.n4.702