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 FunctionNon-Disjunctive DecompositionAppropriate PartitionCombinatorial SearchRecognitionRandomizationComputer 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