15658893
Theories of Causal Ordering
Abstract This paper is a response to Iwasaki and Simon [14] which criticizes de Kleer and Brown [8]. We argue that many of their criticisms, particularly concerning causality, modeling and stability, originate from the difference of concerns between engineering and economics. Our notion of causality arises from considering the interconnections of components, not equations. When no feedback is present, the ordering produced by our qualitative physics is similar to theirs. However, when feedback is present, our qualitative physics determines a causal ordering around feedback loops as well. Causal ordering is a general technique not only applicable to qualitative reasoning. Therefore we also explore the relationship between causal ordering and propagation of constraints upon which the methods of qualitative physics are based.
1800673
Why AM and Eurisko Appear to Work
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.
17008578
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?
38979633
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.
45989851
The Social Life of Documents
Documents are evolving as means for structuring and navigating information space, and resources for constructing and negotiating social space
205225115
The ribonuclease P database
Ribonuclease P is responsible for the 5'-maturation of tRNA precursors. Ribonuclease P is a ribonucleoprotein, and in bacteria (and some Archaea) the RNA subunit alone is catalytically active in vitro, i.e. it is a ribozyme. The Ribonuclease P Database is a compilation of ribonuclease P sequences, sequence alignments, secondary structures, three-dimensional models and accessory information, available via the World Wide Web at the following URL: http://www.mbio.ncsu.edu/RNaseP/home .html
18896340
On the Roots of Chromatic Polynomials
It is proved that the chromatic polynomial of a connected graph with n vertices and m edges has a root with modulus at least (m?1)/(n?2); this bound is best possible for trees and 2-trees (only). It is also proved that the chromatic polynomial of a graph with few triangles that is not a forest has a nonreal root and that there is a graph with n vertices whose chromatic polynomial has a root with imaginary part greater thann/4.
45045031
Well-Covered Vector Spaces of Graphs
For any field ${\bf F}$, the set of all functions $f : V(G) \rightarrow {\bf F}$ whose sum on each maximal independent set is constant forms a vector space over ${\bf F}$. In this paper, we show that the dimension can vary depending on the characteristic of the field. We also investigate the dimensions of these vector spaces and show that while some families, such as chordal graphs, have unbounded dimension, other families, such as nonempty circulant graphs of prime order, have bounded dimension.
10597458
Computational and neural mechanisms of task switching
Switching between tasks that overlap in perceptual and response characteristics is assumed to rely upon the maintenance of task representations in prefrontal cortex (PFC). However, task-switching studies demonstrate ''switch costs,'' even when there is sufficient time to prepare for a new task. These costs suggest that task-switching performance reflects a complex interplay between priming and the updating and maintenance of task representations. We describe a computational model in which this interaction is made explicit and linked to the dynamics of PFC. Simulation results account for a variety of empirical phenomena and predict a double dissociation in lateral PFC that was subsequently identified.
16943733
Chromatic polynomials and order ideals of monomials
Abstract One expansion of the chromatic polynomial π ( G , x ) of a graph G relies on spanning trees of a graph. In fact, for a connected graph G of order n , one can express π(G,x)=(−1) n−1 x ∑ i=1 n−1 t i (1−x) i ), where t i is the number of spanning trees with external activity 0 and internal activity i . Moreover, it is known (via commutative ring theory) that t i arises as the number of monomials of degree n − i − 1 in a set of monomials closed under division. We describe here how to explicitly carry out this construction algebraically. We also apply this viewpoint to prove a new bound for the roots of chromatic polynomials.