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.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.