A comparative analysis of two parallel algorithms for finite language decomposition

• Autorzy: Jastrząb T.

Warianty tytułu

PL

Analiza porównawcza dwóch równoległych algorytmów dekompozycji języków skończonych

• Języki publikacji: EN

Abstrakty

EN

A finite language is said to possess a non-trivial decomposition if it can be represented as a catenation of two non-empty languages. In this paper two parallel versions of a known sequential algorithm for finding the decomposition of finite languages are proposed. The effectiveness of the algorithms is estimated based on the experimental results obtained for several sample languages.

PL

Problem dekompozycji języków skończonych jest rozstrzygalny, chociaż trudny do rozwiązania. Problem sprowadza się do wyznaczenia pary niepustych języków skończonych L1, L2, takich że w wyniku operacji ich złożenia powstaje język wejściowy. Każdy język skończony posiada dekompozycję trywialną, a oprócz niej zero lub więcej dekompozycji nietrywialnych. Ze względu na brak algorytmu pozwalającego na wyznaczenie zbioru dekompozycji dla dowolnego języka, w artykule zaproponowano rozwiązanie oparte na przeszukiwaniu wyczerpującym z obcinaniem przestrzeni rozwiązań. Artykuł przedstawia dotychczasowe próby rozwiązywania problemu dekompozycji języków skończonych z wykorzystaniem algorytmów sekwencyjnych (rys. 1) oraz równoległych (rys. 2 i 3). Na podstawie znanych algorytmów opracowano ulepszone wersje algorytmu równoległego (rys. 4 i 5). W zaproponowanym rozwiązaniu skoncentrowano się na minimalizacji narzutu czasowego wynikającego z komunikacji pomiędzy procesami. Dokonana ocena efektywności opracowanych algorytmów oparta została o pomiary czasu wykonania dla implementacji z użyciem biblioteki MPI. Uzyskane wyniki (tab. 1), a w szczególności przyspieszenia pozwalają na ocenę rozwiązań jako nie w pełni zadowalających, w odniesieniu do wykorzystanej liczby procesorów.

Słowa kluczowe

EN

parallel algorithms; finite languages; finite languages decomposition

PL

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

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 6
• Strony: 350--353
• Opis fizyczny: Bibliogr. 10 poz., tab.

Twórcy

autor

Jastrząb T.

• Institute of Informatics, Silesian University of Technology Akademicka Street 16, 44-100 Gliwice, Poland

Bibliografia

• [1] Wieczorek W.: An algorithm for the decomposition of finite languages. Logic Journal of the IGPL, vol. 18 is. 3, pp. 355÷366, 2009.
• [2] Yu S.: Regular languages. [in:] Rozenberg G., and Salomaa A. (eds.): Handbook of Formal Languages: Volume 1., Word, Language, Grammar. Springer, 1997.
• [3] Watson B.W.: A Fast and Simple Algorithm for Constructing Minimal Acyclic Deterministic Finite Automata. Journal of Universal Computer Science, vol. 8 no. 2, pp. 363÷367, 2002.
• [4] de la Higuera C.: A bibliographical study of grammatical inference. Pattern Recognition, vol. 38 is. 9, pp. 1332÷1348, 2005.
• [5] Wieczorek W.: A Local Search Algorithm for Grammatical Inference. [in:] Sempere J.M., and García P. (eds.): Grammatical Inference: Theoretical Results and Applications. LNCS 6339, Springer-Berlin, pp. 217÷229, 2010.
• [6] Mateescu A., Salomaa A., and Yu S.: On the Decomposition of Finite Languages. [in:] Technical Report, Turku Centre for Computer Science, 1998.
• [7] Wieczorek W.: Metaheuristics for the Decomposition of Finite Languages. [in:] Kłopotek M.A., Przepiórkowski A., Wierzchoń S.T., and Trojanowski K. (eds.): Recent Advances in Intelligent Information Systems, Akademicka Oficyna Wydawnicza EXIT, pp. 495÷505, 2009.
• [8] 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, pp. 22-31, 2000.
• [9] Salomaa A., Salomaa K., and Yu S.: Length Codes, Products of Languages and Primality. [in:] Martín-Vide C., Otto F., and Fernau H. (eds.): Language and Automata Theory and Applications. LNCS 5196, Springer-Berlin, pp. 476÷486, 2008.
• [10] Czech Z.J.: Równoległy algorytm dekompozycji języków skończonych. [in:] Wakulicz-Deja A. (ed.): Systemy wspomagania decyzji. Instytut Informatyki Uniwersytetu Śląskiego, Sosnowiec, pp. 289÷295, 2010.