Foundations of Envisioning
This paper explores a particular kind of qualitative reasoning, called envisioning, that is capable of producing causal explanations for device behavior. It has been implemented in a computer program, ENVISION, which can analyze a wide variety of thermal, fluid, electrical, translational and rotational devices. Rather than present the technical details of the envisioning process, this paper examines the theoretical foundations upon which it is built. Many of these considerations are ones that any builder of qualitative reasoning systems must pay attention to. Two such considerations are explanation and robustness: What notion of causality is adequate for causal explanations of device behavior? How can there be any confidence in the analysis of a novel device?

title: The Social Life of Documents
abstract: Documents are evolving as means for structuring and navigating information space, and resources for constructing and negotiating social space

title: Why AM and Eurisko Appear to Work
abstract: Seven years ago, the AM program was constructed as an experiment in learning by discovery. Its source of power was a large body of heuristics, rules which guided it toward fruitful topics of investigation, toward profitable experiments to perform, toward plausible hypotheses and definitions. "Other heuristics evaluated those discoveries for utility and "interestingness", and they were added to AM's vocabulary of concepts. AM's ultimate limitation apparently was due to its inability to discover new, powerful, domain-specific heuristics for the various new fields it uncovered. At that time, it seemed straight-forward to simply add Heuretics (the study of heuristics) as one more field in which to let AM explore, observe, define, and develop. That task - learning new heuristics by discovery - turned out to be much more difficult than was realized initially, and we have just now achieved some successes at it. Along the way, it became clearer why AM had succeeded in the first place, and why it was so difficult to use the same paradigm to discover new heuristics. This paper discusses those recent insights. They spawn questions about "where the meaning really resides" in the concepts discovered by AM. This leads to an appreciation of the crucial and unique role of representation in theory formation, a role involving the relationship between Form and Content.

title: A Qualitative Physics Based on Confluences
abstract: A qualitative physics predicts and explains the behavior of mechanisms in qualitative terms. The goals for the qualitative physics are (1) to be far simpler than the classical physics and yet retain all the important distinctions (e.g., state, oscillation, gain, momentum) without invoking the mathematics of continuously varying quantities and differential equations, (2) to produce causal accounts of physical mechanisms that are easy to understand, and (3) to provide the foundations for commonsense models for the next generation of expert systems. This paper presents a fairly encompassing account of qualitative physics. First, we discuss the general subject of naive physics and some of its methodological considerations. Second, we present a framework for modeling the generic behavior of individual components of a device based on the notions of qualitative differential equations (confluences) and qualitative state. This requires developing a qualitative version of the calculus. The modeling primitives induce two kinds of behavior, intrastate and interstate, which are governed by different laws. Third, we present algorithms for determining the behavior of a composite device from the generic behavior of its components. Fourth, we examine a theory of explanation for these predictions based on logical proof. Fifth, we introduce causality as an ontological commitment for explaining how devices behave.

title: Subdivisions and Chromatic Roots
abstract: It is well known that chromatic polynomials can have roots (chromatic roots) of arbitrarily large modulus. We prove here that for any graph G and any ?>0, there is a subdivision of G all of whose chromatic roots lie in |z?1|<1+?.

title: On the Chromatic Roots of Generalized Theta Graphs
abstract: The generalized theta graph ?s1, ?, sk consists of a pair of endvertices joined by k internally disjoint paths of lengths s1, ?, sk?1. We prove that the roots of the chromatic polynomial ? of a k-ary generalized theta graph all lie in the disc|z?1|?1+o(1)]k/logk, uniformly in the path lengths si. Moreover, we prove that ?2, ?, 2?K2, k indeed has a chromatic root of modulus 1+o(1)]k/logk. Finally, for k?8 we prove that the generalized theta graph with a chromatic root that maximizes |z?1| is the one with all path lengths equal to 2; we conjecture that this holds for all k.

title: The ribonuclease P database
abstract: The Ribonuclease P Sequence database is a compilation of RNase P sequences, sequence alignments, secondary structures, three-dimensional models, and accessory information. In its initial form, the database contains information on RNase P RNA in bacteria and archaea, and RNase P protein in bacteria. The sequences themselves are presented phylogenetically ordered and aligned. The database also contains secondary structures of bacterial and archaeal RNAs, including specially annotated 'reference' secondary structures of Escherichia coli and Bacillus subtilis RNase P RNAs, a minimum phylogenetic consensus structure, and coordinates for models of three-dimensional structure.

title: The Complexity of Generalized Graph Colorings
abstract: Given a graph property P and positive integer k, a P k-coloring of a graph G is an assignment of one of k colors to each vertex of the graph so that the subgraphs induced by each color class have property P. This notion generalizes the standard definition of graph coloring, and has been investigated for many properties. We consider here the complexity of the decision problem. In particular, for the property —G, of not containing an induced subgraph isomorphic to G, we conjecture (and provide strong evidence) that —G k-colorability is NP-complete whenever G has order at least 3 and k ⩾ 2. The techniques rely on new NP-completeness results for hypergraph colorings.

title: G-functions for the hermeneutic circle of evolution
abstract: Evolution by natural selection may include both frequency and density-dependence. Frequency-dependent selection is a kind of hermeneutic circle. As a literary term (and a school of philosophy), a hermeneutic circle describes how each word of a sentence or paragraph simultaneously draws its meaning from its context (the other words) and contributes towards the context. Frequency dependence is like this. Under frequency dependence, the fitness of an individual is not only influenced by its own heritable phenotype (in evolutionary game theory heritable phenotype = strategy) but by the frequency of strategies found among others in the population. And, the fitness accrued by individuals with a particular strategy will in time influence the frequency of strategies in the population. The challenge is to develop conceptual and modeling tools that allow us to determine the outcome of this hermeneutic circle of evolution. We need a fitness concept that defines the fitness of (or payoff to) to individuals as influenced by both their own strategy and the strategies of others. And, this fitness formulation must describe how these payoffs translate into changes in strategy frequencies. The fitness generating function, or G-function, provides this service for evolutionary game theory.