A parallel algorithm for the decomposition of finite languages

• Autorzy: Jastrząb T. , Czech Z. J.

Warianty tytułu

PL

Równoległy algorytm dekompozycji języków skończonych

• Języki publikacji: EN

Abstrakty

EN

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.

PL

Język skończony jest dekomponowalny, jeżeli może zostać zapisany jako złożenie dwóch niepustych języków. W niniejszym artykule zaproponowany został równoległy algorytm dekompozycji języków skończonych. Efektywność przedstawionego algorytmu została oceniona na podstawie eksperymentów przeprowadzonych dla wybranych języków.

Słowa kluczowe

EN

parallel algorithms; finite language; finite languages decomposition

PL

algorytmy równoległe; języki skończone; dekompozycja języków skończonych

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2014
• Tom: Vol. 35, nr 4
• Strony: 5--16
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Jastrząb T.

• Silesian University of Technology, Institute of Informatics

autor

Czech Z. J.

• Silesian University of Technology, Institute of Informatics

Bibliografia

• 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 Advances 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.