Search

Sequential processes can encounter faults as a result of improper ordering of subsets of the events. In order to reveal faults caused by the relative ordering of t or fewer of v events, for some fixed t, a test suite must provide tests so that every ordering of every set of t or fewer events is exercised. Such a test suite is equivalent to a sequence covering array, a set of permutations on v events for which every subsequence of t or fewer events arises in at least one of the permutations. Equivalently it is a (different) set of permutations, a completely t-scrambling set of permutations, in which the images of every set of t chosen events include each of the t! possible "patterns." In event sequence testing, minimizing the number of permutations used is the principal objective. By developing a connection with covering arrays, lower bounds on this minimum in terms of the minimum number of rows in covering arrays are obtained. An existing bound on the largest v for which the minimum can equal t! is improved. A conditional expectation algorithm is developed to generate sequence covering arrays whose number of permutations never exceeds a specified logarithmic function of v when t is fixed, and this method is shown to operate in polynomial time. A recursive product construction is established when t = 3 to construct sequence covering arrays on vw events from ones on v and w events. Finally computational results are given for t ∈{3, 4, 5} to demonstrate the utility of the conditional expectation algorithm and the product construction. [ABSTRACT FROM AUTHOR]

SONET/WDM networks using wavelength add-drop multiplexing can be constructed using certain graph decompositions used to form a grooming, consisting of unions of primitive rings. The cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The existence of such decompositions with minimum cost, when every pair of sites employs no more than $\frac{1}{6}$ of the wavelength capacity, is determined with a finite number of possible exceptions. Indeed, when the number N of sites satisfies $N \equiv 1 \pmod{3}$, the determination is complete, and when $N \equiv 2 \pmod{3}$, the only value left undetermined is N = 17. When $N \equiv 0 \pmod{3}$, a finite number of values of N remain, the largest being N = 2580. The techniques developed rely heavily on tools from combinatorial design theory. [ABSTRACT FROM AUTHOR]

A difference triangle set (D$\Delta$S) is a collection of sets of integers having the property that every integer can be written in at most one way as the difference of two elements within a set of the collection. The standard objective is to minimize the largest difference represented, given a specified size of the collection and sizes of the sets that it contains. In order to construct D$\Delta$Ss, we present a new type of combinatorial design, monotonic directed $(v,k,\lambda)$- designs (MDDs). Using MDDs, we give a general recursive construction for difference triangle sets (D$\Delta$Ss). Several instances of this main construction are derived. One of these, the perfect construction, leads to an infinite family of regular (optimal) D$\Delta$Ss if the existence of a single regular D$\Delta$S is known. [ABSTRACT FROM AUTHOR]