Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Kwartalnik Elektroniki i Telekomunikacji

1 2000

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Dekompozycja funkcji i relacji boolowskich w syntezie logicznej i analizie danych

Sapiecha P., Pleban M., Zbierzchowski B.

Kwartalnik Elektroniki i Telekomunikacji

2000

Vol. 46, nr 3

400-411

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.

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.