Dekompozycja funkcji i relacji boolowskich w syntezie logicznej i analizie danych

• Autorzy: Sapiecha P. , Pleban M. , Zbierzchowski B.

Warianty tytułu

EN

Decomposition of Boolean relations and functions in logic synthesis and data analysis

• Języki publikacji: PL

Abstrakty

PL

W pracy wykazano, że problem dekompozycji dowolnej funkcji skończonej f(A,B) do postac i h(g(A),B), gdzie g jest funkcją boolowską, jest rozstrzygalny w czasie wielomianowym względem rozmiaru problemu. Równocześnie wykazano, że pominięcie założenia dotyczącego funkcji g powoduje znaczne skomplikowanie problemu. Tak ogólny problem należy do klasy problemów NP - trudnych. W pracy przedstawiono sprowadzenie problemu dekompozycji funkcji skończonych do problemu wierzchołkowego kolorowania grafu. Opisano także, sprowadzenie problemu dekompozycji relacji do problemu wyznaczania kolorowania wierzchołkowego hipergrafu. W celu wykazania poprawności obu redukcji, wykorzystano kombinatoryczną własność Helly.

EN

This paper shows that the problem of decomposing a finite function f(A,B) into the form h (g(A)B), where g is a Boolean function, can be resolved in polynomial time, with respect to the size of the problem. It is also shown that omission of the characteristic of the g function can significantly complicate the problem. Such a general problem belongs to the NP - hard class of problems. The work shows how the problem of decomposition of a finite function can be reduced to the problem of coloring the vertices of a graph. It is also shown that the problem of decomposition of relations can be reduced to coloring the vertices of their hypergraphs. In order to prove the validity of the theorems, combinatory properties of Helly are used.

Słowa kluczowe

PL

synteza logiczna; algorytmy; dekompozycja funkcjonalna

EN

logic synthesis; algorithms; functional decomposition

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2000
• Tom: Vol. 46, nr 3
• Strony: 400--411
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Sapiecha P.

autor

Pleban M.

autor

Zbierzchowski B.

• Instytut Telekomunikacji, Politechnika Warszawska, Warszawa