To dream the invisible dream
often credited as the creator of the computer game industry, explores the “Relationships between Fun and the Computer Business.” In his article he reminisces, assesses, and projects the effects from the game industry to the computer industry as a whole. Bushnell’s article makes tangible some of the incredible distance we’ve come since the 1970s—from a world where manufacturers didn’t take cathode-ray tube use in the computer industry seriously to a time when most two-year-old children know about computers. Bushnell’s way is to mix lessons learned from the game industry with some as-yet unexplored visions of the way we will play. Henry Lieberman’s work has been that of creating programming and idea presentation environments using his favorite tools of creation objects (his work on actors), dynamic languages (his work on garbage collection), and interactive environments (his work on programming by example). Lieberman’s article, “Intelligent Graphics,” focuses on the inventive serendipity that has and can come out of the relationship between AI and graphics—an idea promoted by yet another pioneer, Muriel Cooper. He also briefly discusses programming by example, a style of interaction that he has been working to demonstrate and promote over the last couple of decades. Ken Kahn also cares deeply about programming languages, having devoted his research career to creating Prolog interpreters, parallel logic systems, and logic-oriented systems. In his article, we see him engaged in his first love, that of creating visual approaches for thinking about programs. Watching programs execute, seeing their structure, seeing their function, organizing them—all with the underlying goal of making programming as easy as child’s play. Finally, as you look to my article, you see me not working or talking about any one idea as I could, but giving a review with some context that describes many of the ideas shaping the way people are using computers today. I hope this eclectic collection of articles can serve as a celebration of our temptations to explore and design the ways computers will help us communicate, create, and record our experiences.

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: 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: Steps Toward Automatic Theory Formation
abstract: This paper describes a theory formation system which can discover a partial axiomization of a data base represented as extensionally defined binary relations.- The system first discovers all possible intensional definitions of each binary relation in terms of the others. It then determines a minimal set of these relations from which the others can be defined. It then attempts to discover all the ways the relations of this minimal set can interact with each other, thus generating a set of inference rules. Although the system was originally designed to explore automatic techniques for theory construction for question-answering systems, it is currently being expanded to function as a symbiotic system to help social scientists explore certain kinds of data bases.

title: Foundations of Envisioning
abstract: 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: Theories of Causal Ordering
abstract: This paper is a response to Iwasaki and Simon  which criticizes de Kleer and Brown . 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.

title: Computational and neural mechanisms of task switching
abstract: 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.

title: Graph coloring satisfying restraints
abstract: For an integer k ⩾2, a proper k-restraint on a graph G is a function from the vertex set of G to the set of k -colors. A graph G is amenably k-colorable if, for each nonconstant proper k -restraint r on G , there is a k -coloring c of G with c ( v )≠ r ( v ) for each vertex v of G . A graph G is amenable if it is amenably k -colorable and k is the chromatic number of G . For any k ≠3, there are infinitely many amenable k -critical graphs. For k ⩾ 3, we use a construction of B. Toft and amenable graphs to associate a k -colorable graph to any k -colorable finite hypergraph. Some constructions for amenable graphs are given. We also consider a related property—being strongly critical —that is satisfied by many critical graphs, including complete graphs. A strongly critical graph is critical and amenable, but the converse is not always true. The Dirac join operation preserves both amenability and the strongly critical property. In addition, the Hajos construction applied to a single edge in each of two strongly k -critical graphs yields an amenable graph. However, for any k ⩾5, there are amenable k -critical graphs for which the Hajos construction on two copies is not amenable.

title: Proximity-aware directory-based coherence for multi-core processor architectures
abstract: As the number of cores increases on chip multiprocessors, coherence is fast becoming a central issue for multi-core performance. This is exacerbated by the fact that interconnection speeds are not scaling well with technology. This paper describes mechanisms to accelerate coherence for a multi-core architecture that has multiple private L2 caches and a scalable point-to-point interconnect between cores. These techniques exploit the differences in geometry between chip multiprocessors and traditional multiprocessor architectures.
 Directory-based protocols have been proposed as a scalable alternative to snoop-based protocols. In this paper, we discuss implementations of coherence for CMPs and propose and evaluate a novel directory-based coherence scheme to improve the performance of parallel programs on such processors. Proximity-aware coherence accelerates read and write misses by initiating cache-to-cache transfers from the spatially closest sharer. This has the dual benefit of eliminating unnecessary accesses to off-chip memory, and minimizing the distance over which communicated data moves across the network. The proposed schemes result in speedups up to 74.9% for our workloads.

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: 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.