BulDML at Institute of Mathematics and Informatics >
International Journal ITA >
2007 >
Volume 14 Number 4 >

Please use this identifier to cite or link to this item:

Title: Decomposition of Boolean Functions – Recognizing a Good Solution by Traces
Authors: Zakrevskij, Arkadij
Keywords: Boolean Function
Non-Disjunctive Decomposition
Appropriate Partition
Combinatorial Search
Computer Experiment
Issue Date: 2007
Publisher: Institute of Information Theories and Applications FOI ITHEA
Abstract: The problem of sequent two-block decomposition of a Boolean function is regarded in case when a good solution does exist. The problem consists mainly in finding an appropriate weak partition on the set of arguments of the considered Boolean function, which should be decomposable at that partition. A new fast heuristic combinatorial algorithm is offered for solving this task. At first the randomized search for traces of such a partition is fulfilled. The recognized traces are represented by some "triads" - the simplest weak partitions corresponding to non-trivial decompositions. After that the whole sought-for partition is restored from the discovered trace by building a track initialized by the trace and leading to the solution. The results of computer experiments testify the high practical efficiency of the algorithm.
ISSN: 1313-0463
Appears in Collections:Volume 14 Number 4

Files in This Item:

File Description SizeFormat
ijita14-4-p10.pdf70.1 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License