Perturbation analysis for the QR decomposition - Chang,X. C.; Paige,C. C.; Stewart, G.W. (SIAM Journal on Matrix Analysis and Applications, 1997)

Query previews for networked information systems: a case study with NASA environmental data - Doan,K.; Plaisant, Catherine; Shneiderman, Ben; Bruns,T. (SIGMOD Record, 1997)
Formulating queries on networked information systemsis laden with problems: data diversity, data complexity, network growth, varied user base, and slow network access. This paper proposes a new approach to a network query user interface which consists of two phases: query preview and query refinement. This new approach is based on dynamic queries and tight coupling, guiding users to rapidly and dynamically eliminate undesired items, reduce the data volume to a manageable size, and refine queries locally before submission over a network. A two-phase dynamic query system for NASA’s Earth Observing Systems--Data Information Systems (EOSDIS) is presented. The prototype was well received by the team of scientists who evaluated the interface.

Query previews in networked information systems: the case of EOSDIS - Plaisant, Catherine; Bruns,Tom; Shneiderman, Ben; Doan,Khoa (CHI '97 extended abstracts on Human factors in computing systems: looking to the future, 1997)
Dynamic queries have been shown to be an effective technique to browse information, and to find patterns and exceptions. Dynamic queries involve the interactive control by a user of visual query parameters that generate rapid (100 ms update), animated, and visual displays of database search results. The data of early implementations was stored in local memory to guarantee optimal speed. Problems arise when the data is very large and distributed over a network. To overcome the problems of slow networks and data volume we propose a two-phase approach to query formulation using query previews and query refinements [1]. Preview mechanisms have been used in the past [2] and we believe that their use will be a major component of successful networked information systems interfaces (e.g. [3]).
Keywords: direct manipulation; dynamic query; earth science; network information system; query preview; Visualization

Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds - Panconesi,Alessandro; Srinivasan, Aravind (SIAM Journal on Computing, 1997)
Certain types of routing, scheduling, and resource-allocation problems in a distributed setting can be modeled as edge-coloring problems. We present fast and simple randomized algorithms for edge coloring a graph in the synchronous distributed point-to-point model of computation. Our algorithms compute an edge coloring of a graph $G$ with $n$ nodes and maximum degree $Δ$ with at most $1.6 Δ + O(\log^{1+ δ} n)$ colors with high probability (arbitrarily close to 1) for any fixed $δ > 0$; they run in polylogarithmic time. The upper bound on the number of colors improves upon the $(2 Δ - 1)$-coloring achievable by a simple reduction to vertex coloring.To analyze the performance of our algorithms, we introduce new techniques for proving upper bounds on the tail probabilities of certain random variables. The Chernoff--Hoeffding bounds are fundamental tools that are used very frequently in estimating tail probabilities. However, they assume stochastic independence among certain random variables, which may not always hold. Our results extend the Chernoff--Hoeffding bounds to certain types of random variables which are not stochastically independent. We believe that these results are of independent interest and merit further study.

Sources of, and exploiting, inconsistency: preliminary report - Perlis, Don (JOURNAL OF APPLIED NONCLASSICAL LOGICS, 1997)

Specification-based Testing of Reactive Software: Tools and Experiments - Jagadeesan,Lalita Jategaonkar; Porter, Adam; Puchol,Carlos; Ramming,J. Christopher; Votta,Lawrence G. (Software Engineering, International Conference on, 1997)
Testing commercial software is expensive and time consuming. Automated testing methods promise to save a great deal of time and money throughout the software industry. One approach that is well-suited for the reactive systems found in telephone switching systems is specification-based testing.We have built a set of tools to automatically test softmare applications for violations of safety properties expressed in temporal logic. Our testing system automatically constructs finite state machine oracles corresponding to safety properties, builds test harnesses, and integrates them with the application. The test harness then generates inputs automatically to test the application.We describe a study examining the feasibility of this approach for testing industrial applications. To conduct this study we formally modeled an Automatic Protection Switching system (APS), which is an application common to many telephony systems. We then asked a number of computer science graduate students to develop several versions of the APS and use our tools to test them. We found that the tools are very effective, save significant amounts of human effort (at the expense of machine resources), and are easy to use. We also discuss improvements that are needed before we can use the tools with professional developers building commercial products.
Keywords: empirical studies; reactive systems; specification-based testing; temporal logic

Symbolic model checking of infinite state systems using Presburger arithmetic - Bultan,T.; Gerber,R.; Pugh, William (Computer Aided Verification, 1997)

Techniques for Automated Testing for Automated Testing of Document Analysis Algorithms - Sauvola,J.; Kauniskangas,H.; David Doermann; Pietikainen,M. (Proceedings of the First Brazilian Symposium on Document Image Analysis, 1997)

Toward motion picture grammars - Bolle,Ruud; Aloimonos, J.; Fermüller, Cornelia (Computer Vision — ACCV'98Computer Vision — ACCV'98, 1997)
We are interested in processing video data for the purpose of solving a variety of problems in video search, analysis, indexing, browsing and compression. Instead of concentrating on a particular problem, in this paper we present a framework for developing video applications. Our basic thesis is that video data can be represented at a higher level of abstraction as a string generated by a grammar, termed motion picture grammar. The rules of that grammar relate different spatiotemporal representations of the video content and, in particular, representations of action.

User Interface Reengineering: Low-Effort, High-Payoff Strategies - Plaisant, Catherine; Rose,A.; Shneiderman, Ben; Vanniamparampil,A. J (IEEE Software, 1997)
User interface technology has advanced rapidly in recent years. Incorporating new developments in existing systems could result in substantial improvements in usability, thereby improving performance and user satisfaction, while shortening training and reducing error rates. We describe low-effort, high-payoff strategies that focus attention on improvements to data display and entry, consistency, messages, documentation, system access and additional functionality. We report on experience from six projects, describing observations, recommendations and outcomes. We close with guidance for managers and designers who are responsible for user interface reengineering.

The vegetation canopy lidar mission - Dubayah, R.; Blair,J. B.; Bufton,J. L.; Clark,D. B.; JaJa, Joseph F.; Knox,R.; Luthcke,S. B.; Prince,S.; Weishampel,J. (Proceedings of Land Satellite Information in the Next Decade, II: Sources and Applications. Bethesda (MD): American Society of Photogrammetry and Remote Sensing, 1997)
The Vegetation Canopy Lidar (VCL) is the first selected mission of NASA’s new EarthSystem Science Pathfinder program. The principal goal of VCL is the characterization of the three-dimensional structure of the earth; in particular, canopy vertical and horizontal structure and land surface topography. Its primary science objectives are: landcover characterization for terrestrial ecosystem modeling, monitoring and prediction; landcover characterization for climate modeling and prediction; and, production of a global reference data set of topographic spot heights and transects. VCL will provide unique data sets for understanding important environ- mental issues including climatic change and variability, biotic erosion and sustainable landuse, and will dramatically improve our estimation of global biomass and carbon stocks, fractional forest cover, forest extent and condition. It will also provide canopy data critical for biodiversity, natural hazard, and climate studies. Scheduled for launch in early 2000, VCL is an active lidar remote sensing system consisting of a five-beam instrument with 25 m contiguous along track resolution. The five beams are in a circular configuration 8 km across and each beam traces a separate ground track spaced 2 km apart, eventually producing 2 km coverage between 65° N and S. VCL’s core measurement objectives are: (1) canopy top heights; (2) vertical distribution of intercepted surfaces (e.g. leaves and branches); and, (3) ground surface topographic elevations. These measurements are used to derive a variety of science data products including canopy heights, canopy vertical distribution, and ground elevations gridded monthly at 1° resolution and every 6 months at 2 km resolution, as well as a 2 km fractional forest cover product.

Visual Information Seeking in Digital Image Libraries: The Visible Human Explorer - North,C.; Shneiderman, Ben; Plaisant, Catherine (Information in Images, 1997)
This chapter presents the Visible Human Explorer user interface, developed at theHuman-Computer Interaction Lab of the University of Maryland at College Park, for remotely accessing the National Library of Medicine’s Visible Human digital image library. With the interface, users can visualize the library, browse contents, locate data of interest, and retrieve and zoom on desired image details. The interface presents a pair of tightly coupled views of library data: an overview of the overall search space, and a preview of high-resolution images available for retrieval. To explore, the user sweeps the views through the search space and receives smooth, rapid, visual feedback of contents. Desired details are automatically downloaded over the internet from the library. The interface software is completely functional (runs on Sun Workstations) and freely available for public use, at: http://www.nlm.nih.gov/. We also present several human-computer interaction design principles used to create the Visible Human Explorer interface, describe how these were applied to the design, and discuss issues in employing these techniques in user interfaces for other information collections. These principles are direct manipulation, visual information seeking, query previews, and multiple tightly coupled views. We illustrate these concepts with a plethora of pictures of user interface screens. Please also check the included CD-ROM for additional illustration media.

Automated inference in active logics - Miller,M.; Perlis, Don (JOURNAL OF APPLIED NONCLASSICAL LOGICS, 1996)

On the Complexity of Distributed Network Decomposition - Panconesi,Alessandro; Srinivasan, Aravind (Journal of Algorithms, 1996)
In this paper, we improve the bounds for computing a network decomposition distributively and deterministically. Our algorithm computes an (nϵ(n),nϵ(n))-decomposition innO(ϵ(n))time, where[formula]. As a corollary we obtain improved deterministic bounds for distributively computing several graph structures such as maximal independent sets and Δ-vertex colorings. We also show that the class of graphs G whose maximum degree isnO(δ(n))where δ(n)=1/log lognis complete for the task of computing a near-optimal decomposition, i.e., a (logn, logn)-decomposition, in polylog(n) time. This is a corollary of a more general characterization, which pinpoints the weak points of existing network decomposition algorithms. Completeness is to be intended in the following sense: if we have an algorithmAthat computes a near-optimal decomposition in polylog(n) time for graphs inG, then we can compute a near-optimal decomposition in polylog(n) time for all graphs.

The Development of a General Framework for Intelligent Document Image Retrieval - David Doermann; Sauvola,J.; Kauniskangas,H.; Shin,C.; Pietikainen,M.; Rosenfeld, A. (Proceedings in the International Workshop on Document Analysis Systems, 1996)

Differential expression of the expression site-associated gene I family in African trypanosomes - Morgan,R. W; El‐Sayed, Najib M.; Kepa,J. K; Pedram,M.; Donelson,J. E (Journal of Biological Chemistry, 1996)

Efficient distribution analysis via graph contraction - Sheffler,T.; Schreiber,R.; Pugh, William; Gilbert,J.; Chatterjee,S. (Languages and Compilers for Parallel Computing, 1996)

An empirical exploration of code evolution - Karr,A.; Porter, Adam; Votta,L. (International Workshop on Empirical Studies of Software Maintenance, 1996)

Evaluating workflow and process automation in wide-area software development - Perry,D.; Porter, Adam; Votta,L.; Wade,M. (Software Process Technology, 1996)

Hybrid network management (communication systems) - Baras,J. S; Ball,M.; Karne,R. K; Kelley,S.; Jang,K.D.; Plaisant, Catherine; Roussopoulos, Nick; Stathatos,K.; Vakhutinsky,A.; Valluri,J. (16th AIAA International Communications Satellite Systems Conference, 1996)
We describe our collaborative efforts towards the design and implementation of a next-generation integrated network management system for hybrid networks (INMS/HN). We describe the overall software architecture of the system at its current stage of development. This NMS is specifically designed to address issues relevant to complex heterogeneous networks consisting of seamlessly interoperable terrestrial and satellite networks. NMSs are a key element for interoperability in such networks. We describe the integration of configuration management and performance management. The next step in this integration is fault management. In particular, we describe the object model, issues concerning the graphical user interface, browsing tools, performance data graphical widget displays, and management information database organization issues.

Integrated network management of hybrid networks - Baras,John S; Ball,Mike; Karne,Ramesh K; Kelley,Steve; Jang,Kap D; Plaisant, Catherine; Roussopoulos, Nick; Stathatos,Kostas; Vakhutinsky,Andrew; Jaibharat,Valluri; Whitefield,David (AIP Conference Proceedings, 1996)
We describe our collaborative efforts towards the design and implementation of a next generation integrated network management system for hybrid networks (INMS/HN). We describe the overall software architecture of the system at its current stage of development. This network management system is specifically designed to address issues relevant for complex heterogeneous networks consisting of seamlessly interoperable terrestrial and satellite networks. Network management systems are a key element for interoperability in such networks. We describe the integration of configuration management and performance management. The next step in this integration is fault management. In particular we describe the object model, issues of the Graphical User Interface (GUI), browsing tools and performance data graphical widget displays, management information database (MIB) organization issues. Several components of the system are being commercialized by Hughes Network Systems. © 1996 American Institute of Physics.

LifeLines: visualizing personal histories - Plaisant, Catherine; Milash,Brett; Rose,Anne; Widoff,Seth; Shneiderman, Ben (Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, 1996)
Keywords: History; justice; medical record; overview; personal record; screen design; screen management; timeline; Visualization

Local tools: an alternative to tool palettes - Bederson, Benjamin B.; Hollan,J.D.; Druin, Allison; Stewart,J.; Rogers,D.; Proft,D. (Proceedings of the 9th annual ACM symposium on User interface software and technology, 1996)

Positional sequencing by hybridization - Hannenhalli, Sridhar; Feldman,William; Lewis,Herbert F.; Skiena,Steven S.; Pevzner,Pavel A. (Computer applications in the biosciences : CABIOS, 1996)
Sequencing by hybridization (SBH) is a promising alternative to the classical DNA sequencing approaches. However, the resolving power of SBH is rather low: with 64kb sequencing chips, unknown DNA fragments only as long as 200 bp can be reconstructed in a single SBH experiment. To improve the resolving power of SBH, positional SBH (PSBH) has recently been suggested; this allows (with additional experimental work) approximate positions of every l-tuple in a target DNA fragment to be measured. We study the positional Eulerian path problem motivated by PSBH. The input to the positional eulerian path problem is an Eulerian graph G( V, E) in which every edge has an associated range of integers and the problem is to find an Eulerian path el, …, e|E| in G such that the range of ei, contains i. We show that the positional Eulerian path problem is NP-complete even when the maximum out-degree (in-degree) of any vertex in the graph is 2. On a positive note we present polynomial algorithms to solve a special case of PSBH (bounded PSBH), where the range of the allowed positions for any edge is bounded by a constant (it corresponds to accurate experimental measurements of positions in PSBH). Moreover, if the positions of every l-tuple in an unknown DNA fragment of length n are measured with O(log n) error, then our algorithm runs in polynomial time. We also present an estimate of the resolving power of PSBH for a more realistic case when positions are measured with Θ(n) error.

Query previews in networked information systems - Donn,K.; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the Third Forum on Research and Technology Advances in Digital Libraries, 1996. ADL '96, 1996)
In a networked information system (such as the NASA Earth Observing System-Data Information System (EOS-DIS)), there are three major obstacles facing users in a querying process: network performance, data volume and data complexity. In order to overcome these obstacles, we propose a two phase approach to query formulation. The two phases are the Query Preview and the Query Refinement. In the Query Preview phase, users formulate an initial query by selecting rough attribute values. The estimated number of matching data sets is shown, graphically on preview bars which allows users to rapidly focus on a manageable number of relevant data sets. Query previews also prevent wasted steps by eliminating zero hit queries. When the estimated number of data sets is long enough, the initial query is submitted to the network which returns the metadata of the data sets for further refinement in the Query Refinement phase. The two phase approach to query formulation overcomes slow network performance, and reduces the data volume and data complexity, problems. This approach is especially appropriate for users who do not have extensive knowledge about the data and who prefer an exploratory method to discover data patterns and exceptions. Using this approach, we have developed dynamic query user interfaces to allow users to formulate their queries across a networked environment
Keywords: Computer networks; data complexity; data mining; data patterns; data volume; dynamic query user interfaces; Educational institutions; EOS-DIS; exploratory method; Information retrieval; Information services; Information systems; Intelligent networks; interactive systems; Laboratories; Manipulator dynamics; matching data sets; NASA Earth Observing System-Data Information System; Network performance; networked environment; networked information systems; query formulation; query preview; query refinement; querying process; rough attribute values; User interfaces; visual databases; zero hit queries

Query previews in networked information systems - Donn,K.; Plaisant, Catherine; Shneiderman, Ben (Research and Technology Advances in Digital Libraries, 1996. ADL '96., Proceedings of the Third Forum on, 1996)
In a networked information system (such as the NASA Earth Observing System-Data Information System (EOS-DIS)), there are three major obstacles facing users in a querying process: network performance, data volume and data complexity. In order to overcome these obstacles, we propose a two phase approach to query formulation. The two phases are the Query Preview and the Query Refinement. In the Query Preview phase, users formulate an initial query by selecting rough attribute values. The estimated number of matching data sets is shown, graphically on preview bars which allows users to rapidly focus on a manageable number of relevant data sets. Query previews also prevent wasted steps by eliminating zero hit queries. When the estimated number of data sets is long enough, the initial query is submitted to the network which returns the metadata of the data sets for further refinement in the Query Refinement phase. The two phase approach to query formulation overcomes slow network performance, and reduces the data volume and data complexity, problems. This approach is especially appropriate for users who do not have extensive knowledge about the data and who prefer an exploratory method to discover data patterns and exceptions. Using this approach, we have developed dynamic query user interfaces to allow users to formulate their queries across a networked environment
Keywords: attribute; complexity; data; data; Earth; environment; networked; EOS-DIS; NASA; formulation; querying; formulation; user; hit; information; interfaces; interfaces; exploratory; method; matching; networks; information; Observing; patterns; data; performance; networked; Preview; Query; process; rough; queries; computer; query; refinement; data; retrieval; information; services; interactive; sets; network; System-Data; System; Query; systems; query; user; values; zero; volume; dynamic

Ribosomal RNA: Small nucleolar RNAs make their mark - Peculis,Brenda A.; Mount, Stephen M. (Current Biology, 1996)
Small nucleolar RNAs direct the location of certain methylations in ribosomal RNA by direct base pairing; although evolutionarily conserved, the physiological significance of these modifications remains unclear.

On stratified sampling for high coverage estimations - Powell,David; Michel Cukier; Arlat,Jean (Dependable Computing — EDCC-2, 1996)
This paper addresses the problem of estimating the coverage of a fault tolerance mechanism through statistical processing of observations collected in faultinjection experiments. In an earlier paper, several techniques for sampling the fault/activity input space of a fault tolerance mechanism were presented. Various estimators based on simple sampling in the whole space and stratified sampling in a partitioned space were studied; confidence limits were derived based on a normal approximation. In this paper, the validity of this approximation is analyzed, especially for high coverage systems. The theory of confidence regions is then introduced to estimate the coverage without approximation when, for practical reasons, stratification is used. Three statistics are considered for defining confidence regions. It is shown that one of these statistics — a vectorial statistic — is often more conservative than the other two. However, only the vectorial statistic is computationally tractable. The results obtained are compared with those based on approximation by means of three hypothetical example systems.
Keywords: Computer science

To cut… or not to cut (applications of comparative physical maps in molecular evolution) - Hannenhalli, Sridhar; Pevzner,Pavel (Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, 1996)

Transitive closure of infinite graphs and its applications - Kelly,W.; Pugh, William; Rosser,E.; Shpeisman,T. (Languages and Compilers for Parallel Computing, 1996)

User controlled overviews of an image library: a case study of the visible human - North,Chris; Shneiderman, Ben; Plaisant, Catherine (Proceedings of the first ACM international conference on Digital libraries, 1996)
Keywords: Browsing; digital library; image database; information exploration; Information retrieval; Internet; medical image; remote access; user interface; Visualization; World-wide web

Using priorities to combine knowledge bases - Pradhan,S.; Minker, Jack (International Journal of Cooperative Information Systems, 1996)
Two or more companies, each with its own knowledge base, may merge. In that case one option is to merge the knowledge bases into one knowledge base. It can happen that some of the information contained in one or more knowledge bases may be in conflict with information in the other knowledge bases. There may be several such points of conflict and any information may be involved in several different such points of conflict. In that case, the integrator of the knowledge bases may prefer a certain claim to another in one conflict-point without necessarily preferring that claim in another conflict-point.Our work constructs a framework within which the consequences of a set of such preferences (expressed as priorities among sets of statements) can be computed. We give three types of semantics for priorities, two of which are shown to be equivalent to one another. The third type of semantics for priorities is shown to be more cautious than the other two. In terms of these semantics for priorities, we give a function for combining knowledge from different sources such that the combined knowledge is conflict-free and satisfies all the priorities.

Where is information visualization technology going? - Hascoët-Zizi,Mountaz; Ahlberg,Chris; Korfhage,Robert; Plaisant, Catherine; Chalmers,Matthew; Rao,Ramana (Proceedings of the 9th annual ACM symposium on User interface software and technology, 1996)

An applied ethnographic method for redesigning user interfaces - Rose,Anne; Shneiderman, Ben; Plaisant, Catherine (Proceedings of the 1st conference on Designing interactive systems: processes, practices, methods, & techniques, 1995)

Building a LCS-Based Lexicon in TAGs - Dorr, Bonnie J; Palmer,M. (Proceedings of the AAAI-95 Spring Symposium Series, Representation and Acquisition of Lexical Knowledge: Polysemy, Ambiguity, and Generativity, Stanford, CA, March, 1995)

Code generation for multiple mappings - Kelly,W.; Pugh, William; Rosser,E. (Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the, 1995)
There has been a great amount of recent work toward unifying iteration reordering transformations. Many of these approaches represent transformations as affine mappings from the original iteration space to a new iteration space. These approaches show a great deal of promise, but they all rely on the ability to generate code that iterates over the points in these new iteration spaces in the appropriate order. This problem has been fairly well-studied in the case where all statements use the same mapping. We have developed an algorithm for the less well-studied case where each statement uses a potentially different mapping. Unlike many other approaches, our algorithm can also generate code from mappings corresponding to loop blocking. We address the important trade-off between reducing control overhead and duplicating code
Keywords: code generation; Computer science; Concurrent computing; control overhead; Educational institutions; iteration reordering transformations; Law; Legal factors; loop blocking; multiple mappings; optimisation; optimising compilers; Optimizing compilers; PARALLEL PROCESSING; Performance analysis; program compilers

Combining databases with prioritized information - Pradhan,S.; Minker, Jack; V.S. Subrahmanian (Journal of Intelligent Information Systems, 1995)
To solve a problem one may need to combine the knowledge of several different experts. It can happen that some of the claims of one or more experts may be in conflict with the claims of other experts. There may be several such points of conflict and any claim may be involved in several different such points of conflict. In that case, the user of the knowledge of experts may prefer a certain claim to another in one conflict-point without necessarily preferring that statement in another conflict-point.Our work constructs a framework within which the consequences of a set of such preferences (expressed as priorities among sets of statements) can be computed. We give four types of semantics for priorities, three of which are shown to be equivalent to one another. The fourth type of semantics for priorities is shown to be more cautious than the other three. In terms of these semantics for priorities, we give a function for combining knowledge from different sources such that the combined knowledge is conflict-free and satisfies all the priorities.

Combining Datalog databases using priorities - Pradhan,Shekhar; Minker, Jack (University of Maryland at College Park, 1995)

Comparing detection methods for software requirements inspections: a replicated experiment - Porter, Adam; Votta,L. G.; Basili, Victor R. (IEEE Transactions on Software Engineering, 1995)
Software requirements specifications (SRS) are often validated manually. One such process is inspection, in which several reviewers independently analyze all or part of the specification and search for faults. These faults are then collected at a meeting of the reviewers and author(s). Usually, reviewers use Ad Hoc or Checklist methods to uncover faults. These methods force all reviewers to rely on nonsystematic techniques to search for a wide variety of faults. We hypothesize that a Scenario-based method, in which each reviewer uses different, systematic techniques to search for different, specific classes of faults, will have a significantly higher success rate. We evaluated this hypothesis using a 3×24 partial factorial, randomized experimental design. Forty eight graduate students in computer science participated in the experiment. They were assembled into sixteen, three-person teams. Each team inspected two SRS using some combination of Ad Hoc, Checklist or Scenario methods. For each inspection we performed four measurements: (1) individual fault detection rate, (2) team fault detection rate, (3) percentage of faults first identified at the collection meeting (meeting gain rate), and (4) percentage of faults first identified by an individual, but never reported at the collection meeting (meeting loss rate). The experimental results are that (1) the Scenario method had a higher fault detection rate than either Ad Hoc or Checklist methods, (2) Scenario reviewers were more effective at detecting the faults their scenarios are designed to uncover, and were no less effective at detecting other faults than both Ad Hoc or Checklist reviewers, (3) Checklist reviewers were no more effective than Ad Hoc reviewers, and (4) Collection meetings produced no net improvement in the fault detection rate-meeting gains were offset by meeting losses
Keywords: Assembly; Computer science; Design for experiments; detection methods; Fault detection; fault detection rate; Fault diagnosis; formal specification; formal verification; Gain measurement; individual fault detection rate; Inspection; Loss measurement; nonsystematic techniques; performance evaluation; Performance gain; replicated experiment; scenario-based method; Software development management; software requirements inspections; software requirements specifications; team fault detection rate

Consciousness and complexity: the cognitive quest - Perlis, Don (Annals of Mathematics and Artificial Intelligence, 1995)

Crystallization and preliminary X-ray investigation of the recombinant Trypanosoma brucei rhodesiense calmodulin - El‐Sayed, Najib M.; Patton,C. L; Harkins,P. C; Fox,R. O; Anderson,K. (Proteins: Structure, Function, and Bioinformatics, 1995)

Experimental software engineering: A report on the state of the art - Votta,L. G.; Porter, Adam; Perry,D. (INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, 1995)

Explicitly Biased Generalization - Gordon,D.; Perlis, Don (Goal-Driven Learning, 1995)

Finding Legal Reordering Transformations using Mappings - Pugh, William; Kelly, Wayne (Languages and compilers for parallel computing: 7th International Workshop, Ithaca, NY, USA, August 8-10, 1994: proceedings, 1995)
We present a unified framework for applying iteration reordering transformations. This framework is able to represent traditional transformations such as loop interchange, loop skewing and loop distribution as well as compositions of these transformations. Using a unified framework rather than a sequence of adhoc transformations makes it easier to analyze and predict the effects of these transformations. Our framework is based on the idea that all reordering transformations can be represented as a mapping from the original iteration space to a new iteration space. An optimizing compiler would use our framework by finding a mapping that both corresponds to a legal transformation and produces efficient code. We present the mapping selection problem as a search problem by decomposing it into a sequence of smaller choices. We then characterize the set of all legal mappings by defining a search tree.

Genetic enhancement of RNA-processing defects by a dominant mutation in B52, the Drosophila gene for an SR protein splicing factor. - Peng,X.; Mount, Stephen M. (Molecular and Cellular BiologyMol. Cell. Biol., 1995)
SR proteins are essential for pre-mRNA splicing in vitro, act early in the splicing pathway, and can influence alternative splice site choice. Here we describe the isolation of both dominant and loss-of-function alleles of B52, the gene for a Drosophila SR protein. The allele B52ED was identified as a dominant second-site enhancer of white-apricot (wa), a retrotransposon insertion in the second intron of the eye pigmentation gene white with a complex RNA-processing defect. B52ED also exaggerates the mutant phenotype of a distinct white allele carrying a 5' splice site mutation (wDR18), and alters the pattern of sex-specific splicing at doublesex under sensitized conditions, so that the male-specific splice is favored. In addition to being a dominant enhancer of these RNA-processing defects, B52ED is a recessive lethal allele that fails to complement other lethal alleles of B52. Comparison of B52ED with the B52+ allele from which it was derived revealed a single change in a conserved amino acid in the beta 4 strand of the first RNA-binding domain of B52, which suggests that altered RNA binding is responsible for the dominant phenotype. Reversion of the B52ED dominant allele with X rays led to the isolation of a B52 null allele. Together, these results indicate a critical role for the SR protein B52 in pre-mRNA splicing in vivo.

Genome Sequence Comparison and Scenarios for Gene Rearrangements: A Test Case - Hannenhalli, Sridhar; Chappey,Colombe; Koonin,Eugene V.; Pevzner,Pavel A. (Genomics, 1995)
As large portions of related genomes are being sequenced, methods for comparing complete or nearly complete genomes, as opposed to comparing individual genes, are becoming progressively more important. A major, widespread phenomenon in genome evolution is the rearrangement of genes and gene blocks. There is, however, no consistent method for genome sequence comparison combined with the reconstruction of the evolutionary history of highly rearranged genomes. We developed a schema for genome sequence comparison that includes three successive steps: (i) comparison of all proteins encoded in different genomes and generation of genomic similarity plots; (ii) construction of an alphabet of conserved genes and gene blocks; and (iii) generation of most parsimonious genome rearrangement scenarios. The approach is illustrated by a comparison of the herpesvirus genomes that constitute the largest set of relatively long, complete genome sequences available to date. Herpesviruses have from 70 to about 200 genes; comparison of the amino acid sequences encoded in these genes results in an alphabet of about 30 conserved genes comprising 7 conserved blocks that are rearranged in the genomes of different herpesviruses. Algorithms to analyze rearrangements of multiple genomes were developed and applied to the derivation of most parsimonious scenarios of herpesvirus evolution under different evolutionary models. The developed approaches to genome comparison will be applicable to the comparative analysis of bacterial and eukaryotic genomes as soon as their sequences become available.

Going beyond integer programming with the Omega test to eliminate false data dependences - Pugh, William; Wonnacott,D. (IEEE Transactions on Parallel and Distributed Systems, 1995)
Array data dependence analysis methods currently in use generate false dependences that can prevent useful program transformations. These false dependences arise because the questions asked are conservative approximations to the questions we really should be asking. Unfortunately, the questions we really should be asking go beyond integer programming and require decision procedures for a subclass of Presburger formulas. In this paper, we describe how to extend the Omega test so that it can answer these queries and allow us to eliminate these false data dependences. We have implemented the techniques described here and believe they are suitable for use in production compilers
Keywords: Algorithm design and analysis; Arithmetic; Computer science; Data analysis; false data dependences; integer programming; Linear programming; Omega test; Privatization; Production; production compilers; program compilers; Program processors; program testing; program transformations; Testing

Human-Computer Interaction Laboratory 1995 Video Reports - Plaisant, Catherine; Morrison,S.; Skokowski,C.; Reesch,J.; Shneiderman, Ben; Laboratory,University of Maryland at College Park. Human/Computer Interaction; Channel,F. (University of Maryland at College Park, Human/Computer Interaction Laboratory, 1995)

Image-browser taxonomy and guidelines for designers - Plaisant, Catherine; Carr,D.; Shneiderman, Ben (IEEE Software, 1995)
In many applications users must browse large images. Most designers merely use two one-dimensional scroll bars or ad hoc designs for two-dimensional scroll bars. However, the complexity of two-dimensional browsing suggests that more careful analysis, design, and evaluation might lead to significant improvements. Our exploration of existing 2D browsers has led us to identify many features and a wide variety of tasks performed with the browsers. We introduce an informal specification technique to describe 2D browsers and a task taxonomy, suggest design features and guidelines, and assess existing strategies. We focus on the tools to explore a selected image and so do not cover techniques to browse a series of images or to browse large-image databases
Keywords: analysis; Computer Graphics; design; designer guidelines; Equations; Europe; Evaluation; Formal specifications; Graphical user interfaces; Guidelines; IMAGE PROCESSING; image-browser taxonomy; informal specification technique; Laboratories; large image browsing; Layout; Road transportation; selected image exploration; SHAPE; Software design; task taxonomy; Taxonomy; tools; two-dimensional browsing; user interface management systems; visual databases

The local nature of Δ-coloring and its algorithmic applications - Panconesi,Alessandro; Srinivasan, Aravind (Combinatorica, 1995)
Given a connected graph G =( V, E ) with | V ⊧ n and maximum degree Δ such that G is neither a complete graph nor an odd cycle, Brooks' theorem states that G can be colored with Δ colors. We generalize this as follows: let G - v be Δ-colored; then, v can be colored by considering the vertices in an O (log Δ n ) radius around v and by recoloring an O (log Δ n ) length “augmenting path” inside it. Using this, we show that Δ-coloring G is reducible in O (log 3 n /logΔ) time to (Δ+1)-vertex coloring G in a distributed model of computation. This leads to fast distributed algorithms and a linear-processor NC algorithm for Δ-coloring.

Next generation network management technology - Baras,John S; Atallah,George C; Ball,Mike; Goli,Shravan; Karne,Ramesh K; Kelley,Steve; Kumar,Harsha; Plaisant, Catherine; Roussopoulos, Nick; Schneiderman,Ben; Srinivasarao,Mulugu; Stathatos,Kosta; et al. (AIP Conference Proceedings, 1995)
Today’s telecommunications networks are becoming increasingly large, complex, mission critical and heterogeneous in several dimensions. For example, the underlying physical transmission facilities of a given network may be ‘‘mixed media’’ (copper, fiber‐optic, radio, and satellite); the subnetworks may be acquired from different vendors due to economic, performance, or general availability reasons; the information being transmitted over the network may be ‘‘multimedia’’ (video, data, voice, and images) and, finally, varying performance criteria may be imposed e.g., data transfer may require high throughput while the others, whose concern is voice communications, may require low call blocking probability. For these reasons, future telecommunications networks are expected to be highly complex in their services and operations. Due to this growing complexity and the disparity among management systems for individual sub‐networks, efficient network management systems have become critical to the current and future success of telecommunications companies. This paper addresses a research and development effort which focuses on prototyping configuration management, since that is the central process of network management and all other network management functions must be built upon it. Our prototype incorporates ergonomically designed graphical user interfaces tailored to the network configuration management subsystem and to the proposed advanced object‐oriented database structure. The resulting design concept follows open standards such as Open Systems Interconnection (OSI) and incorporates object oriented programming methodology to associate data with functions, permit customization, and provide an open architecture environment. © 1995 American Institute of Physics

Organization overviews and role management: inspiration for future desktop environments - Plaisant, Catherine; Shneiderman, Ben (Proceedings of the Fourth Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises, 1995, 1995)
In our exploration of future work environments for the World Bank we proposed two concepts. First, organization overviews provide a consistent support to present the results of a variety of manual or semi-automated searches. Second this view can be adapted or expanded for each class of users to finally map the multiple personal roles an individual has in an organization. After command line interfaces, graphical user interfaces, and the current “docu-centric” designs, a natural direction is towards a role-centered approach where we believe the emphasis is on the management of those multiple roles. Large visual overviews of the organization can be rapidly manipulated and zoomed in on to reveal the multiple roles each individual plays. Each role involves coordination with groups of people and accomplishment of tasks within a schedule
Keywords: Asia; bank data processing; Databases; Environmental economics; Environmental management; future desktop environments; Graphical user interfaces; human resource management; management information systems; Management training; multiple personal roles; office automation; organization overviews; personnel; Project management; Prototypes; role management; role-centered approach; scheduling; semi-automated searches; User interfaces; Utility programs; World Bank

Papers on Context: Theory and Practice - Perlis, Don (Fundamenta Informaticae, 1995)

Parametric dispatching of hard real-time tasks - Gerber,R.; Pugh, William; Saksena,M. (IEEE Transactions on ComputersIEEE Trans. Comput., 1995)

QUERY PREVIEWS IN NETWORKED INFORMATION SYSTEMS - Doan,K.; Plaisant, Catherine; Shneiderman, Ben (Institute for Systems Research Technical Reports, 1995)
In a networked information system, there are three major obstacles facing users in a querying process: network performance, data volume and data complexity. In order to overcome these obstacles, we propose a two-phase approach to dynamic query formulation by volume preview. The two phases are the Query Preview and Query Refinement. In the Query Preview phase, users formulate an initial query by selecting desired attribute values. The volume of matching data sets is shown graphically on preview bars which aid users to rapidly eliminate undesired data sets, and focus on a manageable number of relevant data sets. Query previews also prevent wasted steps by eliminating zero-hit queries. When the estimated number of data sets is low enough, the initial query is submitted to the network, which returns the metadata of the data sets for further refinement in the Query Refinement phase. The two-phase approach to query formulation overcomes slow network performance, and reduces the data volume and data complexity problems. This approach is especially appropriate for users who prefer the exploratory method to discover data patterns and exceptions during the query formulation process. Using this approach, we have developed dynamic query user interfaces to allow users to formulate their queries across a networked environment.

The representation of document structure: A generic object-process approach - Dori,D.; David Doermann; Shin,C.; Haralick,R.; Phillips,I.; Buchman,M.; Ross,D. (University of Maryland, College Park, 1995)

SEL's software process improvement program - Basili, Victor R.; Zelkowitz, Marvin V; McGarry,F.; Page,J.; Waligora,S.; Pajerski,R. (Software, IEEE, 1995)
We select candidates for process change on the basis of quantified Software Engineering Laboratory (SEL) experiences and clearly defined goals for the software. After we select the changes, we provide training and formulate experiment plans. We then apply the new process to one or more production projects and take detailed measurements. We assess process success by comparing these measures with the continually evolving baseline. Based upon the results of the analysis, we adopt, discard, or revise the process
Keywords: baseline; detailed; engineering; engineering; evolving; improvement; Laboratory; continually; measurements; experiment; plans; production; process; program; software; projects; training; software; SEL; software

Survival of the fittest: the evolution of multimedia user interfaces - Preece,Jenny; Shneiderman, Ben (ACM Computing Surveys, 1995)

Thinking takes time: a modal active-logic for reasoning in time - Nirkhe,M.; Kraus,S.; Perlis, Don (Proc. of BISFAI-95, 1995)

Towards a computational theory of genome rearrangements - Hannenhalli, Sridhar; Pevzner,Pavel (Computer Science TodayComputer Science Today, 1995)
Analysis of genome rearrangements in molecular biology started in the late 1930's, when Dobzhansky and Sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions for the species of Drosophila. However, until recently there were no computer science results allowing a biologist to analyze genome rearrangements. The paper describes combinatorial problems motivated by genome rearrangements, surveys recently developed algorithms for genomic sequence comparison and presents applications of these algorithms to analyze rearrangements in herpes viruses, plant organelles, and mammalian chromosomes.

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals - Hannenhalli, Sridhar; Pevzner,Pavel (Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 1995)

Transforming men into mice (polynomial algorithm for genomic distance problem) - Hannenhalli, Sridhar; Pevzner,P.A. (Foundations of Computer Science, Annual IEEE Symposium on, 1995)
Many people believe that transformations of humans into mice happen only in fairy tales. However, despite some differences in appearance and habits, men and mice are genetically very similar. In the pioneering paper, J.H. Nadeau and B.A. Taylor (1984) estimated that surprisingly few genomic rearrangements (178/spl plusmn/39) happened since the divergence of human and mouse 80 million years ago. However, their analysis is nonconstructive and no rearrangement scenario for human-mouse evolution has been suggested yet. The problem is complicated by the fact that rearrangements in multi chromosomal genomes include inversions, translocations, fusions and fissions of chromosomes, a rather complex set of operations. As a result, at first glance, a polynomial algorithm for the genomic distance problem with all these operations looks almost as improbable as the transformation of a (real) man into a (real) mouse. We prove a duality theorem which expresses the genomic distance in terms of easily computable parameters reflecting different combinatorial properties of sets of strings. This theorem leads to a polynomial time algorithm for computing most parsimonious rearrangement scenarios. Based on this result and the latest comparative physical mapping data we have constructed a scenario of human-mouse evolution with 131 reversals/translocaitons/fusions/fissions. A combination of the genome rearrangement algorithm with the recently proposed experimental technique called ZOO FISH suggests a new constructive approach to the 100 year old problem of reconstructing mammalian evolution.
Keywords: biology computing; combinatorial properties; comparative physical mapping data; computable parameters; duality (mathematics); duality theorem; evolution (biological); Genetics; genome rearrangement algorithm; genomic distance problem; genomic rearrangements; human-mouse evolution; mammalian evolution; multi chromosomal genomes; parsimonious rearrangement scenarios; pattern matching; polynomial algorithm; polynomial time algorithm; set theory; sorting; string matching; strings; zoo fish

A unifying framework for iteration reordering transformations - Kelly,W.; Pugh, William (Algorithms and Architectures for Parallel Processing, 1995. ICAPP 95. IEEE First ICA/sup 3/PP., IEEE First International Conference on, 1995)

Calibrating, Counting, Grounding, Grouping - Elgot-drapkin,J.; Gordon,D.; Kraus,S.; Miller,M.; Nirkhe,M.; Perlis, Don (Association for the Advancement of Artificial Intelligence, 1994)

Concept-based lexical selection - Dorr, Bonnie J; Voss,C.; Peterson,E.; Kiker,M. (Proceedings of the AAAI-94 Fall Symposium on Knowledge Representation for Natural Language Processing in Implemented Systems, 1994)

Counting solutions to Presburger formulas: how and why - Pugh, William (ACM SIGPLAN Notices, 1994)

Dynamaps: dynamic queries on a health statistics atlas - Plaisant, Catherine; Jain,Vinit (Conference companion on Human factors in computing systems, 1994)

An Error-Theory of Consciousness - Perlis, Don (MARYLAND COMPUTER SCIENCE, 1994)

An experiment to assess different defect detection methods for software requirements inspections - Porter, Adam; Votta,L. G. (Proceedings of the 16th international conference on Software engineering, 1994)

The future of graphic user interfaces: Personal role managers - Shneiderman, Ben; Plaisant, Catherine (People and Computers, 1994)

High performance computing for land cover dynamics - Parulekar,R.; Davis, Larry S.; Chellapa, Rama; Saltz, J.; Sussman, Alan; Townshend,J. (Pattern Recognition, 1994. Vol. 3-Conference C: Signal Processing, Proceedings of the 12th IAPR International Conference on, 1994)

High-specificity neurological localization using a connectionist model - Tuhrim,S.; Reggia, James A.; Peng,Y. (Artificial Intelligence in Medicine, 1994)

Image Browsers: Taxonomy, Guidelines, and Informal Specifications - Plaisant, Catherine; Carr,David A; Shneiderman, Ben (Institute for Systems Research Technical Reports, 1994)
Image browsing is necessary in numerous applications. Designers have merely used two one-dimensional scroll bars or they have made ad hoc designs for a two-dimensional scroll bar. However, the complexity of two-dimensional browsing suggests that more careful analysis, design, and evaluation might lead to significant improvements. We present a task taxonomy for image browsing, suggest design features and guidelines, assess existing strategies, and introduce an informal specification
Keywords: Graphics; Systems Integration; use interface

Meta-languages, reflection principles and self-reference - Perlis, Don; V.S. Subrahmanian (Handbook of logic in artificial intelligence and logic programming, 1994)

Next Generation Network Management Technology - Atallah,George C; Ball,Michael O; Baras,John S; Goli,Shravan K; Karne,Ramesh K; Kelley,Stephen; Kumar,Harsha P.; Plaisant, Catherine; Roussopoulos, Nick; Shneiderman, Ben; Srinivasarao,Mulugu; Stathatos,Kostas; et al. (Institute for Systems Research Technical Reports, 1994)
Today's telecommunications networks are becoming increasingly large, complex, mission critical and heterogeneous in several dimensions. For example, the underlying physical transmission facilities of a given network may be ﲭixed media (copper, fiber- optic, radio, and satellite); the sub networks may be acquired from different vendors due to economic, performance, or general availability reasons; the information being transmitted over the network may be ﲭultimedia (video, data, voice, and images) and, finally, varying performance criteria may be imposed e.g. data transfer may require high throughput while the others, whose concern is voice communications, may require low call blocking probability. For these reasons, future telecommunications networks are expected to be highly complex in their services and operations. Due to this growing complexity and the disparity among management systems for individual sub networks, efficient network management systems have become critical to the current and future success of telecommunications companies. This paper addresses a research and development effort which focuses on prototyping configuration management, since that is the central process of network management and all other network management functions must be built upon it. Our prototype incorporates ergonomically designed graphical user interfaces tailored to the network configuration management subsystem and to the proposed advanced object-oriented database structure. The resulting design concept follows open standards such as Open Systems Interconnection (OSI) and incorporates object oriented programming methodology to associate data with functions, permit customization, and provide an open architecture environment. A revised version of this technical report has been published in The 12th Symposium on Space Nuclear Power and Propulsion/Commercialization, pp. 75-82, Albuquerque, NM, January 8-12, 1995.
Keywords: Constraints for Network Management.; Network Configuration Management; network management; Object Oriented Data Base Model for Network Management; Rules; Systems Integration; Visual Information Management for Network Configuration Management

On a parallel-algorithms method for string matching problems (overview) - Sahinalp,Suleyman; Vishkin, Uzi (Algorithms and ComplexityAlgorithms and Complexity, 1994)
Keywords: Computer; Science

Simplifying polynomial constraints over integers to make dependence analysis more precise - Maslov,V.; Pugh, William (Parallel Processing: CONPAR 94—VAPP VI, 1994)

Software Process Improvement in the NASA Software Engineering Laboratory. - McGarry,Frank; Pajerski,Rose; Page,Gerald; Waligora,Sharon; Basili, Victor R. (CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INSTITUTE, 1994)
The Software Engineering Laboratory (SEL) was established in 1976 for the purpose of studying and measuring software processes with the intent of identifying improvements that could be applied to the production of ground support software within the Flight Dynamics Division (FDD) at the National Aeronautics and Space Administration (NASA)/Goddard Space Flight Center (GSFC). The SEL has three member organizations: NASA/GSFC, the University of Maryland, and Computer Sciences Corporation (CSC). The concept of process improvement within the SEL focuses on the continual understanding of both process and product as well as goal-driven experimentation and analysis of process change within a production environment.
Keywords: *AWARDS; *SOFTWARE ENGINEERING; *SYSTEMS ANALYSIS; *WORK MEASUREMENT; ADMINISTRATION AND MANAGEMENT; COMPUTER PROGRAMMING AND SOFTWARE; COMPUTER PROGRAMS; COMPUTERS; data acquisition; ENVIRONMENTS; EXPERIMENTAL DATA; GROUND SUPPORT.; measurement; Organizations; PE63756E; Production; SOFTWARE PROCESS IMPROVEMENT; SPI(SOFTWARE PROCESS IMPROVEMENT); SPN-19950120014

Software reliability analysis of three successive generations of a Switching System - Kaâniche,M.; Kanoun,K.; Michel Cukier; Martini,M. (Dependable Computing — EDCC-1, 1994)
Most current approaches to software reliability evaluation are based on data collected on a single generation of products. However, many applications are developed through improvements of the existing software: to the families of products are added various generations as the need for new functionalities arises. Experimental studies dealing with the analysis of data collected on families of products are seldom reported. In this paper, we analyze the data (failure and correction reports) collected on the software of three successive generations of the Brazilian Switching System — TROPICO-R, during validation and operation. A comparative analysis of the three products is done and the main results are outlined. Emphasis is placed on the evolution of the software and the corresponding failures and corrected faults. The analysis addresses: i) the modifications introduced on system components, ii) the distribution of failures and corrected faults in the components and the functions fulfilled by the system, and iii) the evolution of the failure intensity functions.
Keywords: Computer science

Software Specification: A Comparison of Formal Methods - Gannon,John D.; Purtilo,James; Zelkowitz, Marvin V (Intellect Books, 1994)
Keywords: Computer software; Computer software/ Specifications; Computers / General; Computers / Programming / General; Formal methods (Computer science); software engineering; specifications

Static analysis of upper and lower bounds on dependences and parallelism - Pugh, William; Wonnacott,David (ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst., 1994)

Tool support for tailored software prototyping - Chen,C.; Porter, Adam; Purtilo,J. (Assessment of Quality Software Development Tools, 1994, Proceedings., Third Symposium on, 1994)

Usability Experiments for the Redesign of a Telepathology Workstation - Carr,D.; Plaisant, Catherine; Hasegawa,H. (Technical Report CS-TR-3270, University of Maryland, 1994)
Dynamic telepathology uses a remotely controlled microscope to allow a pathologist to viewsamples at a remote location. However, time delays introduced by remote operation have made use of a commercial dynamic telepathology system difficult and frustrating. This paper describes experiments to evaluate and redesign the user interface. We also make recommendations for further automation to support the pathology process and increase the usefulness of the system.

What Experts Deny, Novices Must Understand - Perlis, Don; Miller,M.; Perlis, Don (In 3rd International Workshop on Human and Machine Cognition, 1994)

The concurrency workbench: a semantics-based tool for the verification of concurrent systems - Cleaveland, Rance; Parrow,Joachim; Steffen,Bernhard (ACM Transactions on Programming Languages and Systems, 1993)

A connectionist approach to diagnostic problem solving using causal networks - Reggia, James A.; Peng,Y.; Tuhrim,S. (Information sciences, 1993)

A distributed algorithm for ear decomposition - Hannenhalli, Sridhar; Perumalla,K.; Chandrasekharan,N.; Sridhar,R. (, Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93, 1993)
A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition
Keywords: Asynchronous communication; asynchronous communication network; Automata; Communication networks; computational complexity; Computer networks; Computer science; decomposition graph; distributed algorithm; distributed algorithms; Distributed computing; Ear; ear decomposition; graph theory; message-optimal; network decomposition; sorting; Testing; time-optimal

Evaluating three museum installations of a hypertext system - Shneiderman, Ben; Brethauer,D.; Plaisant, Catherine; Potter,R. (Sparks of innovation in human-computer interaction, 1993)

Exploring remote images: a telepathology workstation - Plaisant, Catherine; Carr,David A; Hasegawa,Hiroaki (Proceedings of the INTERACT '93 and CHI '93 conference on Human factors in computing systems, 1993)

Facilitating Data Exploration: Dynamic Queries On A Health Statistics Map - Plaisant, Catherine; Laboratory,Human-computer Interaction (Proc. of the Government Statistics Section, Annual Meeting of the American Statistical Assoc. Conf. Proc, pg, 1993)
: Users with no specialized computer training are often discouraged by the complex syntax of query languages and the output of long tables of alphanumerical values. The Human-Computer Interaction Laboratory has recently developed the concept of dynamic queries which allows user control of animated visual displays of information. Experiments with our first applications have shown that dynamic queries can help reveal trends or global properties as well as assist users in answering specific questions. We present a new application developed with the National Center for Health Statistics and running on a simple PC. A thematic map of the United States is animated by adjusting sliders displayed on the side of the map. A time slider illustrates time trends. The other sliders control the filtering out of areas of the map according to parameters such as demographics. Detailed data about a particular area is obtained by clicking directly on its location on the map. We have received encouraging fe...

Fast search algorithms with applications to split and multi-stage vector quantization of speech lsp parameters - Arya,S.; Phamdo,N.; Farvardin,N.; Mount, Dave (Speech Coding for Telecommunications, 1993. Proceedings., IEEE Workshop on, 1993)

Guide to Opportunities in Volunteer Archaeology: case study on the use of a hypertext system in a museum exhibit - Plaisant, Catherine (Sparks of innovation in human-computer interactionSparks of innovation in human-computer interaction, 1993)

Improving the accuracy of touchscreens: an experimental evaluation of three strategies - Potter,R.L.; Weldon,L.J.; Shneiderman, Ben (Sparks of innovation in human-computer interaction, 1993)

Iterative Methods for Finding the Stationary Vector for Markov Chains - O'Leary, Dianne P. (Linear Algebra, Markov Chains, and Queuing ModelsLinear Algebra, Markov Chains, and Queuing Models, 1993)

Local conditions for phase transitions in neural networks with variable connection strengths - McFadden,F. E; Peng,Y.; Reggia, James A. (Neural networks, 1993)

Logic and Artificial Intelligence: A New Synthesis? - Perlis, Don (ANNALES-SOCIETATIS MATHEMATICAE POLONAE SERIES 4, 1993)

A partial evaluator for the Maruti hard real-time system - Nirkhe,V.; Pugh, William (Real-Time Systems, 1993)

Point probe decision trees for geometric concept classes - Arkin,E.; Goodrich,M.; Mitchell,J.; Mount, Dave; Piatko,C.; Skiena,S. (Algorithms and Data Structures, 1993)
A fundamental problem in model-based computer vision is that of identifying to which of a given set of concept classes of geometric models an observed model belongs. Considering a ldquoproberdquo to be an oracle that tells whether or not the observed model is present at a given point in an image, we study the problem of computing efficient strategies (ldquodecision treesrdquo) for probing an image, with the goal to minimize the number of probes necessary (in the worst case) to determine in which class the observed model belongs. We prove a hardness result and give strategies that obtain decision trees whose height is within a log factor of optimal.These results grew out of discussions that began in a series of workshops on Geometric Probing in Computer Vision, sponsored by the Center for Night Vision and Electro-Optics, Fort Belvoir, Virginia, and monitored by the U.S. Army Research Office. The views, opinions, and/or findings contained in this report are those of the authors and should not be construed as an official Department of the Army position, policy, or decision, unless so designated by other documentation.

Presentations and this and that: logic in action - Miller,M.; Perlis, Don (Proceedings of the 15th Annual Conference of the Cognitive Science Society, Boulder, Colorado, 1993)

Remote direct manipulation: A case study of a telemedicine workstation - Keil-Slawik,R.; Plaisant, Catherine; Shneiderman, Ben (Sparks of innovation in human-computer interactionSparks of innovation in human-computer interaction, 1993)

Scheduling home control devices: a case study of the transition from the research project to a product - Plaisant, Catherine; Shneiderman, Ben; Battagtia,J. (Sparks of innovation in human-computer interactionSparks of innovation in human-computer interaction, 1993)

Simple systems that exhibit template-directed replication - Reggia, James A.; Armentrout,S. L; Chou,H. H.; Peng,Y. (Science, 1993)

Situated reasoning within tight deadlines and realistic space and computation bounds - Nirkhe,M.; Kraus,S.; Perlis, Don (Proc. Common Sense, 1993)

Speech versus mouse commands for word processing: an empirical evaluation - Karl,Lewis R.; Pettey,Michael; Shneiderman, Ben (International Journal of Man-Machine Studies, 1993)
Despite advances in speech technology, human factors research since the late 1970s has provided only weak evidence that automatic speech recognition devices are superior to conventional input devices such as keyboards and mice. However, recent studies indicate that there may be advantages to providing an additional input channel based on speech input to supplement the more common input modes. Recently the authors conducted an experiment to demonstrate the advantages of using speech-activated commands over mouse-activated commands for word processing applications when, in both cases, the keyboard is used for text entry and the mouse for direct manipulation. Sixteen experimental subjects, all professionals and all but one novice users of speech input, performed four simple word processing tasks using both input groups in this counterbalanced experiment. Performance times for all tasks were significantly faster when using speech to activate commands as opposed to using the mouse. On average, the reduction in task time due to using speech was 18·7%. The error rates due to subject mistakes were roughly the same for both input groups, and recognition errors, averaged over all the tasks, occurred for 6·3% of the speech-activated commands. Subjects made significantly more memorization errors when using speech as compared with the mouse for command activation. Overall, the subjects reacted positively to using speech input and preferred it over the mouse for command activation; however, they also voiced concerns about recognition accuracy, the interference of background noise, inadequate feedback and slow response time. The authors believe that the results of the experiment provide evidence for the utility of speech input for command activation in application programs.

Using measurement-driven modeling to provide empirical feedback to software developers - Porter, Adam (Journal of Systems and Software, 1993)
Several authors have explored the application of classification methods to software development. These studies have concentrated on identifying modules that are difficult to develop or that have high fault density. While this information is important, it provides little help in determining appropriate corrective action. This article extends previous work by applying one classification method, classification tree analysis (CTA), to more a fine-grained problem routinely encountered by developers. In this article, we use CTA to identify software modules that have specific types of faults (e.g., logic, interface, etc.) We evaluate this approach using data collected from six actual software projects. Overall, CTA was able to correctly differentiate faulty modules from fault-free modules in 72% of cases. Furthermore, 82% of the faulty modules were correctly identified. We also show that CTA outperformed two simpler classification strategies.

Vacuum-logic - Elgot-drapkin,J.; Kraus,S.; Miller,M.; Nirkhe,M.; Perlis, Don (Proceedings of AAAI 1993 Fall Symposium Series: Instantiating Real-World Agents, 1993)

A connectionist approach to vertex covering problems - Peng,Y.; Reggia, James A.; Li,T. (Int’l J. Neural Systems, 1992)

Definitions of dependence distance - Pugh, William (ACM Letters on Programming Languages and SystemsACM Lett. Program. Lang. Syst., 1992)

Delaunay triangulation and computational fluid dynamics meshes - Posenau,Mary-Anne K; Mount, Dave (Proceedings of the 4th Canadian Conference on Computational Geometry, 1992)
In aerospace computational fluid dynamics (CFD) calculations, the Delaunay triangulation of suitable quadrilateral meshes can lead to unsuitable triangulated meshes. Here, we present case studies which illustrate the limitations of using structured grid generation methods which produce points in a curvilinear coordinate system for subsequent triangulations for CFD applications. We discuss conditions under which meshes of quadrilateral elements may not produce a Delaunay triangulation suitable for CFD calculations, particularly with regard to high aspect ratio, skewed quadrilateral elements.

The effects of time delays on a telepathology user interface. - Carr,D.; Hasegawa,H.; Lemmon,D.; Plaisant, Catherine (Proceedings of the Annual Symposium on Computer Application in Medical CareProc Annu Symp Comput Appl Med Care, 1992)
Telepathology enables a pathologist to examine physically distant tissue samples by microscope operation over a communication link. Communication links can impose time delays which cause difficulties in controlling the remote device. Such difficulties were found in a microscope teleoperation system. Since the user interface is critical to pathologist's acceptance of telepathology, we redesigned the user interface for this system, built two different versions (a keypad whose movement commands operated by specifying a start command followed by a stop command and a trackball interface whose movement commands were incremental and directly proportional to the rotation of the trackball). We then conducted a pilot study to determine the effect of time delays on the new user interfaces. In our experiment, the keypad was the faster interface when the time delay is short. There was no evidence to favor either the keypad or trackball when the time delay was longer. Inexperienced participants benefitted by allowing them to move long distances over the microscope slide by dragging the field-of-view indicator on the touchscreen control panel. The experiment suggests that changes could be made to the trackball interface which would improve its performance.

Eliminating false data dependences using the Omega test - Pugh, William; Wonnacott,D. (Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, 1992)

An environment projection approach to radiosity for meshconnected computers - Varshney, Amitabh; Prins,J. F (Third Eurographics Workshop on Rendering, 1992)

Fast randomized algorithms for distributed edge coloring - Panconesi,Alessandro; Srinivasan, Aravind (Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, 1992)

An improved classification tree analysis of high cost modules based upon an axiomatic definition of complexity - Tian,Jianhui; Porter, Adam; Zelkowitz, Marvin V (Software Reliability Engineering, 1992. Proceedings., Third International Symposium on, 1992)
Identification of high cost modules has been viewed as one mechanism to improve overall system reliability, since such modules tend to produce more than their fair share of problems. A decision tree model has previously been used to identify such modules. In this paper, a previously developed axiomatic model of program complexity is merged with the previously developed decision tree process for an improvement in the ability to identify such modules. This improvement has been tested using data from the NASA Software Engineering Laboratory
Keywords: (mathematics); analysis; axiomatic; classification; classification; complexity; computational; cost; decision; definition; high; metrics; model; modules; overall; program; reliability; software; subroutines; system; tree; TREES

Improved distributed algorithms for coloring and network decomposition problems - Panconesi,Alessandro; Srinivasan, Aravind (Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, 1992)

A new era for high precision touchscreens - Sears,A.; Plaisant, Catherine; Shneiderman, Ben (Advances in human-computer interaction, 1992)
While many input devices allow interfaces to be customized, increased directness distinguishes touchscreens. Touchscreens are easy to learn to use, fast, and result in low error rates when interfaces are designed carefully. Many actions which are diffi cult with a mouse, joystick, or keyboard are simple when using a touchscreen. Making rapid selections at widely separated locations on the screen, signing your name, dragging the hands of a clock in a circular motion are all simple when using a touchscre en, but may be awkward using other devices. This paper presents recent empirical research which can provide a basis for theories of touchscreen usage. We believe recent improvements warrant increased use of touchscreens.

A new era for touchscreen applications: High precision, dragging icons, and refined feedback - Sears,A.; Plaisant, Catherine; Shneiderman, Ben (Advances in Human-Computer Interaction, 1992)

The Omega test: a fast and practical integer programming algorithm for dependence analysis - Pugh, William (Communications of the ACM, 1992)

PARTI primitives for unstructured and block structured problems - Sussman, Alan; Saltz, J.; Das,R.; Gupta,S.; Mavriplis,D.; Ponnusamy,R.; Crowley,K. (Computing Systems in Engineering, 1992)
This paper describes a set of primitives (PARTI) developed to efficiently execute unstructured and block structured problems on distributed memory parallel machines. We present experimental data from a three-dimensional unstructured Euler solver run on the Intel Touchstone Delta to demonstrate the usefulness of our methods.

Partial evaluation of high-level imperative programming languages with applications in hard real-time systems - Nirkhe,V.; Pugh, William (Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1992)

Remote manipulation interfaces the case of a telepathology workstation - Plaisant, Catherine; Carr,David A (Posters and short talks of the 1992 SIGCHI conference on Human factors in computing systems, 1992)
Telemedicine is the practice of medicine over communication links. The physician being consulted and the patient are in two different locations. A first telepathology system has been developed by Corabi Telemetrics. It allows a pathologist to render a diagnosis by examining tissue samples or body fluids under a remotely located microscope.

Scheduling home control devices: design issues and usability evaluation of four touchscreen interfaces - Plaisant, Catherine; Shneiderman, Ben (International Journal of Man-Machine Studies, 1992)
This article describes four different user interfaces supporting scheduling two-state (ON/OFF) devices over time periods ranging from minutes to days. The touchscreen-based user interfaces including a digital 12-h clock, 24-h linear and 24-h dial prototypes are described and compared on a feature by feature basis. A formative usability test with 14 subjects, feedback from more than 30 reviewers, and the flexibility to add functions favour the 24-h linear version.

Simple systems exhibiting self-directed replication: annex of transition functions and software documentation - Reggia, James A.; Chou,Hui-Hsien; Armentrout,Steven L.; Peng,Yun (University of Maryland at College Park, 1992)

Touchscreen interfaces for alphanumeric data entry - Plaisant, Catherine; Sears,A. (Human Factors and Ergonomics Society Annual Meeting Proceedings, 1992)

Touchscreen toggle design - Plaisant, Catherine; Wallace,Daniel (Proceedings of the SIGCHI conference on Human factors in computing systems, 1992)

A two-level knowledge representation for machine translation: Lexical semantics and tense/aspect - Dorr, Bonnie J (Lexical Semantics and Knowledge RepresentationLexical Semantics and Knowledge Representation, 1992)
This paper proposes a two-level model that integrates contemporary theories of tense and aspect with lexical semantics. The model is intended to be extensible to realms outside of the temporal domain (e.g., the spatial domain). The integration of tense and aspect with lexical-semantics is especially critical in machine translation because of the lexical selection process during generation: there is often a number of lexical connective and tense/aspect possibilities that may be produced from a lexical semantic representation, which, as defined in the model presented here, is largely underspecified. Temporal/aspectual information from the source-language sentence constrains the choice of target-language terms. In turn, the target-language terms limit the possibilities for generation of tense and aspect. Thus, there is a two-way communication channel between the two processes.

When an Intermediate View Matters a 2D-browser Experiment - Plaisant, Catherine; Carr,David A; Hasegawa,Hiroaki (Institute for Systems Research Technical Reports, 1992)
The browsing of two dimensional images can be found in a large number of application. When the image to be viewed is much larger than the screen available, a two dimensional browser has to be provided to allow users to access all parts of the image. We show the diversity of tasks and systems available and the need for 2D browser design guidelines. In the context of a microscope image browser, we investigate one common technique consisting of a global view of the whole image, coupled to a detailed, magnified view of part of the image. In particular we look at the benefits of providing an intermediate view when the detail- to-overview ratio over 20:1. Our experience is also a good example of a real world application for which added features and added hardware need to be justified.
Keywords: Human computer interaction; Supervisory control; Systems Integration

Deadline-coupled real-time planning - Kraus,S.; Nirkhe,M.; Perlis, Don (Innovative approaches to planning, scheduling and control: proceedings of a Workshop [on Innovative Approaches to Planning, Scheduling, and Control], held at San Diego, California, November 5-8, 1991, 1991)

Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs - Srinivasan, Aravind; Pandu Rangan,C. (Theoretical Computer Science, 1991)
Given a graph G=(V, E) with real weights assigned to its vertices, a clique of G that also dominates its vertex set V, is called a dominating clique (DC) of G. Given a permutation graph G with all its vertices having nonnegative weights, and its permutation representation, the problem addressed in this paper is that of finding any minimum weight DC of G. We improve the existing O(|V|2) algorithm for this problem to O(|V|log|V|). The space complexity of our algorithm is O(|V|). We also present a |V| processor, O(log|V|) time, O(|V|log|V|) space parallel EREW PRAM algorithm for this problem.

Fully deadline-coupled planning: One step at a time - Nirkhe,M.; Kraus,S.; Perlis, Don (Methodologies for Intelligent Systems, 1991)

Memory, reason and time: the Step-Logic approach - Elgot-drapkin,J.; Miller,M.; Perlis, Don (Philosophy and AI: Essays at the Interface, 1991)

Metric-driven analysis and feedback systems for enabling empirically guided software development - Selby,R. W; Porter, Adam; Schmidt,D. C; Berney,J. (Proceedings of the 13th international conference on Software engineering, 1991)

Nonmonotonicity and the scope of reasoning - Etherington,D. W; Kraus,S.; Perlis, Don (Artificial Intelligence, 1991)

An overview of Hyperties, its user interface and data model - Plaisant, Catherine (Hypermedia/Hypertext And Object-Oriented Databases. Chapman & Hall, 1991)

Polyadenylylation in copia requires unusually distant upstream sequences - Kurkulos,M.; Weinberg,J. M.; Pepling,M. E.; Mount, Stephen M. (Proceedings of the National Academy of SciencesPNAS, 1991)
Retroviruses and related genetic elements generate terminally redundant RNA products by differential polyadenylylation within a long terminal repeat. Expression of the white-apricot (wa) allele of Drosophila melanogaster, which carries an insertion of the 5.1-kilobase retrovirus-like transposable element copia in a small intron, is influenced by signals within copia. By using this indicator, we have isolated a 518-base-pair deletion, 312 base pairs upstream of the copia polyadenylylation site, that is phenotypically like much larger deletions and eliminates RNA species polyadenylylated in copia. This requirement of distant upstream sequences for copia polyadenylylation has implications for the expression of many genetic elements bearing long terminal repeats.

Putting One's Foot in One's Head–Part I: Why - Perlis, Don (Noûs, 1991)

Reasoning about ignorance: A note on the Bush-Gorbachev problem - Kraus,S.; Perlis, Don; Horty,J. F (Fundam. Inform., 1991)

Recent applications of competitive activation mechanisms - Reggia, James A.; Peng,Y.; Bourret,P. (Neural Networks: Advances and Applications, 1991)

Scheduling on-off home control devices - Plaisant, Catherine; Shneiderman, Ben (Proceedings of the SIGCHI conference on Human factors in computing systems: Reaching through technology, 1991)

Stop the world—I want to think - Perlis, Don; Elgot-Drapkin,J. J; Miller,M. (International Journal of Intelligent Systems, 1991)

Typicality constants and range defaults: Some pros and cons of a cognitive model of default reasoning - Miller,M.; Perlis, Don (Methodologies for Intelligent Systems, 1991)

Uniform techniques for loop optimization - Pugh, William (Proceedings of the 5th international conference on Supercomputing, 1991)

Characterization of enhancer-of-white-apricot in Drosophila melanogaster. - Peng,X. B.; Mount, Stephen M. (GeneticsGenetics, 1990)
The white-apricot (w(a)) allele differs from the wild-type white gene by the presence of the retrovirus-like transposable element copia within the transcription unit. Most RNAs derived from w(a) have 3' termini within this insertion, and only small amounts of structurally normal RNA are produced. The activity of w(a) is reduced in trans by a semidominant mutation in the gene Enhancer-of-white-apricot (E(w(a)). Flies that are w(a) and heterozygous for the enhancer have eyes which are much lighter than the orange-yellow of w(a) alone while E(w(a)) homozygotes have white eyes. This semidominant effect on pigmentation is correlated with a corresponding decrease in white RNA having wild type structure, and flies homozygous for E(w(a)) have increased levels of aberrant RNAs. Three revertant alleles of E(w(a)) generated by reversion of the dominant enhancer phenotype with gamma radiation are noncomplementing recessive lethals, with death occurring during the larval stage. The effects on w(a) eye pigmentation of varying doses of the original E(w(a)) allele, the wild type allele, and the revertant alleles suggest that the original E(w(a)) allele produces a product that interferes with the activity of the wild type gene and that the revertants are null alleles. We propose that the E(w(a)) gene product influences the activity of the downstream copia long terminal repeat in 3' end formation.

The concurrency workbench - Cleaveland, Rance; Parrow,J.; Steffen,B. (Automatic Verification Methods for Finite State Systems, 1990)

Empirically guided software development using metric-based classification trees - Porter, Adam; Selby,R. W (IEEE Software, 1990)
The identification of high-risk components early in the life cycle is addressed. A solution that casts this as a classification problem is examined. The proposed approach derives models of problematic components, based on their measurable attributes and those of their development processes. The models provide a basis for forecasting which components are likely to share the same high-risk properties, such as being error-prone or having a high development cost. Developers can use these classification techniques to localize the troublesome 20% of the system. The method for generating the models, called automatic generation of metric-based classification trees, uses metrics from previous releases or projects to identify components that are historically high-risk.
Keywords: Application software; Area measurement; automatic generation; classification problem; Classification tree analysis; Costs; empirically guided software development; Error correction; life cycle; measurable attributes; metric-based classification trees; Predictive models; Programming; software engineering; Software measurement; software metrics; Software systems

Evaluating techniques for generating metric-based classification trees - Porter, Adam; Selby,Richard W. (Journal of Systems and Software, 1990)
Metric-based classification trees provide an approach for identifying user-specified classes of high-risk software components throughout the software lifecycle. Based on measurable attributes of software components and processors, this empirically guided approach derives models of problematic software components. These models, which are represented as classification trees, are used on future systems to identify components likely to share the same high-risk properties. Example high-risk component properties include being fault-prone, change-prone, or effort-prone, or containing certain types of faults. Identifying these components allows developers to focus the application of specialized techniques and tools for analyzing, testing, and constructing software. A validation study using metric data from 16 NASA systems showed that the trees had an average classification accuracy of 79.3% for fault-prone and effort-prone components in that environment.One fundamental feature of the classification tree generation algorithm is the method used for partitioning the metric data values into mutually exclusive and exhaustive ranges. This study compares the accuracy and the complexity of trees resulting from five techniques for partitioning metric data values. The techniques are quartiles, octiles, and three methods based on least weight subsequence (LWS-[chi]) analysis, where [chi] is the upper bound on the number of partitions. The LWS-3 and LWS-5 partition techniques resulted in trees with higher accuracy (in terms of completeness and consistency) than did quartiles and octiles. LWS-3 and LWS-5 trees were not statistically different in terms of accuracy, but LWS-3 trees had lower complexity than all other methods in terms of the number of unique metrics required. The trees from the three LWS methods (LWS-3, LWS-5, and LWS-8) had lower complexity than did the trees from quartiles and octiles. In general, the results indicate that distribution-sensitive partition techniques that use only relatively few partitions, such as the least weight subsequence techniques LWS-3 and LWS-5, can increase accuracy and decrease complexity in classification trees. Classification analysis techniques, along with other empirically based analysis techniques for large-scale software, will be supported in the Amadeus measurement and empirical analysis system.

Inductive inference model for diagnostic problem-solving - Peng,Y.; Reggia, James A. (Springer-Verlag, 1990)

Intentionality and defaults - Perlis, Don (International J. of Expert Systems, 1990)

Limited scope and circumscriptive reasoning - Etherington,D. W; Kraus,S.; Perlis, Don (International Journal of Expert Systems, 1990)

Probabilistic analysis of set operations with constant-time set equality test - Pugh, William (Advances in Computing and Information—ICCI'90, 1990)

Reasoning situated in time I: Basic concepts - Elgot-Drapkin,J. J; Perlis, Don (Journal of Experimental and Theoretical Artificial Intellige, 1990)

Sequence of a cDNA from the Drosophila melanogaster white gene. - Pepling,M; Mount, Stephen M. (Nucleic Acids ResearchNucleic Acids Res, 1990)

Skip lists: a probabilistic alternative to balanced trees - Pugh, William (Communications of the ACMCommun. ACM, 1990)

Thing and Thought - Perlis, Don (Knowledge Representation and Defeasible Reasoning. Kluwer, 1990)

Two-directional record layout for multiple inheritance - Pugh, William; Weddell,G. (Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, 1990)

Assessing others' knowledge and ignorance - Kraus,S.; Perlis, Don (Proceedings of the 4th International Symposium on Methodologies for Intelligent Systems, 1989)

Automatically transforming regularly structured linear documents into hypertext. - Furuta,R.; Plaisant, Catherine; Shneiderman, Ben (Electronic Publishing, 1989)
Fully automatic conversion of a paper-based document into hypertext can be achieved in manycases if the original document is naturally partitioned into a collection of small-sized pieces that are unambiguously and consistently structured. We describe the methodology that we have used successfully to design and implement several straightforward conversions from the original document’s machine-readable markup.

A comfort measure for diagnostic problem solving - Peng,Yun; Reggia, James A. (Information Sciences, 1989)
In order to apply Bayes' theorem for diagnostic problem solving when multiple disorders can occur simultaneously, several previous proposals have suggested using the ratio of posterior probabilities to rank diagnostic hypotheses. Approaches using such relative likelihoods lose the measure of absolute strengths of hypotheses, and thus are incapable of evaluating the “quality” of a problem solution. In this paper, we propose to impose a quantity called a “comfort measure” on the solution: a solution of a diagnostic problem is a minimal-size set of hypotheses such that the sum of their posterior probabilities exceeds a given comfort measure. Based on a probabilistic causal model developed previously, a problem-solving strategy is presented which does not require the manifestation independence assumption required with direct Bayesian classification, and which is applicable to multimembership classification problems. This strategy selectively generates diagnostic hypotheses and calculates both their relative likelihood and the lower and upper bounds of their posterior probabilities. These bounds are successively refined as more hypotheses are generated. Using these bounds, not the real posterior probabilities, the problem-solving strategy identifies a solution satisfying the given comfort measure, usually after only a small portion of all possible hypotheses have been generated.

A connectionist model for diagnostic problem solving - Peng,Y.; Reggia, James A. (Systems, Man and Cybernetics, IEEE Transactions on, 1989)

An experimental evaluation of three touch screen strategies within a hypertext database - Potter,Richard; Berman,Mitchell; Shneiderman, Ben (International Journal of Human-Computer Interaction, 1989)
High resolution touch screens and novel usage strategies have overcome earlier problems with parallax and inaccurate pointing. A study testing the utility of three touch screen strategies within the Hyperties hypertext environment was performed. This provided a replication and extension of an earlier touch screen strategy comparison that focused on small closely?spaced targets. The experiment compared three touch screen strategies in three experimental tasks that reflect hypertext usage. The results showed that a strategy that only uses the initial impact with the touch screen causes the user to miss the target more than other touch strategies. A statistically significant difference in errors was found. Our results should encourage system implementers and touch screen hardware designers to support ?touch mouse? strategies that enable cursor dragging on the touch screen surface.High resolution touch screens and novel usage strategies have overcome earlier problems with parallax and inaccurate pointing. A study testing the utility of three touch screen strategies within the Hyperties hypertext environment was performed. This provided a replication and extension of an earlier touch screen strategy comparison that focused on small closely?spaced targets. The experiment compared three touch screen strategies in three experimental tasks that reflect hypertext usage. The results showed that a strategy that only uses the initial impact with the touch screen causes the user to miss the target more than other touch strategies. A statistically significant difference in errors was found. Our results should encourage system implementers and touch screen hardware designers to support ?touch mouse? strategies that enable cursor dragging on the touch screen surface.

Explicitly biased generalization - Gordon,D.; Perlis, Don (Computational Intelligence, 1989)

Incremental computation via function caching - Pugh, William; Teitelbaum,T. (Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1989)

A semantics based verification tool for finite state systems - Cleaveland, Rance; Parrow,J.; Steffen,B. (Proceedings of the IFIP WG6, 1989)

Software metric classification trees help guide the maintenance of large-scale systems - Selby,R. W; Porter, Adam (, Conference on Software Maintenance, 1989., Proceedings, 1989)
The 80:20 rule states that approximately 20% of a software system is responsible for 80% of its errors. The authors propose an automated method for generating empirically-based models of error-prone software objects. These models are intended to help localize the troublesome 20%. The method uses a recursive algorithm to automatically generate classification trees whose nodes are multivalued functions based on software metrics. The purpose of the classification trees is to identify components that are likely to be error prone or costly, so that developers can focus their resources accordingly. A feasibility study was conducted using 16 NASA projects. On average, the classification trees correctly identified 79.3% of the software modules that had high development effort or faults
Keywords: automated method; automatic programming; classification; Classification tree analysis; classification trees; Computer errors; empirically-based models; error-prone software objects; Fault diagnosis; feasibility study; high development effort; Large-scale systems; multivalued functions; NASA; NASA projects; recursive algorithm; Software algorithms; software engineering; Software maintenance; Software measurement; software metrics; software modules; Software systems; trees (mathematics)

Some Brief Essays on Mind - Perlis, Don (ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE, 1989)
The author tries to explain his view of artificial intelligence, and more broadly how it fits into science as a whole. In doing so, he will not hesitate to indulge in sheer speculation when it seems to fit the topic. He will begin with a negative thought (one that he does not agree with). Consider the statement that, while robots and AI (artificial intelligence) may make great strides in the future, still they never will be able to produce music with the sensitivity of certain humans with great musical talent. (kr)
Keywords: *ARTIFICIAL INTELLIGENCE; CYBERNETICS; HUMANS; Music; Robots

A spectrum of automatic hypertext constructions - Furuta,R.; Plaisant, Catherine; Shneiderman, Ben (Hypermedia, 1989)
We describe our experiences with four separate conversions from paper documents into hypertext and discuss the lessons we have learned. The paper document's organization affects the ease with which it can be converted and the appropriateness of the resu lting hypertext. The form of the paper document's machine-readable `markup' description affects the ability to transform the structure automatically. Designing the link structures that tie together the parts of the hypertext takes special care in automa ting, as badly-designed and incorrectly-formed links destroy the integrity of the hypertext. Overall, each of the conversions followed the same basic methodology, providing the handle for the development of `power tools' that can be applied to simplify s ubsequent conversions.

Truth and meaning (research note) - Perlis, Don (Artificial intelligence, 1989)

The American Voice and Robotics" Guardian" System: A Case Study in User Interface Usability Evaluation - Wallace,D.F.; Norman,K. L; Plaisant, Catherine (University of Maryland, 1988)
American Voice and Robotics (AVR), in conjunction with the Maryland Industrial Partnerships(MIPS) program, contracted the Human-Computer Interaction Laboratory (HCIL) to evaluate the user interface of AVR's "Guardian"home automation system. Among their goals for the system were:Ease of use and learning of the system (intuitiveness), Aesthetic appeal, Unintimidating, Impressive, High Functionality, Fast and accurate input of useraction, Clear feedback, Forgiving to errors, and Fun to use. Researchers found that users were initially impressed with the system, but that they were not fully satisfied with it. Specific initial recommendations, theoretical and methodological concerns, procedures, results, and direction of future research will be discussed.

Autocircumscription - Perlis, Don (Artificial Intelligence, 1988)
Reasoning can be used to select among various possible interpretations of events. But how are these possibilities determined? We isolate two key technical features of circumscription (consistency and minimization), and use the first as the basis for a reformulation of the circumscription principle in a way related to possibility, self-knowledge, and negative introspection. The second (minimization) then can be separately expressed on its own. Conceptual clarity and a kind of validity are results of this separation, as well as a computational means to determine (sometimes) when a wff is not among a reasoner's conclusions.

Commonsense set theory - Perlis, Don (Meta-Level Architectures and Reflection, 1988)

An improved replacement strategy for function caching - Pugh, William (Proceedings of the 1988 ACM conference on LISP and functional programming - LFP '88, 1988)

Languages with self-reference II : Knowledge, belief, and modality - Perlis, Don (Artificial Intelligence, 1988)
Negative results of Montague and Thomason have diverted research in propositional attitudes away from syntactic ("first-order") approaches, encouraging modal formalisms instead, especially in representing epistemic notions. We show that modal logics are on no firmer ground than first-order ones when equally endowed with substitutive self-reference. Nonetheless, there may still be remedies, hinging in part upon a distinction between "dynamic" and "static" notions of provability and belief (an earlier version of this paper emphasized a somewhat different distinction).

Learning from examples: generation and evaluation of decision trees for software resource analysis - Selby,R. W; Porter, Adam (IEEE Transactions on Software Engineering, 1988)
A general solution method for the automatic generation of decision (or classification) trees is investigated. The approach is to provide insights through in-depth empirical characterization and evaluation of decision trees for one problem domain, specifically, that of software resource data analysis. The purpose of the decision trees is to identify classes of objects (software modules) that had high development effort, i.e. in the uppermost quartile relative to past data. Sixteen software systems ranging from 3000 to 112000 source lines have been selected for analysis from a NASA production environment. The collection and analysis of 74 attributes (or metrics), for over 4700 objects, capture a multitude of information about the objects: development effort, faults, changes, design style, and implementation style. A total of 9600 decision trees are automatically generated and evaluated. The analysis focuses on the characterization and evaluation of decision tree accuracy, complexity, and composition. The decision trees correctly identified 79.3% of the software modules that had high development effort or faults, on the average across all 9600 trees. The decision trees generated from the best parameter combinations correctly identified 88.4% of the modules on the average. Visualization of the results is emphasized, and sample decision trees are included
Keywords: Analysis of variance; Artificial intelligence; Classification tree analysis; Data analysis; decision theory; Decision trees; Fault diagnosis; Information analysis; machine learning; metrics; NASA; production environment; software engineering; software modules; software resource analysis; Software systems; Termination of employment; trees (mathematics)

Type theory and concurrency - Cleaveland, Rance; Panangaden,P. (International Journal of Parallel Programming, 1988)

Uniform accountability for multiple modes of reasoning - Kanal,Laveen; Perlis, Don (International Journal of Approximate Reasoning, 1988)
This article discusses various issues surrounding the general debate on knowledge representation methods and argues in favor of the idea that while many methods are necessary, there also must be a kind of unified nature to the enterprise if it is to serve the needs of intelligence. Specific points include the misleading distinction between probabilistic and logical reasoning regarding the notion of truth and also some matters of nonmonotonicity. An effort is made to sample the broad range of approaches in the literature, with an eye toward such a unification.
Keywords: Artificial intelligence; commonsense reasoning; probabilistic logic; probability theory; uncertainty representation

ALEX-an Alexical Programming Language - Kozen,D.; Teitelbaum,T.; Chen,W. Z; Field,J. H; Pugh, William; Vander Zanden,B. T (Cornell University, 1987)
ALEX is an experimental language for high-level parallel programming. It is a testbed for exploring various non-traditional ways of expressing algorithmic ideas, making extensive use of high-resolution color graphics. The language itself is not a programming language in the traditional sense, since there is no lexical syntax. This paper discusses the basic design of the ALEX user interface.

Circumscribing with sets - Perlis, Don (Artificial Intelligence, 1987)
Sets can play an important role in circumscription's ability to deal in a general way with certain aspects of commonsense reasoning. A result of Kueker indicates that sentences that intuitively one would want circumscription to prove are nonetheless not so provable in a formal setting devoid of sets. Furthermore, when sets are introduced, first-order circumscription handles these cases very easily, obviating the need for second-order circumscription. The "Aussonderungs" axiom of ZF set theory plays an intuitive role in this shift back to a first-order language

Circumscription as introspection - Perlis, Don (Proceedings of the Second International Symposium on Methodologies for intelligent systems, 1987)

Diagnostic problem-solving with causal chaining - Peng,Y.; Reggia, James A. (International Journal of Intelligent Systems, 1987)

THE DISCRETE GEODESIC PROBLEM - JOSEPH,SB; Mount, Dave; Papadimitriou,C. H (SIAM Journal on Computing (SICOMP), 1987)
We presentan algorithm for determining the shortest path between a source and a destinationon an arbitrary (possibly nonconvex) polyhedralsurface. The path is constrained to lie on the surface, and distances are measured according to the Euclidean metric. Our algorithm runs in time O(n log n) and requires O(n2) space, where n is the number of edges of the surface. After we run our algorithm, the distance from the source to any other destination may be determined using standard techniques in time O(log n) by locating the destination in the subdivision created by the algorithm. The actual shortest path from the source to a destination can bereported in time O(k+log n), where k is the number of faces crossed by the path. The algorithm generalizes to the case of multiple source points to build the Voronoi diagram on the surface, where n is now the maximum of the number of vertices and the number of sources.

How can a program mean - Perlis, Don (Proceedings of the 10th Int'l Joint Conference on Artificial Intelligence, 1987)

Life on a desert island - Drapkin,J.; Miller,M.; Perlis, Don (Proc. Workshop on The Frame Problem in Artificial Intelligence, 1987)

Modeling diagnostic reasoning: a summary of parsimonious covering theory - Reggia, James A.; Peng,Y. (Computer methods and programs in biomedicine, 1987)

A probabilistic causal model for diagnostic problem solving (parts 1 and 2) - Peng,Y.; Reggia, James A. (IEEE Transactions on Systems, Man and Cybernetics, 1987)

Proving self-utterances - Miller,M.; Perlis, Don (Journal of Automated Reasoning, 1987)

Completeness results for circumscription - Perlis, Don; Minker, Jack (Artificial Intelligence, 1986)
We investigate the model theory of the notion of circumscription, and find completeness theorems that provide a partial converse to a result of McCarthy. We show that the circumscriptive theorems are precisely the truths of the minimal models, in the case of various classes of theories, and for various versions of circumscription. We also present an example of commonsense reasoning in which first-order circumscription does not achieve the intuitive and desired minimization.

On the consistency of commonsense reasoning - Perlis, Don (Computational Intelligence, 1986)

Intentionality as internality - Perlis, Don; Hall,R. (Behavioral and Brain Sciences, 1986)

A Parallel Self-Modifying Default Reasoning System - Minker, Jack; Perlis, Don; Subramanian,K. (AAAI, 1986)

A preliminary excursion into step-logics - Drapkin,J.; Perlis, Don (Proceedings of the ACM SIGART international symposium on Methodologies for intelligent systems -, 1986)

Self-reference, knowledge, belief, and modality - Perlis, Don (Proc 5th National Conference on AI, 1986)

Step-logics: An alternative approach to limited reasoning - Drapkin,J.; Perlis, Don (Proceedings of the European Conf. on Artificial Intelligence, 1986)

Answer justification in abductive expert systems for diagnostic problem solving - Reggia, James A.; Perricone,B.; Nau, Dana S.; Peng,Y. (IEEE Transactions on Biomedical Engineering, 1985)

Answer Justification in Diagnostic Expert Systems-Part II: Supporting Plausible Justifications - Reggia, James A.; Perricone,B. T.; Nau, Dana S.; Peng,Y. (Biomedical Engineering, IEEE Transactions on, 1985)

Computing protected circumscription - Minker, Jack; Perlis, Don (The Journal of Logic Programming, 1985)

Efficient implementation of a shifting algorithm - Perl,Y.; Vishkin, Uzi (Discrete applied mathematics, 1985)

A formal model of abductive inference - Reggia, James A.; Nau, Dana S.; Wang,P.; Peng,Y. (Information Sciences, 1985)

A formal model of diagnostic inference, II. Algorithmic solution and application - Reggia, James A.; Nau, Dana S.; Wang,P. Y; Peng,Y. (Information Sciences, 1985)

Languages with self-reference I: Foundations - Perlis, Don (Artificial Intelligence, 1985)
It is argued that a proper treatment of cognitive notions such as beliefs and concepts should allow broad and consistent expression of syntax and semantics, and that this in turn depends on self-reference. A theory of quotation and unquotation is presented to this end that appears to make unnecessary the usual hierarchical and non-first-order constructions for these notions. In the current paper (Part I) the underlying theory is presented; a sequel will treat in more detail the applications to cognition.

Learning a menu selection tree: training methods compared - Parton,Diana; Huffman,Keith; Pridgen,Patty; Norman,Kent; Shneiderman, Ben (Behaviour & Information Technology, 1985)
Abstract Abstract. Menu selection systems sometimes present learning problems for novice users. This comparison of four training methods for novice users found that the global tree diagram of the menu system was superior to command sequence and frame presentation methods, and somewhat better than trial and error. Methods were evaluated on the basis of (1) number of target nodes found, (2) mean number of selections to a target node, (3) recall of the menu structure, and (4) subjective rating of ease of learning.Abstract Abstract. Menu selection systems sometimes present learning problems for novice users. This comparison of four training methods for novice users found that the global tree diagram of the menu system was superior to command sequence and frame presentation methods, and somewhat better than trial and error. Methods were evaluated on the basis of (1) number of target nodes found, (2) mean number of selections to a target node, (3) recall of the menu structure, and (4) subjective rating of ease of learning.