Group testing is utilized in the case when we want to find a few defectives among a large amount of items. Testing$n$items one by one requires$n$tests, but if the ratio of defectives is small, group testing is an efficient way to reduce the number of tests. Many researches have been developed for group testing for a single type of defectives. In this paper, we consider the case where two types of defective A and B exist. For two types of defectives, we develop a belief propagation algorithm to compute the marginal posterior probability of defectives. Furthermore, we construct several kinds of collections of pools in order to test for A and B. And, by utilizing our belief propagation algorithm, we evaluate the performance of group testing by conducting simulations.

A new notion, error-correcting locating arrays (ECLAs), is presented for locating interaction faults in component-based systems using combinatorial testing. Error tolerances of commonly used combinatorial arrays for testing such as covering arrays and locating arrays are discussed. Moreover, coding-theoretic characterization and constructions for ECLAs are proposed. Lastly, it is shown that multi-value Paley matrices can be used as ECLAs with high error tolerances for which the proof is based on character sums in finite fields.

BCH codes are among the best practical cyclic codes widely used in consumer electronics, communication systems, and storage devices. However, not much is known about BCH codes with large minimum distance. In this paper, we consider narrow-sense BCH codes of length $n = \frac{q^m-1}{N}$ with designed distance $\delta = \frac{s}{q-1}n$ proportional to $n$, where $N$ divides $\frac{q^m-1}{q-1}$ and $1 \le s \le q-1$. We determine both their dimensions and minimum distances. In particular, when $N=1$, the codes are primitive, with minimum distance $d=\frac{s}{q-1}(q^m-1)$ and dimension $k = (q-s)^m$. The general result on code dimensions is achieved by applying generating functions and inverse discrete Fourier transforms to an enumeration problem.

The study of gene functions requires high-quality DNA libraries. However, a large number of tests and screenings are necessary for compiling such libraries. We describe an algorithm for extracting as much information as possible from pooling experiments for library screening. Collections of clones are called pools, and a pooling experiment is a group test for detecting all positive clones. The probability of positiveness for each clone is estimated according to the outcomes of the pooling experiments. Clones with high chance of positiveness are subjected to confirmatory testing. In this paper, we introduce a new positive clone detecting algorithm, called the Bayesian network pool result decoder (BNPD). The performance of BNPD is compared, by simulation, with that of the Markov chain pool result decoder (MCPD) proposed by Knill et al. in 1996. Moreover, the combinatorial properties of pooling designs suitable for the proposed algorithm are discussed in conjunction with combinatorial designs and d-disjunct matrices. We also show the advantage of utilizing packing designs or BIB designs for the BNPD algorithm.

Frequency hopping spread spectrum and direct sequence spread spectrum are two main spread coding technologies in communication systems. Frequency hopping sequences are needed in frequency hopping code-division multiple-access (FH-CDMA) systems. In this paper, four algebraic and a combinatorial constructions of optimal sets of frequency hopping sequences with new parameters are presented, and a number of bounds on sets of frequency hopping sequences are described.

A conflict-avoiding code (CAC) C of length n with weight k is a family of binary sequences of length n and weight k satisfying Sigma0lestlesn-1xitxj,t+sles lambda for any distinct codewords xj= (xi0,xi1,hellip,xi,n-1) and xj= (xj0, xj1,hellip, xj,n-1) in C and for any integer s, where the subscripts are taken modulo n. A CAC with maximal code size for given n and k is said to be optimal. A CAC has been studied for sending messages correctly through a multiple-access channel. The use of an optimal CAC enables the largest possible number of asynchronous users to transmit information efficiently and reliably. In this paper, the case lambda = 1 is treated, and various direct and recursive constructions of optimal CACs for weight k = 4 and 5 are obtained by providing constructions of CACs for general weight k. In particular, the maximum code size of CACs satisfying certain sufficient conditions is determined through number theoretical and combinatorial approaches.

A conflict-avoiding code (CAC) C of length n with weight k is a family of binary sequences of length n and weight k satisfying $\sum_{0\le t\le n-1}x_{it}x_{j,t+s}\le \lambda$ for any distinct codewords $x_i=(x_{i0},x_{i1},\ldots,x_{i,n-1})$ and $x_j=(x_{j0},x_{j1},\ldots,x_{j,n-1})$ in C and for any integer s, where the subscripts are taken modulo n. A CAC with maximum code size for given n and k is said to be optimal. A CAC has been studied for sending messages correctly through a multiple-access channel. The use of an optimal CAC enables the largest possible number of potential users to transmit information efficiently and reliably. In this paper, the case $\lambda=1$ is treated, and various direct and recursive constructions of optimal CACs for weight $k=4$ and 5 are obtained by providing constructions of CACs for general weight k. In particular, the maximum code size of CACs satisfying certain sufficient conditions is determined through number theoretical and combinatorial approaches.

New improved upper and lower bounds on the maximum size of a symmetric or arbitrary conflict-avoiding code of length n = 4 m for three active users are proved. Furthermore, direct constructions for optimal conflict-avoiding codes of length n = 4 m and m equiv 2 (mod 4) for three active users are provided.

Fu, Hwang, Jimbo, Mutoh, and Shiue [J. Statist. Plann. Inference, to appear] introduced the concept of a grid-block design, which is defined as follows: For a v-set V, let ${\cal A}$ be a collection of r × c arrays with elements in V. A pair $(V, {\cal A})$ is called an r × cgrid-block design if every two distinct points i and j in V occur exactly once in the same row or in the same column. This design has originated from the use of DNA library screening. They gave some general constructions and proved the existence of 3×3 grid-block designs. Meanwhile, the existence of 2×3 grid-block designs was shown by Carter [ Designs on Cubic Multigraphs, Ph.D. thesis, McMaster University, Hamilton, ON, Canada, 1989] by decomposing K v into cubic graphs. In this paper, we show the existence of 2×4 grid-block designs.

In this paper, an explicit solution of the optimum requirement spanning tree (ORST), studied by Hu, is obtained in the case when a weight is assigned to each node and when maximum-degree conditions are given. Further, the solution is shown to minimize the probability of communication failure in the situation where one node or line is broken down. © 1999 John Wiley & Sons, Inc. Networks 34: 122–131, 1999

In 1982, G.J. Simmons introduced a mathematical model of authentication theory. Recently, E.F. Brickell (1984) and D.R. Stinson (1988) have shown some combinatorial constructions for optimal authentication systems. In the present work, game-theoretical models are proposed for authentication systems that have multilevel costs on sources, and lower bounds of the game values are obtained. Some constructions of the optimal authentication systems that attain the bounds are shown.>