Human-Document Interaction Area / ISTL / PARC

 
Overview
People
Publications
Skills
Projects
Collaborations
 
Sensemaking
    Recent publications by HDI members:

Reverse chronological order, then alphabetical by first author.

Availability and distribution subject to terms of respective copyright agreements. In particular, the availability of some items might be delayed until date of publication, and other items might not be available for general download at all. If you are interested in an item for which a download link does not appear, please contact the author (see our People page for e-mail addresses), as often the copyright agreements allow limited personal distribution.


T.M. Breuel, W.C. Janssen, K. Popat, and H.S. Baird. Paper to PDA. In Proceedings of 16th International Conference on Pattern Recognition (ICPR2002), page 476, August 2002.
BibTeX entry, Postscript version, PDF version
Kris Popat, Daniel H. Greene, and Tze-Lei Poo. Adaptive stack algorithm in document image decoding. In Proceedings of 16th International Conference on Pattern Recognition (ICPR2002), page 231, August 2002.
BibTeX entry, Postscript version, PDF version
Paula S. Newman. Exploring discussion lists: Steps and directions. In Proceedings of Joint Conference of Digital Libraries, Portland, Oregon, July 2002.
BibTeX entry, PDF version

This paper describes some new facilities for exploring archived email-based discussion lists. The facilities exploit some specific properties of email messages to obtain improved archived overviews, and then use new tree visualizations, developed for the purpose, to obtain thread overviews and mechanisms to aid in the coherent reading of threads.

Patrick Baudisch, Nathan Good, Victoria Bellotti, and Pam Schraedley. Keeping Things in Context: A Comparative Evaluation of Focus Plus Context Screens, Overviews, and Zooming. In CHI 2002, Minneapolis, Minnesota, April 2002.
BibTeX entry

Users working with documents that are too large and de-tailed to fit on the user's screen (e.g. chip designs) have the choice between zooming or applying appropriate visu-alization techniques. In this paper, we present a compari-son of three such techniques. The first, focus plus context screens, are wall-size low-resolution displays with an em-bedded high-resolution display region. This technique is compared with overview plus detail and zooming/panning. We interviewed fourteen visual surveillance and design professionals from different areas (graphic design, chip design, air traffic control, etc.) in order to create a representative sample of tasks to be used in two experimental comparison studies. In the first experiment, subjects using focus plus context screens to extract information from large static documents completed the two experimental tasks on average 21% and 36% faster than when they used the other interfaces. In the second experiment, focus plus context screens allowed subjects to reduce their error rate in a driving simulation to less than one third of the error rate of the competing overview plus detail setup.

Patrick Baudisch and Nathan Good. Focus Plus Context Screens: Displays for Users Working with Large Visual Documents. In CHI 2002 conference companion, Minneapolis, Minnesota, April 2002.
BibTeX entry

Users working with documents that are too large and de-tailed to fit on the user's screen (e.g. chip designs) have the choice between zooming or applying appropriate visu-alization techniques. In this demonstration, we will pre-sent focus plus context screens-wall-size low-resolution displays with an embedded high-resolution display region. They allow users to view details of a document up close, while simultaneously seeing peripheral parts of the docu-ment in lower resolution. Unlike overview plus detail, focus plus context screens do not require users to visually switch between multiple views. Unlike fisheye views, fo-cus plus context screens do not introduce distortion.

Paula S. Newman. Email archive overviews using subject indexes. In Proceedings of Conference on Human Factors and Computing Systems (CHI2002), pages 652-653, Minneapolis, Minnesota, April 2002.
BibTeX entry, PDF version

Archived discussion lists are becoming significant reference sources. This paper describes a new type of overview for such lists, using a back-of-the-book style index containing headwords selected from subject lines and subentries derived from their subject-line contexts.

Eric Gaussier, Cyril Goutte, Kris Popat, and Francine Chen. A hierarchical model for clustering and categorising documents. In Proceedings of the 24th BCS-IRSG European Colloquium on IR Research, March 2002.
BibTeX entry, Postscript version, PDF version

We propose a new hierarchical generative model for textual data, where words may be generated by topic specilic distributions at any level in the hierarchy. This model is naturally well-suited to clus- tering documents in preset or automatically generated hierarchies, as well as categorising new documents in an existing hierarchy. Training algorithms are derived for both cases, and illustrated on real data by clustering news stories and categorising newsgroup messages. Finally, the generative model may be used to derive a Fisher kernel expressing similarity between documents.

Henry S. Baird and Kris Popat. Human interactive proofs and document image analysis. In Proceedings of Document Analysis Systems 2002, pages 507-518, 2002.
BibTeX entry
Gary E. Kopec, Maya R. Said, and Kris Popat. N-gram language models for document image decoding. In Proceedings of IS&T/SPIE Electronic Imaging 2002: Document Recognition and Retrieval IX, January 2002.
BibTeX entry, Postscript version, PDF version

This paper explores the problem of incorporating linguistic constraints into document image decoding, a communication theory approach to document recognition. Probabilistic character n-grams (n=2-5) are used in a two-pass strategy where the decoder first uses a very weak language model to generate a lattice of candidate output strings. These are then re-scored in the second pass using the full language model. Experimental results based on both synthesized and scanned data show that this approach is capable of improving the error rate by a factor of two to ten depending on the quality of the data and the details of the language model used.

Lance Good and Benjamin B. Bederson. Zoomable user interfaces as a medium for slide show presentations. Information Visualization, 1(1), 2002.
BibTeX entry, PDF version

In this paper, we propose Zoomable User Interfaces as an alternative presentation medium to address several common presentation problems. Zoomable User Interfaces offer new techniques for managing multiple versions of a presentation, providing interactive presentation navigation, and distinguishing levels of detail. These zoomable presentations may also offer several cognitive benefits over their commercial slide show counterparts. We also introduce CounterPoint, a tool to simplify the creation and delivery of zoomable presentations. We discuss the techniques we have used to make authoring and navigation manageable in the multidimensional space. Lastly, we present some of the visualization principles we have compiled for designing these types of presentations.

Patrick Baudisch, Nathan Good, and Paul Stewart. Focus Plus Context Screens: Combining Display Technology with Visualization Techniques. In Symposium on User Interface Software and Technology (UIST 2001), Orlando, Florida, November 2001.
BibTeX entry, PDF version

Computer users working with large visual documents, such as large layouts, blueprints, or maps perform tasks that require them to simultaneously access overview information while working on details. To avoid the need for zooming, users currently have to choose between using a sufficiently large screen or applying appropriate visualization techniques. Currently available hi-res wall-size screens, however, are cost-intensive, space-intensive, or both. Visualization techniques allow the user to more efficiently use the given screen space, but in exchange they either require the user to switch between multiple views or they introduce distortion. In this paper, we present a novel approach to simultaneously display focus and context information. Focus plus context screens consist of a hi-res display and a larger low-res display. Image content is displayed such that the scaling of the display content is preserved, while its resolution may vary according to which display region it is displayed in. Focus plus context screens are applicable to practically all tasks that currently use overviews or fisheye views, but unlike these visualization techniques, focus plus context screens provide a single, non-distorted view. We present a prototype that seamlessly integrates an LCD with a projection screen and demonstrate four applications that we have adapted so far.

Kristina Toutanova, Francine Chen, Kris Popat, and Thomas Hofmann. Text classification in a hierarchical mixture model for small training sets. In Proceedings of the ACM Conference on Information and Knowledge Management (CIKM), November 2001.
BibTeX entry, Postscript version, PDF version

Documents are commonly categorized into hierarchies of topics, such as the ones maintained by Yahoo! and the Open Directory project, in order to facilitate browsing and other interactive forms of information retrieval. In addition, topic hierarchies can be utilized to overcome the sparseness problem in text categorization with a large number of categories, which is the main focus of this paper. This paper presents a hierarchical mixture model which extends the standard naive Bayes classifier and previous hierarchical approaches. Improved estimates of the term distributions are made by differentiation of words in the hierarchy according to their level of generality/specificity. Experiments on the Newsgroups and the Reuters-21578 dataset indicate improved performance of the proposed classifier in comparison to other state-of-the-art methods on datasets with a small number of positive examples.

Dan S. Bloomberg, Thomas P. Minka, and Kris Popat. Document image decoding using iterated complete path search with subsampled heuristic scoring. In Proceedings of the IAPR 2001 International Conference Document Analysis and Recognition (ICDAR 2001), September 2001.
BibTeX entry, Postscript version, PDF version

It has been shown that the computation time of Document Image Decoding can be significantly reduced by employing heuristics in the search for the best decoding of a text line. In the Iterated Complete Path (ICP) method, template matches are performed only along the best path found by dynamic programming on each iteration. When the best path stabilizes, the decoding is optimal and no more template matches need be performed. In this way, only a tiny fraction of potential template matches must be evaluated, and the computation time is typically dominated by the evaluation of the initial heuristic upper-bound for each template at each location in the image. The time to compute this bound depends on the resolution at which the matching scores are found. At lower resolution, the heuristic computation is reduced, but because a weaker bound is used, the number of Viterbi iterations is increased. We present the optimal (lowest upper-bound) heuristic for any degree of subsampling of multilevel template and/or interpolation, for use in text line decoding with ICP. The optimal degree of subsampling depends on image quality, but it is typically found that a small amount of template subsampling is effective in reducing the overall decoding time.

Kris Popat. Decoding of text lines in grayscale document images. In Proceedings of the 2001 International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2001), Salt Lake City, Utah, May 2001. IEEE.
BibTeX entry, Postscript version, PDF version
Thomas M. Breuel and Kris Popat. Recent work in the document image decoding group at xerox parc. In Proceedings of the DOD-sponsored Symposium on Document Image Understanding Technology (SDIUT 2001), April 2001.
BibTeX entry, Postscript version, PDF version
Thomas P. Minka, Dan S. Bloomberg, and Kris Popat. Document image decoding using the iterated complete path heuristic. In Proceedings of IS&T/SPIE Electronic Imaging 2001: Document Recognition and Retrieval VIII, January 2001.
BibTeX entry, Postscript version, PDF version
P. Newman. Treetables and other visualizations for email threads. 2001.
BibTeX entry, PDF version

In this paper we describe some new visualization methods for email threads. The methods concatenate initial message texts, or full texts shorn of extraneous material, into logical groupings embedded in, or closely aligned with, thread structure representations. The results are intended to provide useful thread overviews, and to enable coherent, efficient reading of individual thread content.

Kris Popat. Document image compression by adaptive-offset quantization. In Proceedings of IS&T/SPIE Electronic Imaging 2001: Document Recognition and Retrieval VIII, January 2001.
BibTeX entry, Postscript version, PDF version
Kris Popat, Dan Greene, Justin Romberg, and Dan S. Bloomberg. Adding linguistic constraints to document image decoding: Comparing the iterated complete path and stack algorithms. In Proceedings of IS&T/SPIE Electronic Imaging 2001: Document Recognition and Retrieval VIII, January 2001.
BibTeX entry, Postscript version, PDF version
Polle T. Zellweger, Niels Olof Bouvin, Henning Jehoej, and Jock D. Mackinlay. Fluid annotations in an open world. In Proceedings of the Twelfth ACM Hypertext Conference, pages 9-18, 2001.
BibTeX entry, PDF version

Fluid Documents use animated typographical changes to provide a novel and appealing user experience for hypertext browsing and for viewing document annotations in context. This paper describes an effort to broaden the utility of Fluid Documents by using the open hypermedia Arakne Environment to layer fluid annotations and links on top of arbitrary HTML pages on the World Wide Web. Changes to both Fluid Documents and Arakne are required.

Polle T. Zellweger and Jock D. Mackinlay. The fluid reading primer: Animated decoding support for emergent readers. In Proceedings of the World Conference on Educational Multimedia, Hypermedia & Telecommunications (ED-MEDIA 2001), 2001.
BibTeX entry

We have developed a prototype application called the Fluid Reading Primer to help emergent readers with the process of decoding written words into their spoken forms. When a reader requests help for a particular word, the Fluid Primer uses interactive animation to break the word apart to visually indicate its constituent sounds. The Fluid Primer can also play back audio versions of each segmented constituent sound, as well as the blended complete word. We envision that our method could be incorporated into future e-books to provide scaffolding on demand for readers of arbitrary texts. Moreover, we believe that the animations shown by our tool provide a valuable visualization of the decoding steps that will help readers learn to perform the same steps more quickly and confidently on their own.

Kris Popat, Dan Bloomberg, and Dan Greene. Adding linguistic constraints to document image decoding. In Proceedings of the 4th IAPR Workshop on Document Analysis Systems (DAS 2000), December 2000.
BibTeX entry, Postscript version, PDF version
Benjamin B. Bederson, Jon Meyer, and Lance Good. Jazz: An Extensible Zoomable User Interface Graphics Toolkit in Java. In Symposium on User Interface Software and Technology (UIST 2000), pages 171-180, San Diego, California, November 2000.
BibTeX entry, PDF version

In this paper we investigate the use of scene graphs as a general approach for implementing two-dimensional (2D) graphical applications, and in particular Zoomable User Interfaces (ZUIs). Scene graphs are typically found in three-dimensional (3D) graphics packages such as Sun's Java3D and SGI's OpenInventor. They have not been widely adopted by 2D graphical user interface toolkits. To explore the effectiveness of scene graph techniques, we have developed Jazz, a general-purpose 2D scene graph toolkit. Jazz is implemented in Java using Java2D, and runs on all platforms that support Java 2. This paper describes Jazz and the lessons we learned using Jazz for ZUIs. It also discusses how 2D scene graphs can be applied to other application areas.

Kris Popat and Dan S. Bloomberg. Two-stage lossy/lossless compression of grayscale document images. In Mathematical Morphology and its applications to image and signal processing: Proceedings of the Fifth International Symposium on Mathematical Morphology (ISMM 2000), June 2000.
BibTeX entry, Postscript version, PDF version
Michelle Q. Wang Baldonado, Allison Woodruff, and Allan Kuchinsky. Guidelines for using multiple views in information visualization. In Proceedings of Advanced Visual Interfaces 2000, pages 110-119, Palermo, Italy, May 2000.
BibTeX entry
Mike Spreitzer and Bill Janssen. HTTP `Next Generation'. In Proceedings of the 9th World Wide Web Conference, Amsterdam, Netherlands, May 2000.
BibTeX entry, HTML version

We report on the results of the Protocol Design Group of the W3C's HTTP ``Next Generation'' Activity. The group produced and measured a prototype that shows it is possible, largely using familiar engineering principles, to make simultaneous improvements in the following problem areas of HTTP/1.1: (1) the layering of other application protocols over HTTP, (2) modularity and extensibility, (3) networking performance and fairness, (4) the rigid binding between identifiers and protocol stacks, and (5) the opacity of layered traffic to firewalls. The prototype also suggests that these can be done in a way that may lead to unifying the web with related middleware systems such as COM, CORBA, and Java RMI.

Steve B. Cousins, Michelle Baldonado, and Andreas Paepcke. A systems view of annotations. Technical report, Xerox PARC, April 2000.
BibTeX entry, PDF version
Michelle Q Wang Baldonado. A user-centered interface for information exploration in a heterogeneous digital library. Journal of the American Society for Information Science (JASIS), 51(3):297-310, 2000.
BibTeX entry
Michelle Baldonado, Steve Cousins, Jacek Gwizdka, and Andreas Paepcke. Notable: At the intersection of annotations and handheld technology. In H.-W. Gellersen and P. Thomas, editors, Lecture Notes in Computer Science, volume 1927 of Springer Lecture Notes in Computer Science, pages 100-113. Springer-Verlag, 2000.
BibTeX entry
Bay-Wei Chang, Jock D. Mackinlay, and Polle T. Zellweger. Fluidly revealing information in fluid documents. In Proceedings of the Smart Graphics 2000 AAAI Spring Symposium, Stanford University, CA, 2000.
BibTeX entry
Polle T. Zellweger, Susan Harkness Regli, Jock D. Mackinlay, and Bay-Wei Chang. The impact of fluid documents on reading and browsing: An observational study. In Proceedings of CHI 2000, ACM Conference on Human Factors in Computing Systems, 2000.
BibTeX entry, PDF version

Fluid Documents incorporate additional information into a page by adjusting typography using interactive animation. One application is to support hypertext browsing by providing glosses for link anchors. This paper describes an observational study of the impact of Fluid Documents on reading and browsing. The study involved six conditions that differ along several dimensions, including the degree of typographic adjustment and the distance glosses are placed from anchors. Six subjects read and answered questions about two hypertext corpora while being monitored by an eyetracker. The eyetracking data revealed no substantial differences in eye behavior between conditions. Gloss placement was significant: subjects required less time to use nearby glosses. Finally, the reaction to the conditions was highly varied, with several conditions receiving both a best and worst rating on the subjective questionnaires. These results suggest implications for the design of dynamic reading environments.

Mark Stefik, Michelle Baldonado, Daniel Bobrow, Stuart Card, John Everett, Giuliana Lavendel, David Marimon, Paula Newman, Dan Russell, and Steve Smoliar. The knowledge sharing challenge: The sensemaking white paper, November 1999.
BibTeX entry, PDF version
Toby Berger, Philip Chou, Michelle Effros, Nariman Farvardin, Thomas Fischer, William R. Gardner, Robert M. Gray, Nikil S. Jayant, Rajiv Laroia, Upamanyu Madhow, Michael W. Marcellin, James W. Modestino, David L. Neuhoff, Alon Orlitsky, Kris Popat, Kannan Ramchandran, James A. Storer, Vinay Vaishampayan, Kenneth Zeger, and Zhen Zhang. Workshop report: NSF sponsored workshop on joint source-channel coding. Technical report, California Institute of Technology, October 1999.
BibTeX entry, Postscript version, PDF version
Chris Jacobi, Bill Janssen, Dan Larner, Paula Newman, and Mike Spreitzer. ILU: Inter-Language Unification, version 2.0beta1, August 1999.
BibTeX entry, Web version

The Inter-Language Unification system (ILU) is a multi-language object interface system, released under an open-source licence. The object interfaces provided by ILU hide implementation distinctions between different languages, between different address spaces, and between operating system types. ILU can be used to build multi-lingual object-oriented libraries (``class libraries'') with well-specified language-independent interfaces. It can also be used to implement distributed systems. It can also be used to define and document interfaces between the modules of non-distributed programs. ILU interfaces can be specified in either the OMG's CORBA Interface Definition Language (OMG IDL), or ILU's own Interface Specification Language (ISL).

Michelle Baldonado, Steve Cousins, Brian Lee, and Andreas Paepcke. Notable: An annotation system for networked handheld devices. In Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI '99) Extended Abstracts, pages 210-211, Pittsburgh, Pennsylvania, May 1999.
BibTeX entry, Powerpoint version
Andreas Paepcke, Michelle Q. Wang Baldonado, Chen-Chuan K. Chang, Steve Cousins, and Hector Garcia-Molina. Using distributed objects to build the stanford digital library infobus. IEEE Computer, 32(2):80-87, February 1999.
BibTeX entry, Web version

A report from the trenches: Stanford's development of a technical infrastructure for digital libraries brings a vision of huge libraries spanning the Internet closer to reality.

Mark J. Stefik. The Internet Edge: Social, Technical, and Legal Challenges for a Networked World. The MIT Press, Cambridge, Massachusetts, 1999.
BibTeX entry, Order on-line

Sometimes when we face change, we feel conflicting forces driving us forward and pulling us back. This place of tension and confusion can be called an edge. The Internet edge is our collective struggle to change as the world becomes more connected. Turmoil at the Internet edge occurs around interacting social, legal, and technological realms. Examples include issues of online privacy, censorship, digital copyright, and untaxed business competition over the Net. Such issues reflect conflicts between values - local and global, individual and corporate, democratic and nondemocratic. This book is an eagle's eye view of the Internet edge. It is about the experiences of those who encountered similar issues as they built precursors to the Net such as videotext, teletext, and the Source. It is about the trends in technology that will make the Net of the next few years a very different experience from the desktop surfing of today. Finally, it is about how old myths of magic, power, and control can help us to understand our fascination with and fear of new technologies.

Bill Janssen. A `Next Generation' Architecture for HTTP. IEEE Internet Computing, 3(1):69-73, Jan/Feb 1999.
BibTeX entry, PDF version

The HTTP `Next Generation' project of the World Wide Web Consortium is a comprehensive re-thinking of the Web's underlying protocol, the HyperText Transfer Protocol. It provides a framework for defining new applications for the Web, an efficient and powerful messaging system which supports CORBA, DCOM, and Java RMI directly, and a multiplexing transport layer which provides for multiple bi-directional virtual connections over a single TCP/IP connection. Preliminary measurements suggest HTTP-NG is more efficient than HTTP 1.1 in performing the primary Web function of retrieving a Web page.

John Perry Barlow, Lawrence Lessig, Charles Mann, and Mark J. Stefik. Life, Liberty, and the Pursuit of Copyright. The Atlantic Unbound, September 1998.
BibTeX entry, HTML version
Michelle Baldonado, Seth Katz, Andreas Paepcke, Chen-Chuan K. Chang, Hector Garcia-Molina, and Terry Winograd. An extensible constructor tool for the rapid, interactive design of query synthesizers. In Proceedings of the Third ACM International Conference on Digital Libraries (DL '98), pages 19-28, Pittsburgh, Pennsylvania, June 1998.
BibTeX entry, Slides
Mehran Sahami, Salim Yusufali, and Michelle Q. W. Baldonado. Sonia: A service for organizing networked information autonomously. In Proceedings of the Third ACM International Conference on Digital Libraries (DL '98), pages 200-209, Pittsburgh, Pennsylvania, June 1998.
BibTeX entry
Michelle Q Wang Baldonado. Interfaces for information exploration: Seeing the forest. In Workshop: Innovation and Evaluation in Information Exploration Interfaces (at CHI '98), Los Angeles, California, April 1998. The HTML file is from the workshop site.
BibTeX entry, HTML version
Michelle Q Wang Baldonado and Terry Winograd. Hi-cites: Dynamically created citations with active highlighting. In Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI '98), pages 408-415, Los Angeles, California, April 1998. The demo requires IE 4.0 or better.
BibTeX entry, PDF version, Web Demo
Martin Roscheisen, Michelle Baldonado, Kevin Chang, Luis Gravano, Steven Ketchpel, and Andreas Paepcke. The stanford infobus and its service layers: Augmenting the internet with higher-level information management protocols. In A. Barth, M. Breu, A. Endres, and A. de Kemp, editors, Digital Libraries in Computer Science: the MeDoc Approach, pages 213-30. Springer-Verlag, Berlin, Germany, 1998. Includes a description of the metadata architecture as well as other InfoBus layers.
BibTeX entry
Bay-Wei Chang, Jock D. Mackinlay, Polle T. Zellweger, and Takeo Igarashi. A negotiation architecture for fluid documents. In Proceedings of the ACM Conference on User Interface Software and Technology, pages 123-132, 1998.
BibTeX entry, PDF version

The information presented in a document often consists of primary content as well as supporting material such as explanatory notes, detailed derivations, illustrations, and the like. We introduce a class of user interface techniques for fluid documents that supports the reader’s shift to supporting material while maintaining the context of the primary material. Our approach initially minimizes the intrusion of supporting material by presenting it as a small visual cue near the annotated primary material. When the user expresses interest in the annotation, it expands smoothly to a readable size. At the same time, the primary material makes space for the expanded annotation. The expanded supporting material must be given space to occupy, and it must be made salient with respect to the surrounding primary material. These two aspects, space and salience, are subject to a negotiation between the primary and supporting material. This paper presents the components of our fluid document techniques and describes the negotiation architecture for ensuring that the presentations of both primary and supporting material are honored.

Takeo Igarashi, Jock D. Mackinlay, Bay-Wei Chang, and Polle T. Zellweger. Fluid visualization for spreadsheet structures. In Proceedings of the 1998 Conference on Visual Languages, pages 118-125, 1998.
BibTeX entry, PDF version

Spreadsheets augment a visible tabular layout with invisible formulas. Direct manipulations of the tabular layout may or may not result in the desired changes to the formulas. The user is forced to explore the individual cells to find, verify, and modify the formulas, which causes heavy cognitive overhead. We present a set of techniques that make these formulas and their resulting dataflow structure easily accessible while maintaining the natural appearance of the spreadsheet. Transient local views visualize dataflow structures associated with individual cells, while static global views and animated global explanations visually present the entire dataflow structure at once. Semantic navigation enables the user to navigate through the dataflow structure interactively, and visual editing techniques make it possible to construct formulas using graphical editing techniques. Central to these techniques is the use of animation and lightweight interaction for rapid and non-intrusive visualization. Our prototype implementation suggests that these techniques can greatly improve the expressive power of current spreadsheets as well as other applications that have rich underlying structures.

Polle T. Zellweger, Bay-Wei Chang, and Jock D. Mackinlay. Fluid links for informed and incremental link transitions. In Proceedings of the Ninth ACM Conference on Hypertext, pages 50-57, 1998.
BibTeX entry, PDF version

We have developed a novel user interface technique for hypertext, called fluid links, that has several advantages over current methods. Fluid links provide additional information at a link source to support readers in choosing among links and understanding the structure of a hypertext. Fluid links present this information in a convenient location that does not obscure the content or layout of the source material. The technique uses perceptually-based animation to provide a natural and lightweight feeling to readers. In their richer forms, fluid links can provide a novel hypertext navigation paradigm that blurs the boundaries of hypertext nodes and can allow readers to fluidly control the focus on the material to support their current reading goals.

Michelle Q Wang Baldonado. An Interactive, Structure-Mediated Approach to Exploring Information in a Heterogeneous, Distributed Environment. PhD thesis, Stanford University, December 1997. The slides are from the orals.
BibTeX entry, PDF version, Slides, Abstract
Michelle Baldonado, Chen-Chuan Chang, Luis Gravano, and Andreas Paepcke. The stanford digital library metadata architecture. International Journal of Digital Libraries, 1(2):108-21, September 1997.
BibTeX entry
Mark J. Stefik and Alex Silverman. The Bit and the Pendulum: Balancing the interests of stakeholders in digital publishing. American Programmer, 18:18-35, September 1997.
BibTeX entry, PDF version

Personal computers and computer networks have the potential to become an ideal basis for digital publishing. But the potential for digital publishing remains just that-a potential. The market for digital works remains nascent, because the medium has failed so far to balance the interests of important stakeholders. Computers and the digital medium are sometimes seen as the root of this problem. In this article, we explore how computers designed as trusted systems could bring things more into balance.

Mark J. Stefik and Giuliana Lavendel. Libraries and digital property rights. In Proceedings of the Digital Library Conference, Pisa, Italy, September 1997.
BibTeX entry, PDF version

The realization of the digital library - a computer system to enable anyone with a workstation to have access to any of the published works of mankind - has stayed out of reach because of a presumed technical problem. Once a written work is digitized, it becomes so easy to make and distribute copyright infringing copies that publishers would go out of business. A technical solution to this problem based on trusted systems and digital property rights is now becoming available. The big issues for libraries-social and institutional policy challenges-are still ahead.

Michelle Baldonado, Chen-Chuan Chang, Luis Gravano, and Andreas Paepcke. Metadata for digital libraries: Architecture and design rationale. In Proceedings of the Second ACM International Conference on Digital Libraries (DL '97), pages 47-56, Philadelphia, Pennsylvania, July 1997.
BibTeX entry, Slides
R. Kaplan and P. Newman. Lexical resource reconcilation in the xerox linguistic environment. In Proceedings of the 1997 ACL Workshop on Environments for Grammar Development and Linguistic Engineering, Madrid, Spain, July 1997.
BibTeX entry, Postscript version

This paper motivates and describes those aspects of the Xerox Linguistic Environment that facilitate the construction of broad-coverage Lexical Functional grammars by incorporating morphological and lexical material from external resources....

Mehran Sahami, Salim Yusufali, and Michelle Q Wang Baldonado. Real-time full-text clustering of networked documents. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), page 845, Providence, Rhode Island, July 1997. Published abstract.
BibTeX entry
Mark J. Stefik. Shifting the Possible: How digital property rights challenge us to rethink digital publishing. Berkeley Technology Law Journal, 12(1):137-159, June 1997.
BibTeX entry, PDF version

In a widely circulated article about rethinking copyrights, John Perry Barlow has said that everything you know about intellectual property is wrong. Ideas want to be free. Barlow was correct in thinking that we are on our way to a new economy of ideas. He was wrong, however, in thinking that copyright and other forms of author and publisher control over works in digital form are outmoded. There has been a technological shift that changes what is possible in property rights and commerce for digital works. This article aims to demystify the technological shift and to show how it enables new ways of thinking about computers, information, and digital publishing.

Michelle Q Wang Baldonado. Searching, browsing, and metasearching with sensemaker. Web Techniques, 2(5):42-7, May 1997.
BibTeX entry, HTML version
Michelle Q Wang Baldonado and Terry Winograd. Sensemaker: An information-exploration interface supporting the contextual evolution of a user's interests. In Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI '97), pages 11-18, Atlanta, Georgia, April 1997.
BibTeX entry, HTML version
Arturo Crespo, Bay-Wei Chang, and Eric A. Bier. Highly responsive interaction for a large web application: The meteor shower architecture in the webwriter editor. In Proceedings of the 6th International World Wide Web Conference (WWW6), pages 607-618, Santa Clara, California, April 1997.
BibTeX entry
Mark J. Stefik. Letting Loose the Light: Igniting Commerce in Electronic Publication. Forum on Technology-Based Intellectual Property, pages 78-81, March 1997.
BibTeX entry, PDF version

The technological means for commerce in digital works are now at hand. New and unconventional when compared with today's uses of computers, these means will enable us to buy, sell, and lend digital works much as we now buy, sell, and lend printed books and other publications. This technological system will affect everything f rom digital books to digital television, from digital music to digital video games. It will radically change our concepts of digital libraries, digital bookstores, digital music stores, digital newspapers, and digital television stations. Here is a roadmap to this new land.

Mark J. Stefik. Trusted systems. Scientific American, 276(3):78-81, 1997.
BibTeX entry, Web version

Devices that enforce machine-readable rights to use the work of a musician or author may create secure ways to publish over the Internet.

P. Newman. Representing 2p clitic placement in lfg. In Proceedings of the LFG '96 Conference (LFG96), Grenoble, France, July 1996. Proceedings online at http://csli-publications.stanford.edu/LFG.
BibTeX entry, PDF version

Accounting for the placement of what have been called second position (2P) clitics is difficult because the placement is governed by prosodic considerations, which can introduce anomalies in otherwise configurational rule systems. In this paper we consider several possible approaches to this problem having in common the assumption that the initial grammar is constructed without considering final clitic placement, and then rules are automatically added or modified to account for the 2P clitic phenomenon.

Arturo Crespo and Eric A. Bier. Webwriter: A browser-based editor for constructing web applications. In Proceedings of the Fifth International World Wide Web Conference (WWW5), volume 28 of Computer Networks and ISDN Systems, pages 1291-1306, Paris La Defense, France, May 1996.
BibTeX entry
Mark J. Stefik. Internet Dreams: Archetypes, Myths, and Metaphors. The MIT Press, Cambridge, Massachusetts, 1996.
BibTeX entry, Order on-line

The information superhighway is a metaphor oft used to describe the internet, used so often that Stefik fears we're in danger of subjecting the evolution of the net to the limiting implications of this metaphor. Stefik, along with a host of prescient techno thinkers and doers, examine four richer, more powerful metaphors and their Jungian archetypes that together should expand anyone's thinking about the cyber world. And those metaphors are: digital library (The Keeper of Knowledge), electronic mail (Communicator), electronic marketplace (Trader), and digital world (Adventurer). The summoning of the archetypes in service of Stefik's argument is a compelling way to organize this book around the very real ways in which the net is being used.

Ken Pier, Eric A. Bier, Ken Fishkin, and Maureen Stone. Abstract for webedit: shared editing in a web browser. In Poster proceedings of the 4th International World Wide Web Conference (WWW4), pages 66-67, Boston, Massachusetts, December 1995.
BibTeX entry
Scott Minneman, Steve Harrison, Bill Janssen, Gordon Kurtenbach, Thomas P. Moran, Ian Smith, and Bill van Melle. A confederation of tools for capturing and accessing collaborative activity. In Proceedings of the ACM Multimedia'95 Conference, San Francisco, CA, November 1995.
BibTeX entry, HTML version

This paper presents a confederation of tools, called Coral, that combine to support the real-time capture of and subsequent access to informal collaborative activities. The tools provide the means to initiate digital multimedia recordings, a variety of methods to index those recordings, and ways to retrieve the indexed material in other settings. The current system emerged from a convergence of the WhereWereWe multimedia work, the Tivoli LiveBoard application, and the Inter-Language Unification distributed-object programming infrastructure. We are working with a specific user community and application domain, which has helped us shape a particular, demonstrably useful, configuration of tools and to get extensive real-world experience with them. This domain involves frequent discussion and decision-making meetings and later access of the captured records of those meetings to produce accurate documentation. Several aspects of Coral - the application tools, the architecture of the confederation, and the multimedia infrastructure - are described.

Mark J. Stefik. Introduction to Knowledge Systems. Morgan Kaufmann Publishers, San Francisco, California, 1995.
BibTeX entry, Order on-line

Focusing on fundamental scientific and engineering issues, this book communicates the principles of building and using knowledge systems from the conceptual standpoint as well as the practical. Previous treatments of knowledge systems have focused on applications within a particular field, or on symbol-level representations, such as the use of frame and rule representations. Introduction to Knowledge Systems presents fundamentals of symbol-level representations including representations for time, space, uncertainty, and vagueness. It also compares the knowledge-level organizations for three common knowledge-intensive tasks: classification, configuration, and diagnosis.

Eric A. Bier, Maureen C. Stone, Ken Fishkin, William Buxton, and Thomas Baudel. A taxonomy of see-through tools. In Proceedings of ACM Conference on Human Factors in Computing Systems (CHI94), pages 358-364, Boston, Massachusetts, April 1994.
BibTeX entry
Maureen C. Stone, Ken Fishkin, and Eric A. Bier. The movable filter as a user interface tool. In Proceedings of ACM Conference on Human Factors in Computing Systems (CHI94), pages 306-312, Boston, Massachusetts, April 1994.
BibTeX entry
Anna C. B. Garcia, H.G. Howard, and Mark J. Stefik. Improving design and documentation by using partially automated synthesis. AI EDAM, 8(4), 1994.
BibTeX entry, PDF version
William J. Clancey, Stephen W. Smoliar, and Mark J. Stefik. Contemplating Minds: A Forum for Artificial Intelligence. The MIT Press, Cambridge, Massachusetts, 1994.
BibTeX entry, Order on-line

The book review column in Artificial Intelligence has evolved from simple reviews to a forum where reviewers and authors debate in essays, even tutorial presentations, the latest, often competing, theories of human and artificial intelligence. Contemplating Minds brings together a selection of these reviews in a form suitable for the general scientific reader, seminar organizer, or student wanting a critical introduction that synthesizes and compares some of the most important and influential books and ideas to have emerged in AI over the past decade.

Eric A. Bier, Maureen C. Stone, Ken Pier, William Buxton, and Tony D. DeRose. Toolglass and magic lenses: The see-through interface. In Proceedings of SIGGRAPH '93, ACM Computer Graphics Annual Conference Series, pages 73-80, Anaheim, California, August 1993.
BibTeX entry
Daniel M. Russell, Mark J. Stefik, Peter Pirolli, and Stuart K. Card. The cost structure of sensemaking. In Proceedings of INTERCHI, Amsterdam, Netherlands, April 1993.
BibTeX entry, PDF version

Making sense of a body of data is a common activity in any kind of analysis. Sensemaking is the process of searching for a representation and encoding data in that representation to answer task-specific questions. Different operations during sensemaking require different cognitive and external resources. Representations are chosen and changed to reduce the cost of operations in an information processing task. The power of these representational shifts is generally under-appreciated as is the relation between sensemaking and information retrieval.

Mark J. Stefik, Jan Aikins, Robert Balzer, John Benoit, Lawrence Birnbaum, Frederick Hayes-Roth, and Earl Sacerdoti. Retrospective on The organization of expert systems: a tutorial. Artificial Intelligence, 59:221-224, 1993.
BibTeX entry

The area of expert system architecture has not advanced significantly in the last decade. Most commercial systems that were built correspond to architectures early within our tour. Most of the system building was involved in int3egration with conventional programming and databases. During the last decade, research has taken a swing toward analysis. General frameworks of understanding are being replaced by specialized studies. Today in universities, interest in building expert systems is shifting to engineering and science departments where the creation and study of particular computational models is seen as advancing its subject matter.

M. Cecelia Buchanan and Polle T. Zellweger. Automatic temporal layout mechanisms. In Computer Graphics (Multimedia '93 Proceedings), pages 341-350. ACM, 1993.
BibTeX entry
Eric A. Bier. Embeddedbuttons: supporting buttons in documents. ACM Transactions on Information Systems, 10(4):381-407, October 1992.
BibTeX entry
M. Cecelia Buchanan and Polle T. Zellweger. Specifying temporal behavior in hypermedia documents. In European Conference on Hypertext, pages 262-271, 1992.
BibTeX entry
Catherine C. Marshall, Frank G. Halasz, Russell A. Rogers, and William C. Janssen. Aquanet: a hypertext tool to hold your knowledge in place. In Proceedings of the third annual ACM conference on Hypertext, San Antonio, TX, December 1991.
BibTeX entry, PDF version

Hypertext systems have traditionally focussed on information management and presentation. In contrast, the Aquanet hypertext system described in this paper is designed to support knowledge structuring tasks. Aquanet is a browser-based tool that allows users to graphically represent information in order to explore its structure. In this paper, we discuss our motivations for developing Aquanet. We then describe the basic concepts underlying the tool and give an overview of the user interface. We close with some brief comments about our initial experiences with the tool in use, and some of the directions we see the Aquanet research moving in the future.

Eric A. Bier. Embeddedbuttons: documents as user interfaces. In Proceedings of the ACM SIGGRAPH Symposium on User Interface Software and Technology (UIST91), pages 45-53, South Carolina, November 1991.
BibTeX entry
Eric A. Bier and Steve Freeman. Mmm: a user interface architecture for shared editors on a single screen. In Proceedings of the ACM SIGGRAPH Symposium on User Interface Software and Technology (UIST91), pages 79-86, South Carolina, November 1991.
BibTeX entry
Eric A. Bier and Aaron Goodisman. Documents as user interfaces. In R. Furuta, editor, EP90, Proceedings of the International Conference on Electronic Publishing, Document Manipulation and Typography, The Cambridge Series on Electronic Publishing, pages 249-262, Gaithersburg, Maryland, September 1990. Cambridge University Press.
BibTeX entry
P. Newman. Towards convenient bi-directional grammar formalisms. In Proceedings of the xxx International Conference on Computational Linguistics (COLING90), pages 294-298, Helsinki, Finland, August 1990.
BibTeX entry, PDF version

This paper discusses the advantages for practical bidirectional grammars of combining a lexical focus with the GPSG-oriented principle of immediate-dominance/linear-precedence (ID/LP) rule partitioning. It also outlines an implementation approach following these guidelines. The approach is inspired by Slot Grammar, with additions including more explicit mappings between surface and internal representations, and preferential consitituent ordering rules.

P. Newman. Symmetric slot grammar: A bidirectional design for mt. In Proceedings of the Third International Conference on Theoretical and Methodological Issues in Machine Translation, pages 145-156, Austin, Texas, June 1990.
BibTeX entry, PDF version

Grammar formalisms combining a lexicalist orientation with an immediate-dominance / linear-precedence (ID/LP) partitioning of information have considerable potential for bi-directional use, fundamentally because the information is expressed in a modular way and thus can be applied differently in parsing and geration. This paper describes an in-process design for a bi-directional formalism of this type. The formalism is intended for use in a multi-lingual machine translation system, and is founded on the ideas of the 1989 unidirectional Slot Grammar of McCord.

Eric A. Bier. Snap-dragging in three dimensions. In Proceedings of the 1990 Symposium on Interactive 3D Graphics, pages 193-204, Snowbird, Utah, March 1990. ACM SIGGRAPH.
BibTeX entry
William C. Janssen. xRooms: A multiple virtual workspaces window manager for the X Window System. In Proceedings of the 1990 X Window System Technical Conference, Boston, MA, January 1990.
BibTeX entry, Slides

This talk describes an implementation of the Xerox Rooms interface as a window manager for the X Window System. The slides cover a brief introduction to the Rooms system, and look at issues specific to the X Window System implementation of such a system. [An associated video presentation is not available here.]

Mark J. Stefik and John Seely Brown. Toward Portable Ideas, volume 2, pages 327-343. Lawrence Erlbaum Associates, August 1989.
BibTeX entry, PDF version

The key to effective teamwork is in the interaction of properly externalized ideas. To promote responsiveness in next generation organizations we propose active and sharable workspaces for working together to develop information. These can be realized in seamless tools for computer-mediated conversation that extend from offices to coffee lounges to formal meeting rooms.

B.Chieu, P. Newman, and S. Smith. An approach to paraphrase in mt systems based on a study of chinese verbs. In Proceedings of the International Conference on Computer Processing for Chinese and Oriental Languages, 1989. Conference cancelled due to Tianamen Square.
BibTeX entry, PDF version

In contrast to translation between related languages, translation among different language families often involves radical transformation of lexical items and the encompassing syntactic structure. As a result, the types of mechanisms involved in this transformation become a central concern. In this paper we propose a generalized approach to lexically-triggered structural transformations based on semantic features of lexical items and relationships among lexical items, both encoded in the lexicon. The approach is motivated by a study of the requirements for translation from English to Chinese motion and resultative verbs.

Polle T. Zellweger. Scripted documents: A hypermedia path mechanism. In Proceedings of the Second ACM Conference on Hypertext, pages 1-14, 1989.
BibTeX entry
P. Newman. Combinatorial disambiguation. In Proceedings of the Second ACL Conference on Applied Natural Language Processing (ANLP88), pages 243-252, Austin, Texas, February 1988.
BibTeX entry, PDF version

The disambiguation of sentences is a combinatorial problem. This paper describes a method for treating it as such directly, by adapting standard combinatorial search optimizations. Traditional disambiguation heuristics are applied, but, instead of being embedded in individual decision procedures for specific types of ambiguities, they contribute to numerical weights that are considered by a single global optimizer...

Daniel G. Bobrow and Mark J. Stefik. Searching Beyond Reason: A response to McDermott's Critique of Pure Reason.. Computational Intelligence, 3(3):162-165, August 1987.
BibTeX entry, PDF version

We describe how McDermott's critique of the meta-theory defense of logic is somewhat misaimed, and also falls short of the real problems. Logic is expected to be sound, expressive, additive, computationally effective, and fun. We argue that logic is a good thing, but one mustn't expect too much from it. Better results may be obtained by combining logic with principled computational notions and technology, and logic for what it was designed, a language that shows how a line of reasoning leads soundly to a particular result, rather than as a basis for finding that line.

Mark J. Stefik, Daniel G. Bobrow, Greg Foster, Stan Lanning, and Deborah Tartar. WYSIWIS Revised: early experiences with multi-user interfaces. ACM Transactions on Office Information Systems, 5(2):147-167, April 1987.
BibTeX entry, PDF version

WYSIWIS (What You See Is What I See) is a foundational abstraction for multiuser interfaces that expresses many of the characteristics of a chalkboard in face-to-face meetings. In its strictest interpretation, it means that everyone can see the same written information and also see where anyone else is pointing. In our attempts to build software support for collaboration in meetings, we have discovered that WYSIWIS is crucial, yet too inflexible when strictly enforced. This paper is about the design issues and choices that arose in our first generation of meeting tools based on WYSIWIS. Several examples of multiuser interfaces that start from this abstraction are presented. These tools illustrate that there are inherent conflicts between the needs of a group and the needs of individuals, since user interfaces compete for the same display space and meeting time. To help minimize the effect of these conflicts, constraints were relaxed along four key dimensions of WYSIWIS: display space, time of display, subgroup population, and congruence of view. Meeting tools must be designed to support the changing needs of information sharing during process transitions, as subgroups are formed and dissolved, as individuals shift their focus of activity, and as the group shifts from multiple parallel activities to a single focused activity and back again.

Mark J. Stefik, Greg Foster, Daniel G. Bobrow, Kenneth Kahn, Stan Lanning, and Lucy Suchman. Beyond the Chalkboard: Computer support for collaboration and problem solving in meetings. Communications of the ACM, 30(1):32-47, January 1987.
BibTeX entry, PDF version

Although individual use of computers is fairly widespread, in meetings we tend to leave them behind. At Xerox PARC, an experimental meeting room called the Colab has been created to study computer support of collaborative problem solving in face-to-face meetings. The long-term goal is to understand how to build computer tools to make meeting more effective.

Greg Foster and Mark J. Stefik. Cognoter: Theory and practice of a colab-orative tool. In Proceedings of the Conference on Computer-Supported Cooperative Work, pages 7-15, Austin, Texas, December 1986.
BibTeX entry, PDF version
Mark J. Stefik, Daniel G. Bobrow, Greg Foster, and Deborah Tatar. Wysiwis revised: Early experiences with multi-user interfaces. In Proceedings of the Conference on Computer-Supported Cooperative Work, pages 276-290, Austin, Texas, December 1986.
BibTeX entry, PDF version

WYSIWIS (What You See Is What I See) is a foundational abstraction for multiuser interfaces that expresses many of the characteristics of a chalkboard in face-to-face meetings. In its strictest interpretation, it means that everyone can see the same written information and also see where anyone else is pointing. In our attempts to build software support for collaboration in meetings, we have discovered that WYSIWIS is crucial, yet too inflexible when strictly enforced. This paper is about the design issues and choices that arose in our first generation of meeting tools based on WYSIWIS. Several examples of multiuser interfaces that start from this abstraction are presented. These tools illustrate that there are inherent conflicts between the needs of a group and the needs of individuals, since user interfaces compete for the same display space and meeting time. To help minimize the effect of these conflicts, constraints were relaxed along four key dimensions of WYSIWIS: display space, time of display, subgroup population, and congruence of view. Meeting tools must be designed to support the changing needs of information sharing during process transitions, as subgroups are formed and dissolved, as individuals shift their focus of activity, and as the group shifts from multiple parallel activities to a single focused activity and back again.

Daniel G. Bobrow, Gregor Kiczales, Larry Masinter, Mark J. Stefik, and Frank Zdybel. CommonLoops: Merging Lisp and Object-Oriented Programming. In OOPSLA '86: Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 17-29, Portland, Oregon, September 1986.
BibTeX entry, PDF version

CommonLoops blends object-oriented programming smoothly and tightly with the procedure-oriented design of Lisp. Functions and methods are combined in a more general abstraction. Message passing is invoked via normal Lisp function call. Methods are viewed as partial descriptions of procedures. Lisp data types are integrated with object classes. With these integrations, it is easy to incrementally move a program between the procedure and object-oriented styles. One of the most important properties of CommonLoops is its extensive use of meta-objects. We discuss three kinds of meta-objects: objects for classes, objects for methods, and objects for discriminators. We argue that these meta-objects make practical both efficient implementation and experimentation with new ideas for object-oriented programming. CommonLoops' small kernel is powerful enough to implement the major object-oriented systems in use today.

Daniel G. Bobrow, Sanjay Mittal, and Mark J. Stefik. Expert systems: perils and promise. Communications of the ACM, 29(9):880-894, September 1986.
BibTeX entry, PDF version

Based on a review of some actual expert-system projects, guidelines are proposed for choosing appropriate applications and managing the development process.

Daniel G. Bobrow and Mark J. Stefik. Perspectives on Artificial Intelligence Programming. Science, 231(9):951-956, February 1986.
BibTeX entry, PDF version

Programs are judged not only by whether they faithfully carry out the intended processing but also by whether they are understandable and easily changed. Programming systems for artificial intelligence applications use specialized languages, environments, and knowledge-based tools to reduce the complexity of the programming task. Language styles based on procedures, objects, logic, rules, and constraints reflect different models for organizing programs and facilitate program evolution and understandability. To make programming easier, multiple styles can be integrated as sub languages in a programming environment. Programming environments provide tools that analyze programs and crate informative displays of their structure. Programs can be modified by direct interaction with these displays. These tools and languages are helping computer scientists to regain a sense of control over systems that have become increasingly complex.

Mark J. Stefik, Daniel G. Bobrow, and Kenneth Kahn. Integrating access-oriented programming into a multiparadigm environment. IEEE Software, 3(1):10-18, January 1986.
BibTeX entry, PDF version

The Loops knowledge programming system integrates function-oriented, object-oriented, rule-oriented and -something not found in most other systems-access-oriented programming. In access-oriented programming, fetching or storing data can cause procedures to be invoked. In terms of actions and side effects, this is dual to object-oriented programming. In object-oriented programming, when one object sends a message to another, the receiving object may change its data as a side effect. In access-oriented programming, when one object changes its data, a message may be sent as a side effect.

Mark J. Stefik. The Next Knowledge Medium. AI Magazine, 7(1):34-46, 1986.
BibTeX entry

The most widely understood goal of artificial intelligence is to understand and build autonomous, intelligent, thinking machines. A perhaps larger opportunity and complementary goal is to understand and build an interactive knowledge medium.

Mark J. Stefik and Daniel G. Bobrow. Object-oriented programming: themes and variations. AI Magazine, 6(4):40-62, 1986.
BibTeX entry, PDF version

Over the past few years object-oriented programming languages have become popular in the artificial intelligence community, often as add-ons to Lisp. This is an introduction to the concepts of object-oriented programming based on our experience of them in Loops, and secondarily a survey of some of the important variations and open issues that are being explored and debated among users of different dialects.

P. Newman. The data model of ide: A value network. In Proceedings of the 4th International Conference on the Entity-Relationship Approach, pages 246-255, Chicago, Illinois, October 1985.
BibTeX entry, PDF version

The purpose of this paper is to describe and analyze the data model used in IDE, an experimental integrated data processing environment. The data model is one of a class of models which might be termed value networks. Models in this class have considerable, as yet unexploited, potential for eliminating discontinuities between programming language forms and data base access forms...

Mark J. Stefik. Strategic Computing at DARPA: Overview and Assessment. Communications of the ACM, 28(7):690-704, July 1985.
BibTeX entry, PDF version

Strategic Computing, a 10-year initiative to build faster and more intelligent systems, is ambitious, flawed by over scheduling perhaps and problems of definition, but basically sound.

Daniel G. Bobrow and Mark J. Stefik. The LOOPS Manual, 1983.
BibTeX entry, PDF version

LOOPS adds data, object. and rule oriented programming to the procedure oriented programing of Interlisp. In object oriented programming, behavior is determined by responses of instances of classes to messages sent between these objects. with no direct access to the internal structure of an object. This approach makes it convenient to define program interfaces in terms of message protocols. Data oriented programming is a dual of object oriented programming, where behavior can occur as a side effect of direct access to (permanent) object state. This makes it easy to write programs which monitor the behavior of other programs. Rule oriented programming is an alternative to programming in LISP. Programs in this paradigm are organized around recursively composable sets of pattern-action rules for use in expert system design. Rules make it convenient for describing flexible responses to a wide range of events. LOOPS is integrated into interlisp, and thus provides access to the standard procedure oriented programming of Lisp, and use of the extensive environmental support of the Interlisp-D system. Our experience suggests that programs are easier to build in a language when there is an available paradigm that matches the structure of the problem. The paradigms described here offer distinct ways of partitioning the organization of a program, as well as distinct ways of viewing the significance of side effects. LOOPS provides all these paradigms within a single environment. This manual is intended as the primary documentation for users of LOOPS, It describes the concepts and the programming facilities, and gives examples and scenarios for using LOOPS.

Mark J. Stefik, Daniel G. Bobrow, Sanjay Mittal, and Lynn Conway. Knowledge Programming in Loops: Report on an Experimental Course. AI Magazine, 4(3):3-13, 1983.
BibTeX entry, PDF version

Early this year fifty people took an experimental course at Xerox PARC on knowledge programming in Loops. During the course, the extended and debugged small knowledge systems in a simulated economics domain called Truckin. Everyone learned how to use the Loops environment, formulated the knowledge for their own program, and represented it in Loops. At the end of the course a knowledge competition was run so that the strategies used in the different systems could be compared. The punchline to this story is that almost everyone learned enough about Loops to complete a small knowledge system in only three days. Although one must exercise caution in extrapolating from small experiments, the results suggest that there is substantial power in integrating multiple programming paradigms.

P. Newman. Towards an integrated development environment. IBM Systems Journal, 20(1):81-107, 1982.
BibTeX entry
Mark J. Stefik and Lynn Conway. Towards the principled engineering of knowledge. AI Magazine, 3(3):4-16, 1982.
BibTeX entry, PDF version

The acquisition of expert knowledge is fundamental to the cration of expert systems. The conventional approach to building expert systems assumes that the knowledge exists, and that it is feasible to find an expert who has the knowledge and can articulate it in collaboration with a knowledge engineer. This article considers the practice of knowledge engineering when these assumptions can not be strictly justified. It draws on our experiences in the design of VLSI design methods, and in the prototyping of an expert assistant for VLSI design. We suggest methods for expanding the practice of knowledge engineering when applied to fields that are fragmented and undergoing rapid evolution. We outline how the expanded practice can shape and accelerate the process of knowledge generation and refinement. Our examples also clarify some of the unarticulated present practice of knowledge engineering.

Mark J. Stefik, Jan Aikins, Robert Balzer, John Benoit, Lawrence Birnbaum, Frederick Hayes-Roth, and Earl Sacerdoti. The Organization of Expert Systems: A Tutorial. Artificial Intelligence, 18:135-173, 1982.
BibTeX entry, PDF version

This is a tutorial about the organization of expert problem-solving programs. We begin with a restricted class of problems that admits a very simple organization. To make this organization feasible it is required that the input data be static and reliable and that the solution space be small enough to search exhaustively. These assumptions are then relaxed, one at a time, in a case study of ten more sophisticated organizational prescriptions. The first cases give techniques for dealing with unreliable data and time-varying data. Other cases show techniques for creating and reasoning with abstract solutions spaces and using multiple lines of reasoning. The prescriptions are compared for their coverage and illustrated by examples from recent expert systems.

Thomas Blank, Mark J. Stefik, and William van Cleemput. A parallel bit map architecture for DA algorithms. In 18th Annual Design Automation Conference, pages 43-52, June 1981.
BibTeX entry

Bitmaps have been used in many Design Automation (DA) algorithms such as printed circuit board (PCB) layout and integrated circuit (IC) design rule checking (DRC). The attraction of bit maps is that they provide a direct representation of two-dimensional images. The difficulty with large scale use of bit maps (e.g., for DRC on VLSI) is that the large amounts of data can consume impractical amounts of computation on sequential machines. This paper describes a processing architecture that is speacifically designed to operate on bit maps. It has an inherently two-dimensional construction and has a very large parallel processing capability. Also included in this paper are descriptions of algorithms that exploit the architecture. Algorithms for routing, DRC, and bit vector manipulation are included.

Mark J. Stefik. Planning and meta-planning (MOLGEN part 2). Artificial Intelligence, 16(2):141-169, 1981.
BibTeX entry, PDF version

The selection of what to do next is often the hardest part of resource-limited problem solving. In planning problems, there are typically many goals to be achieved in some order. The goals interact with each other in ways which depend both on the order in which they are achieved and on the particular operators which are used to achieve them. A planning program needs to keep its options open because decisions about one part of a plan are likely to have consequences for another part. This paper describes an approach to planning which integrates and extends two strategies termed the least-commitment and the heuristic strategies. By integrating these, the approach makes sense of the need for guessing; it resorts to plausible reasoning to compensate for the limitations of its knowledge base. The decision-making knowledge is organized in a layered control structure which separates decisions about the planning problem from decisions about the planning process. The approach, termed meta-planning, exposes and organizes a variety of decisions, which are usually made implicitly and sub-optimally in planning programs with rigid control structures. This is part of a course of research which seeks to enhance the power of problem solvers by enabling them to reason about their own reasoning processes. Meta-planning has been implemented and exercised in a knowledge-based program (named MOLGEN) that plans gene cloning experiments in molecular genetics.

Mark J. Stefik. Planning with constraints (MOLGEN part 1). Artificial Intelligence, 16(2):111-140, 1981.
BibTeX entry, PDF version

Hierarchical planners distinguish between important considerations and details. A hierarchical planner creates descriptions of abstract states and divides its planning task into subproblems for refining the abstract states. The abstract states enable it to focus on important considerations, thereby avoiding the burden of trying to deal with everything at once. In most practical planning problems, however, the subproblems interact. Without the ability to handle these interactions, hierarchical planners can deal effectively only with idealized cases where subproblems are independent and can be solved separately. This paper presents an approach to hierarchical planning, termed constraint posting, that uses constraints to represent the interactions between subproblems. Constraints are dynamically formulated and propagated during hierarchical planning, and used to coordinate the solutions of nearly independent subproblems. This is illustrated with a computer program, called MOLGEN, that plans gene-cloning experiments in molecular genetics.

Mark J. Stefik, Daniel G Bobrow, Alan Bell, Harold Brown, Lynn Conway, and Christopher Tong. The partitioning of concerns in digital system design. In Proceedings of the Conference on Advanced Research in VLSI, pages 43-52, Massachusetts Institute of Technology, Cambridge, Massachusetts, January 1981.
BibTeX entry, PDF version

This paper proposes the use of explicit abstraction levels to organize decision making in digital design. These levels partition the concerns that a designer must consider at any time. They provide terms and composition rules for the composition of structural descriptions within a level. This allows multiple opportunities for mapping behavior into structure.

Mark J. Stefik. Planning with Constraints. PhD thesis, Computer Science Department, Stanford University, 1980.
BibTeX entry, PDF version
Mark J. Stefik. An examination of a frame-structured representation system. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 845-852, Tokyo, Japan, August 1979.
BibTeX entry, PDF version

The Unit Package is an interactive knowledge representation system with representations for individuals, classes, indefinite individuals, and abstractions. Links between the nodes are structured with explicit definitional roles, types of inheritance, defaults, and various data formats. This paper presents the general ideas of the Unit Package and compares it with other current knowledge representation languages. The Unit Package was created for a hierarchical planning application, and is now in use by several AI projects.

Mark J. Stefik. Inferring DNA structures from segmentation data. Artificial Intelligence, 11(1):84-114, 1978.
BibTeX entry, PDF version

The analysis of DNA structure from restriction enzyme segmentation data has been viewed by molecular geneticists as one of their simpler analysis problems. This paper treats segmentation problems as a case study in the selection between data-driven and model-driven hypothesis formation. The main purpose of this paper is to set forth some useful considerations for selecting a problem solving approach according to the characteristics of a domain. The case study illustrates why an exhaustive model-driven approach, which operates primarily by ruling out all the wrong answers, is a good approach for this domain. A program called GA1 solves segmentation problems using techniques similar to those used in the DENDRAL program.

R. Geoffrey Dromey, Mark J. Stefik, Thomas C. Rindfleisch, and Alan M. Duffield. Extraction of mass spectra free of background and neighboring component contributions from gas chromatography/mass spectrometry data. Analytical Chemistry, 48(9):1368-1375, 1976.
BibTeX entry, PDF version

An effective, minicomputer-based method is described for systematically extracting resolved mass spectra of mixture components from GC/MS data. Using tabular peak models derived directly from the raw data, the spectra have column bleed background removed and are corrected for interference from neighboring elutants and peak saturation. Individual components are detected in the data by means of a pair of histograms, which statistically characterize the positions of mass fragmentogram peak modes. These data-adaptive corrections avoid costly iterative numerical procedures and allow obtaining representative mass spectra f rom GC/MS data of complex mixtures on a routine basis. Using this approach, components that elute within less than two spectral scan times of each other can be detected and their mass spectra well resolved.