Menu
Home
Contact us
Stats
Categories
Calendar
Toggle Wiki
Wiki Home
Last Changes
Rankings
List pages
Orphan pages
Sandbox
Print
Toggle Image Galleries
Galleries
Rankings
Toggle Articles
Articles home
List articles
Rankings
Toggle Blogs
List blogs
Rankings
Toggle Forums
List forums
Rankings
Toggle File Galleries
List galleries
Rankings
Toggle Maps
Mapfiles
Toggle Surveys
List surveys
Stats
ITHEA Classification Structure > G. Mathematics of Computing  > G.2 DISCRETE MATHEMATICS  > G.2.1 Combinatorics 
DECOMPOSITION OF BOOLEAN FUNCTIONS – RECOGNIZING A GOOD SOLUTION BY TRACES
By: Arkadij Zakrevskij (3745 reads)
Rating: (1.00/10)

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.

Keywords: Boolean function, non-disjunctive decomposition, appropriate partition, combinatorial search, recognition, randomization, computer experiment.

ACM Classification Keywords: G.2.1 Combinatorics – combinatorial problems, combinatorial search, G.3 Probability and Statistics – randomization.

Link:

DECOMPOSITION OF BOOLEAN FUNCTIONS – RECOGNIZING A GOOD SOLUTION BY TRACES

Arkadij Zakrevskij

http://www.foibg.com/ijita/vol14/ijita14-4-p10.pdf

Print
G.2.1 Combinatorics
article: RANDOMIZED SET SYSTEMS CONSTRAINED BY THE DISCRETE TOMOGRAPHY · A NEW ALGORITM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM · ON THE STRUCTURE OF MAXIMUM INDEPENDENT SETS IN BIPARTITE GRAPHS · SOME PROPERTIES IN MULTIDIMENSIONAL MULTIVALUED DISCRETE TORUS · ON PROBLEM OF ADEQUACY OF MULTISET MATHEMATICAL MODELS · SPREADING THE MOORE - PENROSE PSEUDO INVERSE ON MATRICES EUCLIDEAN SPACES: ... · VECTORS AND MATRIXES IN GROUPING INFORMATION PROBLEM · CHOICE OF DIAGNOSTIC DECISION MAKING IN MEDICINE AND INTERVENTION MISTAKE ... · RECURRENT PROCEDURE IN SOLVING THE GROUPING INFORMATION PROBLEM IN APPLIED... · ‘FEATURE VECTORS’ IN GROUPING INFORMATION PROBLEM IN APPLIED MATHEMATICS: .. · DECOMPOSITION METHODS FOR LARGE-SCALE TSP · ON THE DISCRETIZATION OF DISTANCE GEOMETRY PROBLEMS · REGULAR INVERSIVE POLYTOPES · LOGARITHMIC DISTANCES IN GRAPHS · FUZZY SETS AS A MEAN FOR UNCERTAINTY HANDLING: MATH, APPLIED MATH, HEURISTICS · FUZZY SETS: MATH, APPLIED MATH, HEURISTICS? PROBLEMS AND INTERPRETATIONS · CROSS INTERSECTION SEQUEL OF DISCRETE ISOPERIMETRY1 · GENERATING MORE BOUNDARY ELEMENTS OF SUBSET PROJECTIONS · MULTICRITERION PROBLEMS ON THE COMBINATORIAL SET OF POLYARRANGEMENTS · CHAIN SPLIT OF PARTIALLY ORDERED SET OF K-SUBSETS · SOLVING LARGE SYSTEMS OF BOOLEAN EQUATIONS · LAGRANGEAN APPROXIMATION FOR COMBINATORIAL INVERSE PROBLEMS · MULTICRITERION PROBLEMS ON THE COMBINATORIAL SET OF POLYARRANGEMENTS · DESCRIPTION REDUCTION FOR RESTRICTED SETS OF (0,1) MATRICES 1 · DECOMPOSITION OF BOOLEAN FUNCTIONS – RECOGNIZING A GOOD SOLUTION BY TRACES · THE BOUNDARY DESCRIPTORS OF THE n-DIMENSIONAL UNIT CUBE SUBSET PARTITIONING1 · RANDOMIZED PARALLELIZATION – A NEW METHOD FOR SOLVING ... · OPTIMIZATION OF ATM TELECOMMUNICATION NETWORKS · VECTOR COMBINATORIAL PROBLEMS IN A SPACE OF COMBINATIONS ... ·
Login
[ register | I forgot my password ]
World Clock
Powered by Tikiwiki Powered by PHP Powered by Smarty Powered by ADOdb Made with CSS Powered by RDF powered by The PHP Layers Menu System
RSS Wiki RSS Blogs rss Articles RSS Image Galleries RSS File Galleries RSS Forums RSS Maps rss Calendars
[ Execution time: 0.08 secs ]   [ Memory usage: 7.57MB ]   [ GZIP Disabled ]   [ Server load: 0.37 ]
Powered by Tikiwiki CMS/Groupware