Springer
Table of ContentsAuthor IndexSearch

Building-Block Identification by Simultaneity Matrix

Chatchawit Aporntewan and Prabhas Chongstitvatana

Intelligent System Laboratory
Department of Computer Engineering
Chulalongkorn University
Bangkok, 10330, Thailand
43718043@student.chula.ac.th
Prabhas.C@chula.ac.th

Abstract. We propose a BB identification by simultaneity matrix (BISM) algorithm. The input is a set of $\ell$-bit solutions denoted by $S$. The number of solutions is denoted by $n =\vert S\vert$. The output is a partition of bit positions $\{0, \ldots, \ell - 1\}$. The BISM is composed of Simultaneity-Matrix-Construction and Fine-Valid-Partition algorithms. Algorithm SMC is outlined as follows (aij denotes the matrix element at row $i$ and column $j$, $\mbox{Count}^{ab}_{S}(i, j) = \vert\{ x \in \{0, \ldots, n - 1\} : s_{x}[i] = a ~ \mbox{and} ~ s_{x}[j] = b\}\vert ~ \mbox{for all} ~ (i, j)$ $\in \{0, \ldots, \ell - 1\}^{2}, ~ (a, b) \in \{0, 1\}^{2}$, $s_{x}[i]$ denotes the ith bit of xth solution, Random(0,1) gives a real random number between 0 and 1).

LNCS 2724, p. 1566 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003