An important step in molecular diagnostics for genetic diseases is the interpretation of sizing signals obtained by gel electrophoresis. Usually, the interpretation is done manually and is labor-intensive. An algorithm for automatic interpretation of two-dimensional sizing signals is described. The underlying computation is a rule-based assignment of values to labels of a set of image variables.>

Visualization is an important component of modern computing. By animating the course of an algorithm's temporal execution, many key features can be elucidated. The author has developed a general framework, termed Call-Graph Caching (CGC), for automating the construction of many complex AI algorithms. By incorporating visualization into CGC interpreters, principled animations can be automatically displayed as AI computations unfold. Systems that support the automation animation of AI algorithms must address these three design issues: how to represent AI data structures in a general, uniform way that leads to perspicuous animation and efficient redisplay; how to coordinate the succession of graphical events; and how to partition AI graphs to provide for separate, uncluttered displays. CGC provides a natural and effective solution to all these concerns. The author describes the CGC method, including detailed examples, and discusses why CGC works well for animation. He discusses the CACHE system, the CGC environment for AI algorithm animation. Finally, the author demonstrates the animation of several AI algorithms-RETE match, linear unification, arc consistency, chart parsing, and truth maintenance-all of which have been implemented in CACHE.

An attempt is made to improve production system match by incorporating the arc consistency (AC) algorithm, in the RETE algorithm. This approach combines the constraint graphs of RETE and AC into a single network, which is then incrementally updated. Empirical studies show the technique to be most efficacious with expensive rules. Thus, by using the lookahead from AC preprocessing, in many cases costly RETE computation can be effectively reduced.>

A panel session in which issues relating to the effects of advances in faster and more parallel hardware, production system match (PSM) algorithms, and application domains for match on PSM as a research area is presented. It is argued that there is no such thing as the optimal matching algorithm, even for the well-defined task of production-system match and that broadening the scope of the matching task beyond forward-chaining production system presents a new set of problems to the artificial intelligence community. Also, even with all the speedups, large production system runs take hours to complete, and a major portion of this time is attributable to PSM. Match technology remains a large and centralized component of system performance. To that extent, providing sufficient speedups in the match in these systems may still be useful. Performance issues of production system execution are discussed, and a common set of benchmarks and test cases is called for. It is argued that parallel algorithms for match, resolve, and fire are all interesting and difficult problems to solve, and should be the focus of research by the PSM community.>

Efficient syntactic and semantic parsing for ambiguous context-free languages are generally characterized as complex, specialized, highly formal algorithms. In fact, they are readily constructed from straightforward recursive transition networks (RTNs). In this paper, we introduce LR-RTNs, and then computationally motivate a uniform progression from basic LR parsing, to Earley's (chart) parsing, concluding with Tomita's parser. These apparently disparate algorithms are unified into a single implementation, which was used to automatically generate all the figures in this paper.

An optimal arc consistency algorithm AC-4 was given by R. Mohr and T.C. Henderson (1986). AC-4 has costO(ea/sup 2/), and cost(na/sup 2/) for scene labeling. Although their algorithm is indeed optimal, under certain conditions a constraint satisfaction problem can be transformed into a less complex problem. Conditions and mechanisms are presented for such transformations, and it is shown how to factor relations into more manageable components. A description is given of how factorization can reduce AC-4's cost to O(ea), and this result is applied to RETE match.>

A new mechanism is presented for graph instantiation. It is used to investigate various bottom-up data-driven AI algorithms. The author views instances as fairly autonomous objects that inherit graph information (e.g. links or relations) from their classes. Instances themselves can be instantiated. For example, a parse tree symbol is an instance of a grammar class-graph symbol, which itself is a symbol of instance. The model focuses on underlying computational processes, and makes little use of program text. Instead of transforming programs, CGC (call graph caching) is used to instantiate processes. Experimental results show that RETE matching, efficient context-free parsing, and truth maintenance are different manifestations of the same underlying computational process.>

A new binding-space algorithm conjunctive match is introduced. Known as the linearized match box, it improves on the parallel match box algorithm by reducing broadcast cost, better adapting it to serial computers. Cost estimates are presented that help determine the applicability of linearized match box for particular rule problems. Linearized match box has been implemented, and its utility in overcoming PRODIGY's control knowledge bottleneck is discussed.>

Conjunctive match is often used in Artificial Intelligence as the kernel of a pattern-directed inference [37] engine. Conjunctive match entails generating and testing all possible combinations of objects against a pattern of constraints. While simple to program, it is an expensive, exponential cost computation. To reduce this average match cost in production system engines, the RETE match algorithm [8] was devised. RETE compiles each rule's pattern of constraints into a network, and then incrementally updates partial matches as objects are inserted and deleted. RETE, however, has its own cost: conceptual and implementational complexity. Call-graph caching (CGC) [20] is a mechanism for transforming recursive specifications into highly optimized networks. In this paper, we describe CGC, and use it to transform a family of recursive conjunctive match formulations into their corresponding RETE networks. Our approach illustrates the ideas behind RETE, and shows their application to other algorithms.