In this paper we report the results of an independent experimental evaluation of an information retrieval (IR) system developed at the Illinois Institute of Technology (IIT). The system, which is called the Advanced Information Retrieval Engine (AIRE), consists of a set of tools and utilities providing indexing, extraction, searching and visualization. We evaluated AIRE on three data sets from the Text REtrieval Conference (TREC) - TREC 8, 9 and 10. Overall, our results indicate that AIRE is a highly accurate IR system. Compared with results published by IIT, in our experiments AIRE consistently scored higher in recall. AIRE also scored higher in precision, but only for automatic tasks. In manual tasks, AIRE scored lower in precision in our experiments, but we attributed that to factors external to AIRE. Our final conclusion is that AIRE is a highly accurate IR system.

Let M be a finite-state machine, and let S be an implementation of M. The protocol-testing problem is the problem of determining if S is a correct implementation of M. One known method for solving this problem, called the W-method, has the disadvantage that it generates a relatively large test set.In this paper, we describe three new versions of this method.We prove that these versions all have the same fault detection capability as the W-method.In addition, we show that in most cases all three generate a smaller number of tests than the W-method.Specifically, suppose Ml and Mz are finite-state machines having n and m states, respectively, where Ml is a specification (M), Mz is an implementation (S), and m > n.In addition, suppose they have input alphabet X, where 1X1= k; let a be the total number of strings in a characterization set for Ml, and let ~be the total number of strings in a transition couer set for Ml.The W-method will generate a test set consisting of afl(k M n + 1 -I)/(k -1) strings.In contrast, our first algorithm will generate a test set containing at most B( a + km-n ) strings.For our second algorithm, the number of strings will be ~kmaxt'-l>m-"j, and for the third, ~(kn -1 + km-"), When m >> ~, all three of our algorithms will produce fewer strings than the W-method.Finally, two of our algorithms make use of a heuristic for minimizing the number of strings in a characterization set.We show that the performance ratio for this heuristic has an upper bound of O(log n).

Considers a strategy for dealing with communication conflicts in omega networks. Specifically, the authors consider the problem of partitioning a set of conflicting messages into a minimum number of subsets, called rounds, each free of communication conflicts. In addition to standard omega networks, they consider this problem for a more general class of networks called bundled omega networks, where interconnection links in the network are replaced by bundles of wires. Although the partitioning problem has previously been considered in the literature, its computational complexity has remained open. The authors show that for a number of cases, the problem is NP-complete, but for certain special cases, it is solvable in polynomial time. In addition, they present a class of distributed, on-line heuristics for the problem. Finally, they give a lower bound of /spl Omega/(log N) on the performance ratio for one of these heuristics.>

Let S be a set of messages to be routed on an N*N omega network. In addition, suppose that S contains communication conflicts. One strategy to deal with such conflicts is to partition S into some number of subsets, called rounds, such that each subset is conflict-free. The messages are then routed through the network by successively routing the messages in each subset. The minimum round partitioning problem is the problem of partitioning a given message set into a minimum number of rounds. The author establishes upper and lower bounds on the performance ratio for two heuristics for partitioning message patterns into rounds. For both of these heuristics they give upper and lower bounds of O (log N) and Omega (logN), respectively.>

A strategy for dealing with communication conflicts that occur in omega networks is presented. The strategy operates by implementing the dual path property of omega networks, which allows the source and destination processors to reverse roles for some of the messages that are being transmitted. For certain message patterns, such a reversal produces a modified message pattern for which the network routes are disjoint. For a circuit switching mode in which the network links and switches are bidirectional, the disjoint set of routes for modified message pattern can be used to achieve conflict-free message transmission for the original message pattern. This strategy is investigated, and an efficient algorithm to determine whether it can be successfully applied to a given message pattern is presented.>