IMI-BAS
 

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

Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/705

Title: Decomposition of Boolean Functions – Recognizing a Good Solution by Traces
Authors: Zakrevskij, Arkadij
Keywords: Boolean Function
Non-Disjunctive Decomposition
Appropriate Partition
Combinatorial Search
Recognition
Randomization
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.
URI: http://hdl.handle.net/10525/705
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! DSpace Software Copyright © 2002-2009  The DSpace Foundation - Feedback