Wyniki wyszukiwania - BazTech

1

On Boolean Representation of Continuous Data Biclustering

Michalak Marcin, Ślęzak Dominik

Fundamenta Informaticae

|

2019

|

Vol. 167, nr 3

193--217

EN

Biclustering is considered as the method of finding two-dimensional subgroups in a matrix of scalars. The paper introduces a new approach to biclustering continuous matrices on the basis of boolean function analysis. We draw the strong relation between inclusion-maximal (maximal with respect to inclusion) biclusters of the assumed maximal difference between the data in a bicluster and prime implicants of a boolean function describing the data. These biclusters are called similarity biclusters. In the opposition to them, a new notion of dissimilarity biclusters was also introduced in the paper.

2

Boolean Representation for Exact Biclustering

Michalak M., Ślęzak D.

Fundamenta Informaticae

|

2018

|

Vol. 161, nr 3

275--297

EN

Biclustering is a branch of data analysis, whereby the goal is to find two–dimensional subgroups in a matrix of scalars. We introduce a new approach for biclustering discrete and binary matrices on the basis of boolean function analysis. We draw the correspondence between non–extendable (maximal with respect to inclusion) exact biclusters and prime implicants of a discernibility function describing the data. We present also the results of boolean-style clustering of the artificial discrete image data. Some possibilities of utilizing basic image processing techniques for this kind of input to the biclustering problem are discussed as well.

3

Novel method to simplify Boolean functions

Prasad V. C.

Automatyka / Automatics

|

2018

|

Vol. 22, no. 2

29--40

EN

Most methods for determining the prime implicants of a Boolean function depend on the minterms of the function. Deviating from this philosophy, this paper presents a method that dependson maxterms (the minterms of the complement of the function) for this purpose. Normally, maxterms are used to get prime implicates and not prime implicants. It is shown that all prime implicants of a Boolean function can be obtained by expanding and simplifying any product of sums form of the function appropriately. No special form of the product of the sums is required. What is more, prime implicants can generally be generated from any form of the function by converting it into a POS using well-known techniques. The prime implicants of a product of Boolean functions can be obtained from the prime implicants of individual Boolean functions. This allows us to handle big functions by breaking them into the products of smaller functions. A simple method is presented to obtain one minimal set of prime implicants from all prime implicants without using minterms. Similar statements also hold for prime implicates. In particular, all prime implicates can be obtained from any sum of a products form.Twelve variable examples are solved to illustrate the methods.

PL

Większość metod wyznaczania implikantów prostych funkcji boolowskiej wykorzystuje mintermy funkcji. Niniejszy artykuł prezentuje odmienną metodę, która stosuje do tego celu makstermy (mintermy dopełnienia funkcji). Jest to podejście niestandardowe, gdyż zazwyczaj na podstawie makstermów uzyskuje się implicenty proste, a nie implikanty proste. W artykule pokazano, że wszystkie implikanty proste funkcji boolowskiej mogą być otrzymane przez odpowiednie rozwinięcie i uproszczenie funkcji podanej w dowolnej postaci typu iloczyn sum. Nie jest przy tym wymagana żadna szczególna postać tego iloczynu. Co więcej, implikanty proste mogą być zwykle utworzone na podstawie funkcji w dowolnej postaci, przez przekształcenie jej do postaci typu iloczyn sum z wykorzystaniem znanych metod. Implikanty proste iloczynu funkcji boolowskich można uzyskać z implikantów prostych poszczególnych funkcji. To pozwala operować na dużych funkcjach przez rozbicie ich na iloczyn mniejszych. Artykuł pokazuje prostą metodę uzyskania jednego zbioru minimalnego implikantów prostych na podstawie zbioru wszystkich implikantów prostych bez korzystania z mintermów. Podobne stwierdzenia mają zastosowanie także w przypadku implicentów prostych. W szczególności, wszystkie implicenty proste mogą być otrzymane z dowolnej formy typu suma iloczynów. Zaproponowana w artykule metoda została zilustrowana licznymi przykładami.

4

Algorytm selekcji wykorzystujący teorię hipergrafów

Stefanowicz Ł., Wiśniewski R., Adamski M.

Pomiary Automatyka Kontrola

|

2014

|

R. 60, nr 7

516--518

PL

Artykuł porusza kwestię selekcji określonych elementów zbioru z wykorzystaniem teorii hipergrafów. Przedstawiona została idea wspólnego algorytmu selekcji, w przypadku takich problemów, jak selekcja podsieci automatowych w dekompozycji sieci Petriego, a także selekcja implikantów prostych w procesie miminalizacji funkcji logicznych. Jako bazowy algorytm, wykorzystano metodę transwersal dokładnych, jednocześnie usprawniając ją o alternatywną scieżkę w przypadku, kiedy dany hipergraf selekcji nie należy do klasy hipergrafu transwersal dokładnych. Jak pokazują badania, metoda może być dobrą alternatywą obok wykorzystywanych metod tradycyjnych.

EN

The paper deals with the selection problem based on the hypergraph theory. There is presented an idea of a common selection algorithm for selection of State Machine Components and Prime Implicants. The exact transversal method was used as a baseline algorithm. It was improved by supporting it with an optional path when a given selection hypergraph did not belong to the xt-class (class of the exact transversal hypergraph). In this case, the exact transversal was searched. When it was unsuccessful, the regular transversal was searched. The studies prove that the method allows obtaining the exact solution when the selection hypergraph does not belong to the xt-class, but has an exact transversal. The presented results show that a hypergraph which does not belong to the xt-class may have an exact transversal enabling obtaining a solution which would be as good as the one obtained with the backtracking method. The exact solution was also obtained with the use of an ordinary transversal, which de facto indicated that the regular transversals allowed, in certain cases, obtaining the exact solution. It seems to confirm the aptly determined class of solutions of the proposed improvements. In some cases, the solution contained one extra subnet, but in one tested case, the solution turned out to be much worse than the exact one.

5

Heuristics for Thelen's Prime Implicant Method

Bieganowski J., Karatkevich A.

Schedae Informaticae

|

2005

|

Vol. 14

125-135

EN

Thelen's algorithm is an efficient method for generation of the prime implicants of a Boolean function represented in CNF. In the paper new heuristics are presented, allowing to accelerate the algorithm. Experimental analysis of their effects is performed.