ANN: A library for approximate nearest neighbor searching - Mount, Dave; Arya,S. (CGC 2nd Annual Fall Workshop on Computational Geometry, 1997)

APGAN and RPMC: Complementary heuristics for translating DSP block diagrams into efficient software implementations - Bhattacharyya, Shuvra S.; Murthy,P. K; Lee,E. A (Design Automation for Embedded Systems, 1997)

Bringing treasures to the surface: iterative design for the Library of Congress National Digital Library Program - Plaisant, Catherine; Marchionini,Gary; Bruns,Tom; Komlodi,Anita; Campbell,Laura (Proceedings of the SIGCHI conference on Human factors in computing systems, 1997)
Keywords: browse; design process; digital libraries; dynamic query; java; preview; search; web design

Challenges in sending large radiology images over military communications channels - Cleary,K.R.; Levine,B.A.; Norton,G.S.; Mundur,P.V. (Proceedings of SPIE, 1997)

A characterization of the partial stable models for disjunctive deductive databases - Minker, Jack (Logic programming: proceedings of the 1997 International Symposium, 1997)

Collabcad: A toolkit for integrated synchronous and asynchronous sharing of cad applications - Mishra,P.; Varshney, Amitabh; Kaufman,A. (Proceedings TeamCAD: GVU/NIST Workshop on Collaborative Design, Atlanta, GA, USA, 1997)
We are developing CollabCAD, a novel software architecture and toolkit, that supports shar-ing of arbitrary user-defined objects or applications over intranets and the internet. Developers can use CollabCAD to rapidly re-engineer existing CAD applications to be collaboration-capable or build new collaboration-capable CAD applications. CollabCAD provides the following functionalities: 1. Support for fiexible forms of sharing in which users can interact with multiple presentations of CAD applications or objects. 2. asynchronous and synchronous sharing, as well as a mixture of both, 3. effective communication between users by supporting direct manipulation of user-defined objects, and a new form of sharing called para-synchronous sharing, 4. support for asymmetric collaborations between users with 1 different roles, or, 2 systems with different input-output, hardware and network capabilities. We plan to test and evaluate CollabCAD by building collaboration systems in several CAD- oriented application areas: these include virtual reality for mechanical, architectural and molec- ular CAD, and volume visualization and volume graphics for CAD applications.

Combining Closed World Assumptions with Stable Negation - Ruiz,Carolina; Minker, Jack (Fundamenta Informaticae, 1997)
We study the semantics of disjunctive logic programs that simultaneously contain multiple kinds of default negations. We introduce operators notG, notW, and notSTB in the language of logic programs to represent the Generalized Closed World Assumption, the Weak Generalized Closed World Assumption, and the stable negation, respectively. The notion of stratification involving different kinds of negations is defined and the meaning of stratified programs with multiple negations is described. The class of stratified programs is extended to the class of quasi-stratified programs and the semantics of the latest class is studied.

Comments on "Towards a framework for software measurement validation" - Morasca,S.; Briand,L.C.; Basili, Victor R.; Weyuker,E.J.; Zelkowitz, Marvin V; Kitchenham,B.; Lawrence Pfleeger,S.; Fenton,N. (Software Engineering, IEEE Transactions on, 1997)
A view of software measurement that disagrees with the model presented by Kitchenham, Pfleeger, and Fenton (1995), is given. Whereas Kitchenham et al. argue that properties used to define measures should not constrain the scale type of measures, the authors contend that that is an inappropriate restriction. In addition, a misinterpretation of Weyuker's (1988) properties is noted.
Keywords: measurement; metrics; software; testing; program; validation; program; verification; software

Comprehension and object recognition capabilities for presentations of simultaneous video key frame surrogates - Slaughters,Laura; Shneiderman, Ben; Marchionini,Gary (Research and Advanced Technology for Digital LibrariesResearch and Advanced Technology for Digital Libraries, 1997)
The demand for more efficient browsing of video data is expected to increase as greater access to this type of data becomes available. This experiment looked at one technique for displaying video data using key frame surrogates that are presented as a ldquoslide showrdquo. Subjects viewed key frames for between one and four video clips simultaneously. Following this presentation, the subjects performed object recognition and gist comprehension tasks in order to determine human thresholds for divided attention between these multiple displays. It was our belief that subject performance would degrade as the number of slide shows shown simultaneously increased. For object recognition and gist comprehension tasks, a decrease in performance between the one slide show display and the two, three or four slide show displays was found. In the case of two or three video presentations, performance is about the same, and there remains adequate object recognition abilities and comprehension of the video clips. Performance drops off to unacceptable levels when four slide shows are displayed at once.

Designing interactive multimedia (panel) - Scarlatos,Lori L.; Darken,Rudolph P.; Harada,Komei; Heeter,Carrie; Muller,Richard; Shneiderman, Ben (Proceedings of the fifth ACM international conference on Multimedia, 1997)

Direct manipulation vs. interface agents - Shneiderman, Ben; Maes,P. (Interactions, 1997)

Efficient algorithms for robust feature matching - Mount, Dave; Netanyahu,N. S; Le Moigne,J. (Image Registration Workshop Proceedings, 1997)
One of the basic building blocks in any point-based registration scheme involves matching feature points that are extracted from the sensed image to their counterparts in the reference image. This leads to the fundamental problem of point matching: given two sets of points, find the affine transformation that transforms one point set so that its distance from the other point set is minimized. Because of measurement errors and the presence of outlying data points, it is important that the distance measure between two point sets be robust to these effects. We measure distances using the generalized Hausdorff distance. Point matching can be a computationally intensive task, and there have been a number of algorithms and approaches proposed for solving this problem both theoretical and applied. We present two approaches to the point matching problem, in an attempt to reduce the computational complexity of the problem, while still providing guarantees on the quality of the final match. Our first method is an approximation algorithm, which is loosely based on a branch-and-bound approach due to Huttenlocher and Rucklidge. We show that by varying the approximation error bounds, it is possible to achieve a tradeoff between the quality of the match and the running time of the algorithm. Our second method involves a Monte Carlo method for accelerating the search process used in the first algorithm. With high probability this method succeeds in finding an approximately optimal match. We establish the efficiency of our approaches empirically.

Genetic depletion reveals an essential role for an SR protein splicing factor in vertebrate cells - Mount, Stephen M. (BioEssays, 1997)
SR proteins are essential for the splicing of messenger RNA precursors in vitro, where they also alter splice site selection in a concentration-dependent manner. Although experiments involving overexpression or dominant mutations have confirmed that these proteins can influence RNA processing decisions in vivo, similar results with loss-of-function mutations have been lacking. Now, a system for genetic depletion of the chicken B cell line DT40 has revealed that the SR protein ASF/SF2 (alternative splicing factor/splicing factor 2) is essential for viability in these cells(1). This study opens the way for a complete functional dissection of this protein, and other SR proteins, in vivo.

Geometric intersection - Mount, Dave (Handbook of Discrete and Computational Geometry, chapter 33, 1997)
Detecting whether two geometric objects intersect and computing the region of intersection are fundamental problems in computational geometry. Geometric intersection problems arise naturally in a number of applications. Examples include geometric packing and covering, wire and component layout in VLSI, map overlay

Hardness of flip-cut problems from optical mapping - DANČÍK,V.; Hannenhalli, Sridhar; Muthukrishnan,S. (Journal of Computational Biology, 1997)

Hardness of flip-cut problems from optical mapping [DNA molecules application] - Dancik,V.; Hannenhalli, Sridhar; Muthukrishnan,S. (Compression and Complexity of Sequences 1997. Proceedings, 1997)
Optical mapping is a new technology for constructing restriction maps. Associated computational problems include aligning multiple partial restriction maps into a single “consensus” restriction map, and determining the correct orientation of each molecule, which was formalized as the exclusive binary flip cut (EBFC) problem by Muthukrishnan and Parida (see Proc. of the First ACM Conference on Computational Molecular Biology (RECOMB), Santa Fe, p.209-19, 1997). Here, the authors prove that the EBFC problem, as well as a number of its variants, are NP-complete. They also identify another problem formalized as binary shift cut (BSC) problem motivated by the fact that there might be missing fragments at the beginnings and/or the ends of the molecules, and prove it to be NP-complete. Therefore, they do not have efficient, that is, polynomial time solutions unless P=NP
Keywords: binary shift cut; Biochemistry; Bioinformatics; biological techniques; Biology; biomedical optical imaging; combinatorial mathematics; combinatorial problem; computational complexity; computational problems; DNA; DNA molecule; exclusive binary flip cut; flip-cut problem hardness; Genetic engineering; Genomics; MATHEMATICS; molecular biology; molecular biophysics; molecule orientation; multiple partial restriction maps; NP-complete problem; optical mapping; polynomial time solutions; Polynomials; sequences

How to (plan to) meet a deadline between now and then - Nirkhe,M.; Kraus,S.; Miller,M.; Perlis, Don (Journal of Logic and Computation, 1997)

Intelligent software agents vs. user-controlled direct manipulation: a debate - Maes,Pattie; Shneiderman, Ben; Miller,Jim (CHI '97 extended abstracts on Human factors in computing systems: looking to the future, 1997)
Critical issues in human-computer interaction - in particular, the advantages and disadvantages of intelligent agents and direct manipulation - will be discussed, debated, and hotly contested. The intent of the participants is to strike an appropriate balance between a serious discussion of the issues and an entertaining debate.
Keywords: agents; direct manipulation; graphical representation; intelligent interfaces

Joint minimization of code and data for synchronous dataflow programs - Murthy,P. K; Bhattacharyya, Shuvra S.; Lee,E. A (Formal Methods in System Design, 1997)

Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model - Agarwala,Richa; Batzoglou,Serafim; DančíK,Vlado; Decatur,Scott E.; Hannenhalli, Sridhar; Farach,Martin; Muthukrishnan,S.; Skiena,Steven (Journal of Computational Biology, 1997)
We consider the problem of determining the three-dimensional folding of a protein given its one-dimensional amino acid sequence. We use the HP model for protein folding proposed by Dill (1985), which models protein as a chain of amino acid residues that are either hydrophobic or polar, and hydrophobic interactions are the dominant initial driving force for the protein folding. Hart and Istrail (1996a) gave approximation algorithms for folding proteins on the cubic lattice under the HP model. In this paper, we examine the choice of a lattice by considering its algorithmic and geometric implications and argue that the triangular lattice is a more reasonable choice. We present a set of folding rules for a triangular lattice and analyze the approximation ratio they achieve. In addition, we introduce a generalization of the HP model to account for residues having different levels of hydrophobicity. After describing the biological foundation for this generalization, we show that in the new model we are able to achieve similar constant factor approximation guarantees on the triangular lattice as were achieved in the standard HP model. While the structures derived from our folding rules are probably still far from biological reality, we hope that having a set of folding rules with different properties will yield more interesting folds when combined.

Logic and Databases Past, Present, and Future - Minker, Jack (AI Magazine, 1997)

MDL: a language and compiler for dynamic program instrumentation - Hollingsworth, Jeffrey K; Niam, O.; Miller, B. P; Zhichen Xu; Goncalves,M. J.R; Ling Zheng (, 1997 International Conference on Parallel Architectures and Compilation Techniques., 1997. Proceedings, 1997)
We use a form of dynamic code generation, called dynamic instrumentation, to collect data about the execution of an application program. Dynamic instrumentation allows us to instrument running programs to collect performance and other types of information. The instrumentation code is generated incrementally and can be inserted and removed at any time. Our instrumentation currently runs on the SPARC, PA-RISC, Power 2, Alpha, and x86 architectures. Specification of what data to collect are written in a specialized language called the Metric Description Language, that is part of the Paradyn Parallel Performance Tools. This language allows platform independent descriptions of how to collect performance data. It also provides a concise way to specify, how to constrain performance data to particular resources such as modules, procedures, nodes, files, or message channels (or combinations of these resources). We also describe the details of how we weave instrumentation into a running program
Keywords: Alpha architecture; application program; application program interfaces; Application software; compiler generators; Computer science; dynamic code generation; Dynamic compiler; dynamic program instrumentation; Educational institutions; files; instrumentation code; Instruments; MDL; measurement; message channels; Message passing; Metric Description Language; modules; nodes; Operating systems; optimising compilers; PA-RISC; Paradyn Parallel Performance Tools; Parallel architectures; parallel programming; performance data; platform independent descriptions; Power 2 architecture; Power generation; procedures; program debugging; Program processors; running programs; Runtime; software metrics; SPARC; Specification languages; x86 architecture

The measured cost of copying garbage collection mechanisms - Hicks, Michael W.; Moore,Jonathan T.; Nettles,Scott M. (SIGPLAN Not., 1997)
We examine the costs and benefits of a variety of copying garbage collection (GC) mechanisms across multiple architectures and programming languages. Our study covers both low-level object representation and copying issues as well as the mechanisms needed to support more advanced techniques such as generational collection, large object spaces, and type segregated areas.Our experiments are made possible by a novel performance analysis tool, Oscar. Oscar allows us to capture snapshots of programming language heaps that may then be used to replay garbage collections. The replay program is self-contained and written in C, which makes it easy to port to other architectures and to analyze with standard performance analysis tools. Furthermore, it is possible to study additional programming languages simply by instrumenting existing implementations to capture heap snapshots.In general, we found that careful implementation of GC mechanisms can have a significant benefit. For a simple collector, we measured improvements of as much as 95%. We then found that while the addition of advanced features can have a sizeable overhead (up to 15%), the net benefit is quite positive, resulting in additional gains of up to 42%. We also found that results varied depending upon the platform and language. Machine characteristics such as cache arrangements, instruction set (RISC/CISC), and register pool were important. For different languages, average object size seemed to be most important.The results of our experiments demonstrate the usefulness of a tool like Oscar for studying GC performance. Without much overhead, we can easily identify areas where programming language implementors could collaborate with GC implementors to improve GC performance.

Model generation and state generation for disjunctive logic programs - Seipel,Dietmar; Minker, Jack; Ruiz,Carolina (The Journal of Logic Programming, 1997)
This paper investigates two fixpoint approaches for minimal model reasoning with disjunctive logic programs P. The first one, called model generation, is based on an operator TPINT defined on sets of Herbrand interpretations whose least fixpoint is logically equivalent to the set of minimal Herbrand models of the program. The second approach, called state generation, uses a fixpoint operation TPs based on hyperresolution. It operates on disjunctive Herbrand states, and its least fixpoint is the set of logical consequences of P, the so-called minimal model state of the program. We establish a useful relationship between hyperresolution by PPs and model generation by TPINT. Then we investigate the problem of continuity of the two operators TPs and TPINT. It is known that the operator TPs is continuous, and so it reaches its least fixpoint in at most ω iterations. On the other hand, the question of whether TPINT is continuous has been open. We show by a counterexample that TPINT is not continuous. Nevertheless, we prove that it converges towards its least fixpoint in at most ω iterations, too, as follows from the relationship that we show exists between hyperresolution and model generation. We define an iterative version of TPINT that computes the perfect model semantics of stratified disjunctive logic programs. On each stratum of the program, this operator converges in at most ω iterations. Model generations for the stable semantics and the partial stable semantics are respectively achieved by using this iterative operator together with the evidential transformation and the 3-S transformation.

Parallelizing and algorithm for visibility on polyhedral terrain - Teng,Y. A; Mount, Dave; Puppo,E.; Davis, Larry S. (International Journal of Computational Geometry and Applications, 1997)
The best known output-sensitive sequential algorithm for computing the viewshedon a polyhedral terrain from a given viewpoint was proposed by Katz, Overmars, and Sharir 10, and achieves time complexity O((k + n(n)) logn) where n and k are the input and output sizes respectively, and () is the inverse Ackermann's function. In this paper, we present a parallel algorithm that is based on the work mentioned above, and achieves O(log2 n) time complexity, with work complexity O((k +n(n)) logn) in a CREW PRAM model. This improves on previous parallel complexity while maintaining work e ciency with respect to the best sequential complexity known.

A practical approximation algorithm for the LMS line estimator - Mount, Dave; Netanyahu,Nathan S.; Romanik,Kathleen; Silverman,Ruth; Wu,Angela Y. (Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, 1997)
Keywords: Approximation algorithms; least median-of-squares regression; line arrangements; line fitting; randomized algorithms; robust estimation

Semantic query optimization for object databases - Grant,J.; Gryz,J.; Minker, Jack; Raschid, Louiqa (Data Engineering, 1997. Proceedings. 13th International Conference on, 1997)

Semantic query optimization for object databases - Grant,J.; Gryz,J.; Minker, Jack; Raschid, Louiqa (Data Engineering, 1997. Proceedings. 13th International Conference on, 1997)
Presents a technique for semantic query optimization (SQO) for object databases. We use the ODMG-93 (Object Data Management Group) standard ODL (Object Database Language) and OQL (Object Query Language) languages. The ODL object schema and the OQL object query are translated into a DATALOG representation. Semantic knowledge about the object model and the particular application is expressed as integrity constraints. This is an extension of the ODMG-93 standard. SQO is performed in the DATALOG representation, and an equivalent logic query and (subsequently) an equivalent OQL object query are obtained. SQO is based on the residue technique of Chakravarthy et al. (1990). We show that our technique generalizes previous research on SQO for object databases. It can be applied to queries with structure constructors and method application. It utilizes integrity constraints about keys, methods and knowledge of access support relations, to produce equivalent queries, which may have more efficient evaluation plans
Keywords: application; object; constraints; keys; method; constructors; DATALOG; data; databases; object-oriented; databases; query; Datalog; Evaluation; integrity; data; languages; query; Logic; object; optimization; structure; plans; residue; processing; software; query; query; access; query; integrity; relations; equivalent; representation; ODL; schema; ODMG-93; standard; OQL; standards; structures; object-oriented; Support; technique; semantic

Semi-automatic acquisition of domain-specific translation lexicons - Resnik, Philip; Melamed,I.D. (Proceedings of the fifth conference on Applied natural language processing, 1997)

A Service Layer Routing Protocol for PLAN - Moore,J. T; Hicks, Michael W. (PLAN documentation, September, 1997)

Spanish EuroWordNet and LCS-Based Interlingual MT - Dorr, Bonnie J; Marti,M. Antonia; Castellon,Irene (IN PROCEEDINGS OF THE MT SUMMIT WORKSHOP ON INTERLINGUAS IN MT, 1997)
We present a machine translation framework in which the interlingua -- Lexical Conceptual Structure (LCS) -- is coupled with a definitional component that includes bilingual (EuroWordNet) links between words in the source and target languages. While the links between individual words are language-specific, the LCS is designed to be a language-independent, compositional representation. We take the view that the two types of information -- shallower, transfer-like knowledge as well as deeper, compositional knowledge -- can be reconciled in interlingual machine translation, the former for overcoming the intractability of LCS-based lexical selection, and the latter for relating the underlying semantics of two words cross-linguistically. We describe the acquisition process for these two information types and present results of hand-verification of the acquired lexicon. Finally, we demonstrate the utility of the two information types in interlingual MT.

Testing simple polygons - Arkin,Esther M.; Belleville,Patrice; Mitchell,Joseph S.B.; Mount, Dave; Romanik,Kathleen; Salzberg,Steven; Souvaine,Diane (Computational Geometry, 1997)
We consider the problem of verifying a simple polygon in the plane using “test points”. A test point is a geometric probe that takes as input a point in Euclidean space, and returns “+” if the point is inside the object being probed or “−” if it is outside. A verification procedure takes as input a description of a target object, including its location and orientation, and it produces a set of test points that are used to verify whether a test object matches the description. We give a procedure for verifying an n-sided, non-degenerate, simple target polygon using 5n test points. This testing strategy works even if the test polygon has n + 1 vertices, and we show a lower bound of 3n + 1 test points for this case. We also give algorithms using O(n) test points for simple polygons that may be degenerate and for test polygons that may have up to n + 2 vertices. All of these algorithms work for polygons with holes. We also discuss extensions of our results to higher dimensions.
Keywords: probing; Testing; Verifying

Titan: a High-Performance Remote-sensing Database - Bongki,C. C; Chang,C.; Moon,B.; Acharya, A.; Shock,C.; Sussman, Alan; Saltz, J. (In Proceedings of the 1997 International Conference on Data Engineering, 1997)

Using content-derived names for configuration management - Hollingsworth, Jeffrey K; Miller, E. L (ACM SIGSOFT Software Engineering Notes, 1997)

The virtual microscope. - Ferreira,R.; Moon,B.; Humphries,J.; Sussman, Alan; Saltz, J.; Miller,R.; Demarzo,A. (Proceedings of the AMIA Annual Fall Symposium, 1997)

Visual and textual consistency checking tools for graphical user interfaces - Mahajan,R.; Shneiderman, Ben (IEEE Transactions on Software Engineering, 1997)
Designing user interfaces with consistent visual and textual properties is difficult. To demonstrate the harmful effects of inconsistency, we conducted an experiment with 60 subjects. Inconsistent interface terminology slowed user performance by 10 to 25 percent. Unfortunately, contemporary software tools provide only modest support for consistency control. Therefore, we developed SHERLOCK, a family of consistency analysis tools, which evaluates visual and textual properties of user interfaces. It provides graphical analysis tools such as a dialog box summary table that presents a compact overview of visual properties of all dialog boxes. SHERLOCK provides terminology analysis tools including an interface concordance, an interface spellchecker, and terminology baskets to check for inconsistent use of familiar groups of terms. Button analysis tools include a button concordance and a button layout table to detect variant capitalization, distinct typefaces, distinct colors, variant button sizes, and inconsistent button placements. We describe the design, software architecture, and the use of SHERLOCK. We tested SHERLOCK with four commercial prototypes. The outputs, analysis, and feedback from designers of the applications are presented
Keywords: button analysis tools; Color; dialog box summary table; experiment; graphical analysis tools; Graphical user interfaces; human factors; inconsistent interface terminology; interface color; interface spell checker; Output feedback; Prototypes; SHERLOCK; Software architecture; Software design; software metrics; software prototyping; software tools; Terminology; terminology analysis tools; Testing; textual consistency checking tools; user interface management systems; User interfaces; user performance; visual consistency checking tools

Accounting for boundary effects in nearest-neighbor searching - Arya,S.; Mount, Dave; Narayan,O. (Discrete & Computational Geometry, 1996)
Given n data points ind-dimensional space, nearest-neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest-neighbor searching algorithms are made under the simplifying assumption thatd is fixed and thatn is so large relative tod thatboundary effects can be ignored. This means that for any query point the statistical distribution of the data points surrounding it is independent of the location of the query point. However, in many applications of nearest-neighbor searching (such as data compression by vector quantization) this assumption is not met, since the number of data pointsn grows roughly as 2 d .Largely for this reason, the actual performances of many nearest-neighbor algorithms tend to be much better than their theoretical analyses would suggest. We present evidence of why this is the case. We provide an accurate analysis of the number of cells visited in nearest-neighbor searching by the bucketing andk-d tree algorithms. We assumem dpoints uniformly distributed in dimensiond, wherem is a fixed integer ≥2. Further, we assume that distances are measured in theL ∞ metric. Our analysis is tight in the limit asd approaches infinity. Empirical evidence is presented showing that the analysis applies even in low dimensions.

An adaptive cost system for parallel program instrumentation - Hollingsworth, Jeffrey K; Miller, B. (Euro-Par'96 Parallel Processing, 1996)

AT-AC Introns—An ATtACk on Dogma - Mount, Stephen M. (ScienceScience, 1996)
Messenger RNAs are initially made as long precursor molecules from which final, transcribable mRNAs are assembled. A specialized organelle, the spliceosome, contains small RNAs with pairs of dinucleotides that can pick out complementary pairs of nucleotides at the ends of the introns that are to be spliced together. It has been assumed that these pairs were always GU-AG (or GT-AG in the DNA), but in findings described in this week's issue of Science (p. 1716) and the current issue of Cell (vol. 84, p. 801) a minor class of intron is shown to be flanked by AU-AC (or AT-AC in the DNA). In his Perspective, Mount explains how these maverick introns were discovered and why their existence is so surprising.

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

Basic Electric Circuit Theory: A One-Semester Text - Mayergoyz, Issak D; Lawson,Wes (Academic Press, 1996)
This is the only book on the market that has been conceived and deliberately written as a one-semester text on basic electric circuit theory. As such, this book employs a novel approach to the exposition of the material in which phasors and ac steady-state analysis are introduced at the beginning. This allows one to use phasors in the discussion of transients excited by ac sources, which makes the presentation of transients more comprehensive and meaningful. Furthermore, the machinery of phasors paves the road to the introduction of transfer functions, which are then used in the analysis of transients and the discussion of Bode plots and filters. Another salient feature of the text is the consolidation into one chapter of the material concerned with dependent sources and operational amplifiers. Dependent sources are introduced as linear models for transistors on the basis of small signal analysis. In the text, PSpice simulations are prominently featured to reinforce the basic material and understanding of circuit analysis.Key Features* Designed as a comprehensive one-semester text in basic circuit theory* Features early introduction of phasors and ac steady-state analysis* Covers the application of phasors and ac steady-state analysis* Consolidates the material on dependent sources and operational amplifiers* Places emphasis on connections between circuit theory and other areas in electrical engineering* Includes PSpice tutorials and examples* Introduces the design of active filters* Includes problems at the end of every chapter* Priced well below similar books designed for year-long courses
Keywords: Electric circuits; Technology & Engineering / Electrical

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)

Disjunctive deductive databases: Semantics, updates and architecture - Fernandez,J. A.; Gryz,J.; Minker, Jack (Proceedings of the 4th Bar-Ilan Symposium on Foundations of AI, 1996)
The basic assumption in relational and deductive databases is that there are no gaps in our knowledge. That is, the database cannot store data that contain null values or data that is indefinite. In practical situations knowledge is not precise, and there are gaps in our knowledge. These gaps may be due to null values in the data, may arise when we combine several databases that lead to inconsistent theories, or may occur because information is indefinite in nature, such as in military or medical applications. In this paper we describe semantics for disjunctive deductive databases that extend the work in deductive databases, solve the view update problem, and permit indefinite data to be represented efficiently. Hierarchic, stratified, and normal stable models of disjunctive databases are described. An architecture is proposed for a disjunctive deductive database system and a class of theories for which the architecture will be effective is discussed.

DNA sequence variation in the ribosomal internal transcribed spacer region of freshwater ıt Cladophora species (Chlorophyta) - Marks,J. C; Cummings, Michael P. (J Phycol, 1996)
Freshwater species of Cladophora (Chlorophyta) are globally distributed and occupy an unusually wide range of ecological habitats. Delineating species is difficult because most easily observed morphological traits are highly variable and because sexual reproduction has not been clearly documented. Synthesizing ecological data on freshwater Cladophora species is problematic because it is unclear whether freshwater Cladophora species comprise many genetically distinct species or a few ecologically and morphologically variable and / or plastic species. We determined nucleotide sequences of the internal transcribed spacer (ITS) region of the nuclear ribosomal cistron of freshwater Cladophora species from a wide range of habitats and geographic locations. We compared these sequences to those derived from culture collections of C. fracta and C. glomerata, the two most commonly reported freshwater Cladophora species. Cladophora fracta and C. glomerata had very similar ITS sequences (95.3%). All other sequences were identical to those from the C. fracta or C. glomerata culture collections with the exception of one California sample that was similar to both C. fracta (95.6%) and C. glomerata (92.4%). ITS genotypes did not correlate with morphology or geography. This analysis shows that common freshwater Cladophora species comprise very few (possibly one) ecologically and morphologically variable species.
Keywords: algae; Chlorophyta; Cladophora; diversity; freshwater; genetic; internal; spacer; transcribed

Effect of Chemical Reactions on Decaying Isotropic Turbulence - Martin, M.P; Candler,G. V (APS Meeting Abstracts, 1996)

Effect of chemical reactions on the decay of isotropic homogeneous turbulence - Aguirre,M; Candler,G. V; Martin, M.P (AIAA Fluid Dynamics Conference, 1996)
Direct numerical simulations, (DNS), are usedto simulate the decay of an isotopic, turbulent, chemically-reacting flow at high temperatures. The independent parameters that govern the physical pro- cess are introduced. The different effects from each of the parameters in the flow are explained by using the results from the DNS. It is found that there is a feedback mechanism between the chemical reactions and the turbulent motion. This feedback is positive for exothermic reactions and negative for endother- mic reactions.

Fast sorting by reversal - Berman,Piotr; Hannenhalli, Sridhar (Combinatorial Pattern MatchingCombinatorial Pattern Matching, 1996)
Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. Following a series of work recently, Hannenhalli and Pevzner developed the first polynomial algorithm for the problem of sorting signed permutations by reversals and proposed an O(n 4 ) implementation of the algorithm. In this paper we exploit a few combinatorial properties of the cycle graph of a permutation and propose an O(n 2 (n)) implementation of the algorithm where is the inverse Ackerman function. Besides making this algorithm practical, our technique improves implementations of the other rearrangement distance problems.

Inferring phylogenies from DNA sequence data: The effects of sampling - Otto,S. P; Cummings, Michael P.; Wakeley,J. (New Uses for New PhylogeniesNew Uses for New Phylogenies, 1996)

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

Logic and databases: A 20 year retrospective - Minker, Jack (Logic in Databases, 1996)

Mixing a default rule with stable negation - Minker, Jack; Ruiz,C. (Proceedings of the Fourth International Symposium on Artificial Intelligence and Mathematics, 1996)
Logic programs containing only at most one form ofdefault negation have been studied in the literature. We describe a class of logic programs containing multi- ple forms of default negation. We de ne a meaning for these programs based on the well{founded semantics and the stable semantics. We investigate properties of the new combined semantics and calculate the com- putational complexity of determining the existence of models, and of skeptical and credulous reasoning. An e ective procedure to construct the collection of mod- els characterizing the semantics of a program is given. Applications to knowledge representation and knowl- edge base merging are presented.

Model theoretic approach to view updates in deductive databases - Fernandez,J. A.; Grant,J.; Minker, Jack (Journal of Automated Reasoning, 1996)
The view update problem for deductive databases has been defined as the problem of accomplishing the update of an intensional predicate by modifying appropriately the extensional database. A previous paper by Grant, Horty, Lobo, and Minker developed algorithms for the insertion and the deletion of an intensional predicate in certain important classes of stratified disjunctive deductive databases. This paper introduces a model theoretic approach which encompasses a wide class of Herbrand semantics, including the perfect model and stable model semantics, for disjunctive databases including negation. This generalizes the earlier results: now the intensional database may contain disjunctive and denial rules, and the database may be required to satisfy integrity constraints. As in the previous paper, the algorithms are proved to be correct and best according to the criterion of causing minimal change to the database, where the first priority is to minimize deletions.

Recognition of head gestures using hidden markov models - Morimoto,C.; Yacoob,Yaser; Davis, Larry S. (Pattern Recognition, 1996., Proceedings of the 13th International Conference on, 1996)

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.

Semantic query optimization for bottom-up evaluation - Godfrey,P.; Gryz,J.; Minker, Jack (Foundations of Intelligent Systems, 1996)
Semantic query optimization uses semantic knowledge in databases (represented in the form of integrity constraints) to rewrite queries and logic programs to achieve efficient query evaluation. Much work has been done to develop various techniques for optimization. Most of it, however, is applicable to top-down query evaluation strategies. Moreover, little attention has been paid to the cost of the optimization. We address the issue of semantic query optimization for bottom-up query evaluation strategies with an emphasis on overall efficiency. We focus on a single optimization technique, join elimination. We discuss factors that influence the cost of semantic optimization, and present two different abstract algorithms for optimization. The first pre-processes a query statically before it is evaluated; the second combines query evaluation with semantic optimization using heuristics to achieve the largest possible savings.

Semantics of knowledge-based systems with multiple forms of negation - Ruiz,C.; Minker, Jack (University of Maryland at College Park, 1996)

SEROS – A SELF-ROUTING OPTICAL ATM SWITCH - Guizani,Mohsen; Memon, Atif M. (International Journal of Communication Systems, 1996)
A fault-tolerant high-performance SElf-Routing 2 × 2 Optical ATM Switch (SEROS) is proposed. The switch is designed using all-optical components which allows the exploitation of spatial parallelism. SEROS can be used with any multistage interconnection network such as Omega, Banyan, Shuffle or Benes. For the purpose of this study, SEROS has been incorporated into a generic self-routing multistage interconnection network that uses 2 × 2 switches and is not fault tolerant. Reliability analysis is carried out and the results are compared with two major fault-tolerant networks. They show that without redundant switches, better network survivability is achieved. All the switches in the network are 2 × 2, making it easier to mass produce.
Keywords: 2 × 2 ATM switch; fault-tolerant; MINs; photonic switching network; reliability; self-routing

Simplification envelopes - Cohen,Jonathan; Varshney, Amitabh; Manocha,Dinesh; Turk,Greg; Weber,Hans; Agarwal,Pankaj; Brooks,Frederick; Wright,William (Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, 1996)
Keywords: geometric modeling; hierarchical approximation; levels-of-detail generation; model simplification; offsets; shape approximation

Simulation of the logic switching characteristics of hot-carrier-degraded ultra-thin SOI CMOS inverters - Tai,Gwo-Chung; Korman,Can E.; Mayergoyz, Issak D (Solid-State Electronics, 1996)
The switching characteristics of ultra-thin SOI CMOS inverters with hot-carrier-induced degradations are examined by using device simulations. The simulator employs a robust fixed-point iteration method to avoid conventional matrix solutions. Potential-dependent interface traps and oxide trapped charges are used to model the degradations. The effects of front and back channel degradations in an nMOS device of a CMOS inverter are investigated in steady-state and transient regimes. The nonlinear variation of interface charges cannot be simulated by using a single nMOS device alone since the transition of the inverter is also determined by the pMOS transistor. It is found that the stagnant holes generated by impact ionization have a much greater effect on the rate of the pull-down transient than that of interface charges.

Software synthesis from dataflow graphs - Bhattacharyya, Shuvra S.; Murthy,P. K; Lee,E. A (Springer, 1996)

A three-dimensional MOSFET solver implementing the fixed point iteration technique - Madabhushi,Rajiv; Korman,Can E.; Mayergoyz, Issak D (Solid-State Electronics, 1996)
Our implementation of a fixed-point iteration technique for the three-dimensional (3D) steady-state simulation of MOSFET devices is presented. The simulation program is employed to investigate narrow channel effects on the device current-voltage characteristics. Particularly, the effects of impact ionization and the effects of variations in channel width and the field oxide bird's beak angle are evaluated. The degree to which various field oxide configurations isolate the device from the gate contact over the oxide transition region is determined by comparing the current-voltage characteristics with those of an idealized device with perfect isolation. Perfect isolation is simulated by setting the normal component of the electric field to zero at the semiconductor-field oxide interface. Simulation results show that the 3D computations are essential to account for rapidly varying charge densities and generation rates near the channel edge. Moreover, it is observed that the isolation effects of field oxides increase for larger bird's beak angles.

Tuning the performance of I/O-intensive parallel applications - Acharya, A.; Uysal, M.; Bennett, R.; Mendelson, A.; Beynon, M.; Hollingsworth, Jeffrey K; Saltz, J.; Sussman, Alan (Proceedings of the fourth workshop on I/O in parallel and distributed systems: part of the federated computing research conference, 1996)

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.

Video representations - Bolle,Ruud; Aloimonos, J.; Fermüller, Cornelia (Recent Developments in Computer Vision, 1996)

Visual metaphor and the problem of complexity in the design of Web sites: techniques for generating, recognizing and visualizing structure - Joyce,Michael; Kolker,Robert; Moulthrop,Stuart; Shneiderman, Ben; Unsworth,John Merritt (Proceedings of the the seventh ACM conference on Hypertext, 1996)

Approximate range searching - Arya,Sunil; Mount, Dave (Proceedings of the eleventh annual symposium on Computational geometry, 1995)

Bottom-up computation of perfect models for disjunctive theories - Fernández,J. A.; Minker, Jack (The Journal of logic programming, 1995)

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)

Computing stable and partial stable models of extended disjunctive logic programs - Ruiz,C.; Minker, Jack (Non-Monotonic Extensions of Logic Programming, 1995)
n [Prz91], Przymusinski introduced the partial (or 3-valued) stable model semantics which extends the (2-valued) stable model semantics defined originally by Gelfond and Lifschitz [GL88]. In this paper we describe a procedure to compute the collection of all partial stable models of an extended disjunctive logic program. This procedure consists in transforming an extended disjunctive logic program into a constrained disjunctive program free of negation-by-default whose set of 2-valued minimal models corresponds to the set of partial stable models of the original program.

Dealing with complexity: uniting agents and direct manipulation (panel session) - Riecken,Doug; Maes,Pattie; Shneiderman, Ben; Smith,David Canfield (Conference companion on Human factors in computing systems, 1995)

Deductive Databases and Knowledge Base Systems. - Minker, Jack (Department of Computer Science, University of Maryland, College Park, 1995)
The following sections describe the research that has been accomplished during the entire grant period form September 1, 1991 to March 31, 1995, with partial support from the Air Force Office of Scientific Research and summarizes the papers, prototype systems and theses produced on the grant. Several major areas will be discussed. These are Cooperative Databases Systems, Combining Knowledge Base Systems, Disjunctive Deduction Databases, Extensions to the Semantics of Logic Programming and Parallel Logic Programming. During the first year of the grant we emphasized theoretical aspects of work in deductive databases and knowledge base systems. During the second year we stressed the development of tools and techniques to transfer the theory into practical systems. During the third year we developed prototype systems and experiments with them. Technological developments were made in Cooperative Database Systems and Disjunctive Deductive Databases. New theoretical developments were achieved in the Semantics of Logic Programming and in Combining Databases.
Keywords: *DATA BASES; *KNOWLEDGE BASED SYSTEMS; *RESEARCH MANAGEMENT; *SYSTEMS ENGINEERING; AIR FORCE RESEARCH; COMPUTER LOGIC; COMPUTER PROGRAMMING; COMPUTER PROGRAMMING AND SOFTWARE; COMPUTER SYSTEMS; logic programming; PARALLEL LOGIC PROGRAMMING; PARALLEL PROCESSING; Prototypes; semantics; THESES; TRANSFER.; WUAFOSR2304GS

Defining, Computing, and Visualizing Molecular Interfaces - Varshney, Amitabh; Brooks Jr,Frederick P.; Manocha,Dinesh; Wright,William V.; Richardson,David C. (Proceedings of the 6th conference on Visualization '95, 1995)
A parallel, analytic approach for defining and computing the inter- and intra-molecular interfaces in three dimensions is described. The "molecular interface surfaces" are derived from approximations to the power-diagrams over the participating molecular units. For a given molecular interface our approach can generate a family of interface surfaces parametrized by alpha and beta, where alpha is the radius of the solvent molecule (also known as the probe-radius) and beta is the interface radius that defines the size of the molecular interface. Molecular interface surfaces provide biochemists with a powerful tool to study surface complementarity and to efficiently characterize the interactions during a protein-substrate docking. The complexity of our algorithm for molecular environments is O(n k \log^2{k}), where n is the number of atoms in the participating molecular units and k is the average number of neighboring atoms -- a constant, given alpha and beta.
Keywords: Computational Biochemistry Algorithms Molecular Graphics; Connolly Surfaces; Molecular Interfaces; Molecular Surfaces; Protein-Protein Recognition

Euclidean spanners: short, thin, and lanky - Arya,Sunil; Das,Gautam; Mount, Dave; Salowe,Jeffrey S.; Smid,Michiel (Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 1995)

Experimental investigation of high performance cognitive and interactive text filtering - Oard, Douglas; DeClaris,N.; Dorr, Bonnie J; Faloutsos,C.; Marchionini,G. (, IEEE International Conference on Systems, Man and Cybernetics, 1995. Intelligent Systems for the 21st Century, 1995)
Text filtering has become increasingly important as the volume of networked information has exploded in recent years. This paper reviews recent progress in that field and reports on the development of a testbed for experimental investigation of cognitive and interactive text selection based on a history of user evaluations. An interactive filtering system model is presented and a new cognitive filtering technique which the authors call the Gaussian User Model is described. Because development of analytic measures of text selection effectiveness has proven intractable, the authors have modified the Cornell SMART text retrieval system to create a flexible text filtering testbed for experimental determination of filtering effectiveness. The paper concludes with a description of the design of this testbed system
Keywords: Cause effect analysis; Computer science; Contracts; Cornell SMART text retrieval system; Educational institutions; Gaussian User Model; high performance cognitive interactive text filtering; History; Information filtering; Information filters; Information retrieval; information retrieval system evaluation; Libraries; Matched filters; online front-ends; Query processing; System testing; text selection effectiveness; user evaluations; User interfaces; user modelling

A Family of User Interface Consistency Checking Tools - Mahajan,Rohit; Shneiderman, Ben (Institute for Systems Research Technical Reports, 1995)
Incorporating evaluation metrics with GUI development tools will help designers create consistent interfaces in the future. Complexity in design of interfaces makes efficient evaluation impossible by a single consistency checking evaluation tool. Our focus is on developing a family of evaluation tools in order to make the evaluation process less cumbersome. We have developed a dialog box typeface and color table to facilitate detection of anomalies in color, font, font size, and font style. Concordance tools have been developed to spot variant capitalization and abbreviations globally in the interface and specifically in the button widgets. As buttons are frequently used widgets, a button layout table has been created to spot any inconsistencies in height, width and relative position between a given group of buttons if present. Finally, a terminology basket tool has been created to identify unwanted synonyms of computer related terms used in the interface which may be misleading to the end user.
Keywords: automated metrics; concordance tools; consistency checking tools; Human-computer interaction; spatial; Systems Integration Methodology; textual evaluation tools; user interface

A Family of User Interface Consistency Checking Tools: Design and Development of SHERLOCK - Mahajan,R.; Shneiderman, Ben (Proceedings of the Twentieth Annual Software Engineering Workshop, 1995)
Incorporating evaluation metrics with GUI development tools will help designers create consistent interfaces in the future. Complexity in design of interfaces makes efficient evaluation infeasible by a single consistency checking evaluation tool. Our focus is on developing a family of consistency checking tools to evaluate spatial layout and terminology in user interfaces and make the evaluation process less cumbersome. We have Created a dialog box summary table to provide a compact overview of spatial and visual properties of dozens or hundreds of dialog boxes of the interface. Interface concordance tool has been developed to spot variant capitalization and abbreviations in interface terminology. As buttons are most frequent used widgets, a button concordance tool and a button layout table has been constructed. Button concordance identifies variant capitalization, distinct typefaces, distinct background colors and variant sizes in buttons. Button layout table spots any inconsistencies in height, width and relative position between a given group of buttons. A spell checking tools which detects spelling errors in interface terms has also been included in the tool set. Finally, a terminology basket tool has been created to identify unwanted synonyms of computer related terms used in the interface. These tools are integrated together as SHERLOCK, a family of six consistency checking tools to expedite the evaluation process and provide feedback to the designers plus aid Usability Testing.

A front-end generator for verification tools - Cleaveland, Rance; Madelaine,E.; Sims,S. (Tools and Algorithms for the Construction and Analysis of Systems, 1995)

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.

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)

Localization of Sequences Required for Size-specific Splicing of a SmallDrosophilaIntronin Vitro - Guo,Ming; Mount, Stephen M. (Journal of Molecular Biology, 1995)
Many introns inDrosophilaand other invertebrates are less than 80 nucleotides in length, too small to be recognized by the vertebrate splicing machinery. Comparison of nuclear splicing extracts from human HeLa andDrosophilaKc cells has revealed species-specificity, consistent with the observed size differences. Here we present additional results with the 68 nucleotide fifth intron of theDrosophilamyosin heavy chain gene. As observed with the 74 nucleotide second intron of theDrosophilawhite gene, the wild-type myosin intron is accurately spliced in a homologous extract, and increasing the size by 16 nucleotides both eliminates splicing in theDrosophilaextract and allows accurate splicing in the human extract. In contrast to previous results, however, an upstream cryptic 5′ splice site is activated when the wild-type myosin intron is tested in a human HeLa cell nuclear extract, resulting in the removal of 98 nucleotide intron.The size dependence of splicing inDrosophilaextracts is also intron-specific; we noted that a naturally larger (150 nucleotide) intron from theftzgene is efficiently spliced in Kc cell extracts that do not splice enlarged introns (of 84, 90, 150 or 350 nucleotides) derived from the 74 nucleotidewhiteintron. Here, we have exploited that observation, using a series of hybrid introns to show that a region of 46 nucleotides at the 3′ end of thewhiteintron is sufficient to confer the species-specific size effect. At least two sequence elements within this region, yet distinct from previously described branchpoint and pyrimidine tract signals, are required for efficient splicing of small splicing of small hybrid intronsin vitro.
Keywords: Drosophila; pre-mRNA splicing; intron size; species specificity; in vitrosplicing

M.H.M: Euclidean spanners: short, thin, and lanky - Arya,Sunil; Dast,Gautam; Mount, Dave; Salowe,Jeffrey S.; Smid,Michiel (In: 27th ACM Symposium on Theory of Computing, 1995)
Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest path length between each pair of points is not more than a constant factor longer than the Euclidean distance between the points. In many applications of spanners, it is important that the spanner possess a number of additional properties: low tot al edge weight, bounded degree, and low diameter. Existing research on spanners has considered one property or the other. We show that it is possible to build spanners in optimal O (n log n) time and O(n) space that achieve optimal or near optimal tradeoffs between all combinations of these *Max-Planck-Institut fiir Informatik, D-66123 Saarbrucken,

A note on reducing parallel model simulations to integer sorting - Matias,E.; Vishkin, Uzi (Parallel Processing Symposium, 1995. Proceedings., 9th International, 1995)

The Paradyn parallel performance measurement tool - Miller, B. P; Callaghan, M. D; Cargille, J. M; Hollingsworth, Jeffrey K; Irvin, R. B; Karavanic, K. L; Kunchithapadam, K.; Newhall, T. (Computer, 1995)
Paradyn is a tool for measuring the performance of large-scale parallel programs. Our goal in designing a new performance tool was to provide detailed, flexible performance information without incurring the space (and time) overhead typically associated with trace-based tools. Paradyn achieves this goal by dynamically instrumenting the application and automatically controlling this instrumentation in search of performance problems. Dynamic instrumentation lets us defer insertion until the moment it is needed (and remove it when it is no longer needed); Paradyn's Performance Consultant decides when and where to insert instrumentation
Keywords: Aerodynamics; Automatic control; automatic instrumentation control; Debugging; dynamic instrumentation; flexible performance information; high level languages; insertion; Instruments; large-scale parallel program; Large-scale systems; measurement; Paradyn parallel performance measurement tool; Parallel machines; parallel programming; Performance Consultant; Programming profession; scalability; software performance evaluation; software tools

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

A simple randomized sieve algorithm for the closest-pair problem - Khuller, Samir; Matias,Y. (Information and Computation, 1995)
We present a linear time randomized sieve algorithm for the closest-pair problem. Thealgorithm as well as its analysis are simple. The algorithm is extended to obtain a randomized linear time approximation algorithm for the closest bichromatic pair problem.

The SVD in Image Restoration - O'Leary, Dianne P. (SVD and Signal Processing III: Algorithms, Architectures, and ApplicationsSVD and Signal Processing III: Algorithms, Architectures, and Applications, 1995)

Switching as an exit problem - Korman,C.E.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 1995)
Previously, it has been shown that Preisach type models driven by stochastic inputs can be employed to model aftereffect. In this model, the machinery of the ldquo;exit problem rdquo; is instrumental in computing the time evolutions of the expected value and the distributions of switching times. Here, for the first time, we present numerical simulation results of the aforementioned viscosity models and demonstrate that these models can be employed to compute switching times and time evolutions of the expected value of magnetization
Keywords: aftereffect; magnetic; aftereffect; stochastic; analysis; distribution; viscosity; force; fluctuations; magnetic; hysteresis; magnetic; inputs; switching; models; coercive; models; exit; Preisach; problem; expected; switching; numerical; times; type; value; magnetization; model

Techniques for performance measurement of parallel programs - Hollingsworth, Jeffrey K; Lumpp, J. E; Miller, B. P (Parallel computers: theory and practice, 1995)

Vision, Graphic Design, and Visual Display - Marcus,A.; Murch,G.M.; Baecker,R.; Small,I.; Mander,R.; Ahlberg,C.; Shneiderman, Ben (Readings in human-computer interaction: toward the year 2000, 1995)

An Atlas of Drosophila Genes: Sequences and Molecular Features - Maroni,G.; Mount, Stephen M.; Cavener,DR; Cavener,BA; Sharp,PM; Lloyd,AT; Schaeffer,SW (Journal of Heredity, 1994)

Calculation of head sensitivity function from 3-D magnetic fields - Burke,E.R.; Gomez,R.D.; Madabhushi,R.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 1994)
A head sensitivity function is calculated using 3-D magnetic fields. The 3-D magnetic fields are calculated for recorded tracks with finite widths. The magnetization in the medium is expressed in 2-D Fourier series in the plane of the film and is assumed uniform through the thickness of the film. The reproduce head is idealized. These techniques are applied to data found in the literature for very narrow tracks ( 0.5 mu;m). A surprising amount of the experimental data can be explained by the finite width of the tracks. The fine structure of the measurements can then be isolated and attributed to the particular features of the individual heads
Keywords: 3-D; fields; finite; fields; magnetic; function; magnetization; recorded; head; very; heads; magnetisation; sensitivity; magnetic; narrow; Sensitivity; series; magnetic; tracks; Fourier; tracks; reproduce; widths; head

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)

Computationally Efficient Algorithms for High-Dimensional Robust Estimators - Mount, Dave; Netanyahu,N. S (CVGIP: Graphical Models and Image Processing, 1994)
Given a set of n distinct points in d-dimensional space that are hypothesized to lie on a hyperplane, robust statistical estimators have been recently proposed for the parameters of the model that best fits these points. This paper presents efficient algorithms for computing median-based robust estimators (e.g., the Theil-Sen and repeated median (RM) estimators) in high-dimensional space. We briefly review basic computational geometry techniques that were used to achieve efficient algorithms in the 2-D case. Then generalization of these techniques to higher dimensions is introduced. Geometric observations are followed by a presentation of O(nd − 1 log n) expected time algorithms for the d-dimensional Theil-Sen and RM estimators. Both algorithms are space optimal; i.e., they require O(n) storage, for fixed d. Finally, an extension of the methodology to nonlinear domain(s) is demonstrated.

Design for manufacture in multi-enterprise partnerships: current status and future directions - Nau, Dana S.; Ball,M. O; Gupta,S.K.; Minis,I. E.; Zhang, G. (1994)
To pursue market and technology opportunities effectively, US commercial and defense industries will be relying increasingly on multi-enterprise partnerships. Horizontal partnering combines the strengths of multiple firms in product design, manufacture, after sales support and customer service, in order to launch superior products in the global market. To support effective partnering, new approaches will be needed for integrating the activities of design, planning, and production. It is important to address both the fundamental modeling of design, process planning, and production planning in ways that account for the capabilities of potential manufacturing partners, and the development of optimization procedures to address the underlying decision problems. This paper elaborates on these issues and discusses approaches for addressing them.

Dynamic algorithms for geometric spanners of small diameter: Randomized solutions - Arya,Sunil; Mount, Dave; Smid,Michiel (Computational Geometry: Theory and Applications, 1994)
Let S be a set of n points in IR d and let t ? 1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and q. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. A randomized algorithm is given for constructing a t-spanner that, with high probability, contains O(n) edges and has spanner diameter O(log n). A data structure of size O(n log d n) is given that maintains this t-spanner in O(log d n log log n) expected amortized time per insertion and deletion, in the model of random updates, as introduced by Mulmuley. Keywords: Computational geometry, proximity problems, skip lists, randomization, dynamic data structures. Preprint submitted to Els...

Dynamic program instrumentation for scalable performance tools - Hollingsworth, Jeffrey K; Miller, B. P; Cargille, J. (Scalable High-Performance Computing Conference, 1994., Proceedings of the, 1994)
Presents a new technique called `dynamic instrumentation' that provides efficient, scalable, yet detailed data collection for large-scale parallel applications. Our approach is unique because it defers inserting any instrumentation until the application is in execution. We can insert or change instrumentation at any time during execution by modifying the application's binary image. Only the instrumentation required for the currently selected analysis or visualization is inserted. As a result, our technique collects several orders of magnitude less data than traditional data collection approaches. We have implemented a prototype of our dynamic instrumentation on the CM-5, and present results for several real applications. In addition, we include recommendations to operating system designers, compiler writers, and computer architects about the features necessary to permit efficient monitoring of large-scale parallel systems
Keywords: Application software; binary image; compiler writing; Computer architecture; Computer displays; Computerized monitoring; Concurrent computing; data acquisition; data collection; data visualisation; Data visualization; dynamic program instrumentation; efficient monitoring; executing program; Instruments; large-scale parallel applications; Large-scale systems; operating system design; Operating systems; parallel programming; program analysis; program diagnostics; program visualization; Programming profession; Sampling methods; scalable performance tools; software tools

Human Emotion Recognition From Motion Using A Radial Basis Function Network Architecture - Mark,R.; Yaser,Y.; Larry,D. (University Of Maryland, 1994)

The input dependent Preisach model with stochastic input as a model for aftereffect - Korman,C.E.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 1994)
In a previous work, it has been suggested to use the Preisach model driven by stochastic inputs as a model for aftereffect. Here, we further extend this approach by employing the more accurate nonlinear input dependent Preisach model. The time evolution of the expected value of the output (magnetization) is derived in terms of the stochastic description of the input. It is shown that the mathematical machinery of the ldquo;exit problem rdquo; is instrumental for calculations of time evolutions of the expected value of the output of the nonlinear input dependent Preisach model
Keywords: aftereffect; input; aftereffect; magnetic; dependent; evolutions; magnetic; hysteresis; input; time; model; stochastic; Preisach

Interacting with virtual environments - MacDonald,L.; Vince,J.; Shneiderman, Ben (John Wiley & Sons, 1994)

Optimal parallel approximation for prefix sums and integer sorting - Goodrich,M. T; Matias,Y.; Vishkin, Uzi (Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, 1994)

P element-mediated in vivo deletion analysis of white-apricot: deletions between direct repeats are strongly favored. - Kurkulos,M.; Weinberg,J. M.; Roy,D.; Mount, Stephen M. (GeneticsGenetics, 1994)
We have isolated and characterized deletions arising within a P transposon, P[hswa], in the presence of P transposase. P[hswa] carries white-apricot (wa) sequences, including a complete copia element, under the control of an hsp70 promoter, and resembles the original wa allele in eye color phenotype. In the presence of P transposase, P[hswa] shows a high overall rate (approximately 3%) of germline mutations that result in increased eye pigmentation. Of 234 derivatives of P[hswa] with greatly increased eye pigmentation, at least 205 carried deletions within copia. Of these, 201 were precise deletions between the directly repeated 276-nucleotide copia long terminal repeats (LTRs), and four were unique deletions. High rates of transposase-induced precise deletion were observed within another P transposon carrying unrelated 599 nucleotide repeats (yeast 2 mu FLP; recombinase target sites) separated by 5.7 kb. Our observation that P element-mediated deletion formation occurs preferentially between direct repeats suggests general methods for controlling deletion formation.

A parallel-in-time method for the transient simulation of SOI devices with drain current overshoots - Tai,G.-C.; Korman,C.E.; Mayergoyz, Issak D (Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 1994)
This paper presents a new parallel-in-time algorithm for the two dimensional transient simulation of SOI devices. With this approach, simulation in both space and time domains is performed in parallel As a result, the CPU time is reduced significantly from the conventional serial-in-time method. This new approach fully exploits the inherent parallelism of the finite difference formulation of the basic semiconductor device equations and the massively parallel architecture of SIMD computers. The space domain computations are inherently parallel due to the nature of our technique of solving the finite-difference equations. Time domain parallelism is achieved by shifting the potentials from previous time points to subsequent points one-step forward along the time axis with each Gummel iteration. This algorithm employs a fixed-point iteration technique, therefore a direct solution of matrix equations is avoided. The algorithm is especially suitable for the transient simulation of SOI devices that exhibit transient drain current overshoot. Numerical experiments show that the new parallel-in-time method is up to eight times faster than the conventional serial-in-time method in SOI transient simulations. The program is coded in CM Fortran for the Connection Machine
Keywords: 2D; algorithms; semiconductor; analysis; transient; architecture; parallel-in-time; boundaries; silicon; time-domain; computations; time; computers; SOI; computing; finite; current; device; devices; drain; devices; parallel; difference; dimensional; domain; effect; engineering; equations; fixed-point; equations; space; field; Fortran; CPU; gate; iteration; iteration; SIMD; Machine; Gummel; method; semiconductor; methods; insulated; methods; metal-insulator-semiconductor; models; semiconductor-insulator; overshoots; finite-difference; Parallel; parallelism; transient; response; simulation; CM; simulation; digital; simulation; electronic; simulation; two; technique; massively; time; Connection; transistors; iterative

Query-sensitive ray shooting - Mitchell,Joseph S.B.; Mount, Dave; Suri,Subhash (Proceedings of the tenth annual symposium on Computational geometry, 1994)

QUEST—Query Environment for Science Teaching - Shneiderman, Ben; Rosenfeld, A.; Marchioni,G.; Holliday,W.; Ricart, G.; Faloutsos,С.; Dick,J. (Digital Libraries' 94, 1994)
QUery Environment for Science Teaching (QUEST) is a proposed digital library implementation consisting of a set of research projects dealing with data capture and organization, content analysis, information seeking and visual interfaces.The QUEST team includes a large number of renown technical collaborators and prominent source collaborators, as well as a significant number of contributors in the University of Maryland, the central, co-ordinating agency.A large collection of multidisciplinary materials in visual and textual formats, made accessible to us by our source collaborators, will be organized to allow integrated access by users from the science education community, that is elementary school through college level teachers. QUEST will be structured so as to provide seamless access to widespread resources on disparate subjects. We intend to provide first-rate subject analysis and representation in order to provide ready access. QUEST will be accessible nationally by means of Mosaic. We propose to provide highly sophisticated querying, browsing and information investigation facilities which will handle integrated textual and visual materials without difficulty. They will be augmented by online reference and referral services, immediately accessible by the user. QUEST will provide a comprehensive information resource for science education accessible through a dynamic, visual user interface.

Randomized and deterministic algorithms for geometric spanners of small diameter - Arya,S.; Mount, Dave; Smid,M. (Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on, 1994)
Let S be a set of n points in IRd and let t gt;1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and p. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. Randomized and deterministic algorithms are given for constructing t-spanners consisting of O(n) edges and having O(log n) diameter. Also, it is shown how to maintain the randomized t-spanner under random insertions and deletions. Previously, no results were known for spanners with low spanner diameter and for maintaining spanners under insertions and deletions
Keywords: computational geometry; deletions; deterministic algorithms; directed graph; directed graphs; geometric spanners; insertions; randomised algorithms; randomized algorithms

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

Simulation of the transient characteristics of partially- and fully-depleted SOI MOSFETs - Tai,Gwo-Chung; Korman,Can E.; Mayergoyz, Issak D (Solid-State Electronics, 1994)
We present a numerical technique which employs a local-in-time initial guess for the transient simulation of SOI MOSFETs. Specifically, the goal of this work is to compute the transient drain current which exhibits overshoot. A critical factor in such computations is the choice of the initial guess at each time point after the gate ramp. Our numerical simulations have shown that the use of the previous time point solution as an initial guess in the Gummel iterations fails to predict the decay in the drain current from its maximum overshoot value. This difficulty is circumvented when the steady-state solution is used as a local-in-time initial guess. We use the diagonally implicit Runge-Kutta method for the time domain discretization. A fixed-point iteration technique is employed for the space domain iterations. To demonstrate the usefulness of the local-in-time method, numerical results of the transient drain current for various device parameters, such as the silicon film doping, silicon film thickness and back-gate bias are presented.

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

Suppressor U1 snRNAs in Drosophila. - Lo,P. C.; Roy,D.; Mount, Stephen M. (GeneticsGenetics, 1994)
Although the role of U1 small nuclear RNAs (snRNAs) in 5' splice site recognition is well established, suppressor U1 snRNAs active in intact multicellular animals have been lacking. Here we describe suppression of a 5' splice site mutation in the Drosophila melanogaster white gene (w(DR18)) by compensatory changes in U1 snRNA. Mutation of positions -1 and +6 of the 5' splice site of the second intron (ACG|GTGACT to ACC|GTGAGC) results in the accumulation of RNA retaining this 74-nucleotide intron in both transfected cells and transgenic flies. U1-3G, a suppressor U1 snRNA which restores basepairing at position +6 of the mutant intron, increases the ratio of spliced to unspliced w(DR18) RNA up to fivefold in transfected Schneider cells and increases eye pigmentation in w(DR18) flies. U1-9G, which targets position -1, suppresses w(DR18) in transfected cells less well. U1-3G,9G has the same effect as U1-3G although it accumulates to lower levels. Suppression of w(DR18) has revealed that the U1b embryonic variant (G134 to U) is active in Schneider cells and pupal eye discs. However, the combination of 9G with 134U leads to reduced accumulation of both U1b-9G and U1b-3G,9G, possibly because nucleotides 9 and 134 both participate in a potential long-range intramolecular base-pairing interaction. High levels of functional U1-3G suppressor reduce both viability and fertility in transformed flies. These results show that, despite the difficulties inherent in stably altering splice site selection in multicellular organisms, it is possible to obtain suppressor U1 snRNAs in flies.

Trade-offs between communication throughput and parallel time - Mansour,Y.; Nisan,N.; Vishkin, Uzi (Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, 1994)

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

Algorithms for fast vector quantization - Arya,S.; Mount, Dave (Data Compression Conference, 1993. DCC '93., 1993)
This paper shows that if one is willing to relax the requirement of finding the true nearest neighbor, it is possible to achieve significant improvements in running time and at only a very small loss in the performance of the vector quantizer. The authors present three algorithms for nearest neighbor searching: standard and priority <e1>k </e1>-<e1>d</e1> tree search algorithms and a neighborhood graph search algorithm in which a directed graph is constructed for the point set and edges join neighboring points
Keywords: algorithm; algorithms; directed; fast; graph; graph; graphs; Neighborhood; performance; problems; quantisation; quantization; running; search; time; tree; vector

Approximate nearest neighbor queries in fixed dimensions - Arya,Sunil; Mount, Dave (Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, 1993)

Approximate nearest neighbor searching - Arya,S.; Mount, Dave (Proceedings of 4th Annual ACMSIAM Symposium on Discrete Algorithms (SODA’93), 1993)

Approximate parallel prefix computation and its applications - Goodrich,M. T; Matias,Y.; Vishkin, Uzi (Parallel Processing Symposium, 1993., Proceedings of Seventh International, 1993)

On the area of overlap of translated polygons - Mount, Dave; Silverman,R.; Wu,A. (SPIE Vision Geometry II, 1993)
Given two simple polygons P and Q in the plane and a translation vector t 2R2, the area-of-overlap function of P and Q is the function Ar(t) = Area(P \(t + Q)), where t + Q denotes Q translated by t. This function has a number of applications in areas such as motion planning and object recognition. We present a number of mathematical results regarding this function. We also provide e cient algorithms for computing a representation of this function, and for tracing contour curves of constant area-of-overlap.

Data parallel algorithms for the numerical modeling of semiconductor devices - Darling,James Paul (University of Maryland at College Park, 1993)

Dynamic control of performance monitoring on large scale parallel systems - Hollingsworth, Jeffrey K; Miller, Barton P. (Proceedings of the 7th international conference on Supercomputing - ICS '93, 1993)

Efficient algorithms for robust circular arc estimators - Mount, Dave; Netanyahu,N. S (Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo, Ontario, Canada, 1993)

Evaluating surface intersections in lower dimensions - Manocha,D.; Varshney, Amitabh; Weber,H. (Second International Conference on Curves and Surfaces, 1993)
We highlight a new algorithm for evaluating the sur-face intersection curve using a matrix formulation. The projection of the intersection curve is represented as the singular set of a bi- variate matrix polynomial. The resulting algorithm for evaluating the intersection curve is based on matrix computations like eigen- decomposition and singular value decomposition. Furthermore, at each stage of the algorithm we make use of inverse power iterations to march back to the curve. We also describe the performance of the resulting robust and accurate approach

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)

Finding facts vs. browsing knowledge in hypertext systems - Marchionini,G.; Shneiderman, Ben (Sparks of innovation in human-computer interaction, 1993)

Geometric knapsack problems - Arkin,E. M; Khuller, Samir; Mitchell,J. S.B (Algorithmica, 1993)
We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following ldquofence enclosurerdquo problem: given a setS ofn points in the plane with valuesv i ge 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the ldquovaluerdquo of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowingS to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of at mostM connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. We also provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.

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)

On The Maximum Number of Intersections of Two Polyhedra in 2 and 3 Dimensions - Dillencourt,M. B; Mount, Dave; Saalfeld,A.J. (Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo, Ontario, 1993)
We obtain exact bounds on the maximum number of in-tersections between two polygons with prescribed edge counts. In three dimensions, we obtain exact bounds on the number of intersecting face-pairs of two polyhe- dra with prescribed face counts when the polyhedra are convex, and lower bounds in the general case.

Messenger RNA splicing signals in Drosophila genes - Mount, Stephen M. (Atlas of Drosophila Genes, 1993)
This chapter provides a general description of introns in Drosophila genes, withemphasis on the genetic information responsible for the correct specification of boundaries between introns and exons. The problem of locating introns within unannotated DNA sequences is posed by any large genomic sequencing project, and provides a perspective for discussing the information that specifies their removal. I want to stress, however, that there may not be a single set of rules that can identify all introns in all tissues. Certainly, it has become clear that the rules for locating introns will differ between species, such as flies and humans, in different taxonomic classes. Here, I will attempt to describe in general terms both what is known about how introns are recognized by the splicing machinery, and how an investigator might go about identifying introns within the sequence of his favorite Drosophila gene. Ultimately, such searches will be carried out by computer. Most current software, however, is designed specifically or primarily for species other than Drosophila (one exception is the program GM (Fields and Soderlund 1990), which accepts organism-specific consensus matrices and codon asymmetry tables). I am currently developing computational applications of the ideas described here, and interested readers are encouraged to consult current releases of the electronic Drosophila Infor- mation Newsletter.

Multiple Resource Allocation for Multiprocessor Distributed Real-Time Systems - Mosse,Daniel; Noh,Sam H; Trinh,Bao; Agrawala, Ashok K. (In Workshop on Parallel and Distributed Real-Time Systems (PDRTS), IEEE IPPS'93, 1993)
this report are those of the author(s) and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency, ONR, the U.S. Government or Honeywell. Computer facilities were provided in part by NSF grant CCR-8811954. Workshop on Parallel and Dist Real-Time Syst, IEEE IPPS'93 April 1993 in the queue and tries to schedule it. If the task is successfully scheduled, it is removed from the queue and executed. Otherwise, the task is unlocked so that other processors may examine it in the same fashion. This scheme is convenient for a shared memory architecture, but becomes too expensive and cumbersome when such facility is not available in hardware (for example, in distributed systems). The goal of this paper is twofold: first, to study the problem of allocating multiple resources to a single task; and second, to provide a heuristic allocation policy for selecting a resource among multiple instances of identical resources. We consider a distributed system in which each site is a uniform memory access (UMA) multiprocessor, but the scheme is easily extensible to non-UMA models. For the first problem, a three-tiered resource allocation scheme is proposed. A hierarchy of the resources is defined to reduce the probability of allocation failure as the allocation progresses. To reduce the complexity of multiple resource allocation, we group the resources into schedulable sets of resources. Since the objective in real-time systems is to meet deadlines, this approach is acceptable so long as it meets a justifiable minimum level of resource utilization. It is shown that our approach allows modularity, flexibility, and potential concurrency in scheduling. Another contribution of this paper is in explicitly ide...

A new point of view on the mathematical structure of Maxwell's equations - Mayergoyz, Issak D; D'Angelo,J. (Magnetics, IEEE Transactions on, 1993)
It is emphasized that the Maxwell equations have a peculiar mathematical structure which leads to boundary value problems with an overspecified number of partial differential equations and an underspecified number of boundary conditions. An attempt is made to reduce these boundary value problems to standard mathematical formulations with equal numbers of partial differential equations and boundary conditions. It is demonstrated that these formulations have some attractive features which appreciably facilitate their finite element discretizations. A numerical example involving scattering of plane electromagnetic waves from a perfect conducting thin plate illustrates the discussion
Keywords: analysis; partial; conditions; boundary; conducting; differential; discretizations; mathematical; element; EM; equations; equations; boundary; equations; boundary-value; equations; perfect; example; partial; Maxwell's; plate; plane; problems; electromagnetic; problems; finite; scattering; finite; scattering; Maxwell; structure; numerical; thin; value; wave

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.

Potentials and limitations of pen-based computers - Citrin,Wayne; Halbert,Dan; Hewitt,Carl; Meyrowitz,Norm; Shneiderman, Ben (Proceedings of the 1993 ACM conference on Computer science, 1993)
There are four possible genres of input devices that can be attached to personal workstations; keyboard, mouse, pen, and voice. For investigating potentials and limitations of pen-based computers, we propose to compare those four categories as different types of man-machine communication channel.Even though arrow keys allow a limited scope of 2D capability in keyboard usage, the primary use of a keyboard is typing. Typing generates a linear sequence of discrete characters. The maximum speed of typing is roughly 10 characters per second, hence the bandwidth of 100 (10×10) bps. A mouse is used primarily for pointing (menu item/object selection) and then for dragging (moving and re-sizing objects). Mouse pointing generates a discrete information of a point location on a 2D (planer) plane with the maximum speed of 2 clicking per second. Each pointing may generate 20 bits of information with the bandwidth of 40 (2×20) bps. Mouse dragging generates a continuous geometric pattern in 2D. Assuming the maximum rate of 40 selections per second in the eight (3 bits) possible directions of dragging, the bandwidth of mouse dragging peaks at 120 (40×3) bps. The usage of pen on a planer flat surface of LCD unit can be divided into scribing and tapping. By scribing we mean a generation of continuous pen strokes forming a character, a gesture, or a picture. Scribing includes drawing and gesturing. Tapping corresponds to a mouse clicking. Tapping may be considered as a special kind of gesture as in the PenPoint operating system. The bandwidth of scribing can be calculated in the same manner as for mouse dragging. With the maximum rate of 100 selections of direction per second for pen, scribing may produce strokes with the speed of 300 (100×3) bps. The bandwidth of pen tapping is almost the same as that of a mouse clicking except that a selection of a point is easier by a pen (3 tappings per second) than by a mouse (2 clickings per second). Talking through a microphone generates a linear sequence of continuous speech with a high degree of redundancy. Using the CELP speech compression algorithm, the bandwidth of normal speech can be reduced to 4800 bps. By vocal signaling we mean a generation of a sequence of discrete messages each of which consists of different pitches and loudness levels. The maximum rate of signaling could be 5 messages per second with 10 differentiable pitches and 10 levels of loudness producing the bandwidth of 35 (5×7) bps. Note that mouse dragging, pen scribing, and voice talking, each produces continuous data objects. Only after quantization by sampling, the data objects can be represented by discrete data structure. By precision we mean the degree of ease in duplicating the identical information using the same input technology. Keyboard is a high precision device because there is no difficulty in generating the same character over and over again. Drawing by a mouse is more difficult than drawing by a pen, because pen is easier to control than mouse. Precision of voice is low because it is difficult to duplicate the sound of the same pitch and the same volume. By latency we mean the set-up time necessary to start generating a stream of information. The latency of using keyboard and mouse is larger than the latency of using pen and voice. By translation we mean a process of converting the information generated by the input device into a sequence of discrete symbols, i.e., a transduction of a continuous data type to a discrete data type. Translation for a keyboard is not necessary. Translation of a mouse click on a menu item requires a finite table look-up which is rather simple operation. Translation of pen scribing and mouse dragging involves a handwriting recognition algorithm which is still a difficult problem at present time. Voice recognition is a very difficult problem. With the assumption that real-time translation is feasible for handwriting recognition and speech recognition, the efficiency of input device for text entry can be measured by how many characters can be entered in a second (cps). A simulated keyboard on CRT is used for entering text by a mouse. Long handwriting on a pen computer is used for a pen. When personal workstations become down-sized, the physical dimension of an input/output device becomes a dominant factor for the mobility of workstations. Keyboard and mouse are portable but intrusive. Wireless pen is mobile and less intrusive. Voice can be ubiquitous but intrusive. One conclusion we can draw from the above analysis is that pen is mightier than mouse. A pen can replace a mouse any time any place. However, keyboard, pen, and voice have different strong points and weak points. They compensate with each other. Therefore, we predict that future workstations will carry multi-modal user-interface with any combination of keyboard, pen, and voice.

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)

Probabilistic analysis of some navigation strategies in a dynamic environment - Sharma, R.; Mount, Dave; Aloimonos, J. (Systems, Man and Cybernetics, IEEE Transactions on, 1993)

RF scattering and radiation by using a decoupled Helmholtz equation approach - D'Angelo,J.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 1993)
A novel finite-element formulation for the solution of 3-D RF scattering and radiation problems is presented. This formulation is based on the solution of a set of decoupled Helmholtz equations for the Cartesian components of the field vectors. This results in a robust, computer-efficient method that eliminates previous difficulties associated with `curl-curl' type partial differential equations. Although it is presented in the frequency domain, the method is easily extendible to the time domain
Keywords: 3D; analysis; approach; computer-efficient; computing; decoupled; domain; electrical; electromagnetic; element; engineering; equation; finite; finite-element; formulation; Frequency; frequency-domain; Helmholtz; method; Physics; problems; propagation; radiation; radiowave; RF; scattering; wave

Species-specific signals for the splicing of a short Drosophila intron in vitro. - Guo,M.; Lo,P. C.; Mount, Stephen M. (Molecular and Cellular BiologyMol. Cell. Biol., 1993)
The effects of branchpoint sequence, the pyrimidine stretch, and intron size on the splicing efficiency of the Drosophila white gene second intron were examined in nuclear extracts from Drosophila and human cells. This 74-nucleotide intron is typical of many Drosophila introns in that it lacks a significant pyrimidine stretch and is below the minimum size required for splicing in human nuclear extracts. Alteration of sequences of adjacent to the 3' splice site to create a pyrimidine stretch was necessary for splicing in human, but not Drosophila, extracts. Increasing the size of this intron with insertions between the 5' splice site and the branchpoint greatly reduced the efficiency of splicing of introns longer than 79 nucleotides in Drosophila extracts but had an opposite effect in human extracts, in which introns longer than 78 nucleotides were spliced with much greater efficiency. The white-apricot copia insertion is immediately adjacent to the branchpoint normally used in the splicing of this intron, and a copia long terminal repeat insertion prevents splicing in Drosophila, but not human, extracts. However, a consensus branchpoint does not restore the splicing of introns containing the copia long terminal repeat, and alteration of the wild-type branchpoint sequence alone does not eliminate splicing. These results demonstrate species specificity of splicing signals, particularly pyrimidine stretch and size requirements, and raise the possibility that variant mechanisms not found in mammals may operate in the splicing of small introns in Drosophila and possibly other species.

A study of file manipulation by novices using commands vs, direct manipulation - Margono,S.; Shneiderman, Ben (Sparks of innovation in human-computer interaction, 1993)

Use of lexical conceptual structure for intelligent tutoring - Dorr, Bonnie J; Hendler,J.; Blanksteen,S.; Migdalof,B. (University of Maryland, 1993)
We describe the use of an LCS-based semantics for question-answeringexercises in foreign language training. We start by reviewing the LCS model and show how this representation can be used to support a question answering lesson as well as a limited domain discourse. An authoring tool for entering the relevant semantic knowledge is also described.

Using differential technlques to efficiently support transaction time - Jensen,Christian S.; Mark,Leo; Roussopoulos, Nick; Sells,Timos (The VLDB JournalVLDB Journal, 1993)

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)

Constrained Matrix Sylvester Equations - Barlow,Jewel B.; Monahemi,Moghen M.; O'Leary, Dianne P. (SIAM Journal on Matrix Analysis and Applications, 1992)
The problem of finding matrices $L$ and $T$ satisfying $TA - FT = LC$ and $TB = 0$ is considered. Existence conditions for the solution are established and an algorithm for computing the solution is derived. Conditions under which the matrix $[C^T ,T^T ]$ is full rank are also discussed. The problem arises in control theory in the design of reduced-order observers that achieve loop transfer recovery.
Keywords: loop transfer recovery; matrix Liapunov equation; Sylvester operator

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 Design of Reduced Order Observers with Precise Loop Transfer Recovery - Monahemi,Moghen M.; Barlow,Jewel B.; O'Leary, Dianne P. (AIAA Journal of Guidance, Control, and Dynamics, 1992)

Incremental construction and dynamic maintenance of constrained Delaunay triangulations - Kao,T.C.; Mount, Dave (Proceedings of the 4th Canadian Conference on Computational Geometry, 1992)

Incrementally maintained network→relational database mapping - Mark,Leo; Roussopoulos, Nick; Newsome,Tina; Laohapipattana,Piriya (Software: Practice and Experience, 1992)
An incrementally maintained mapping from a network to a relational database is presented. This mapping may be established either to support the efficient retrieval of data from a network database through a relational interface, or as the first step in a gradual conversion of data and applications from a network to a relational database system. After the mapping has been established, the only data mapped from the network to the relational database are the increments resulting from updates on the network database. The mapping is therefore an efficient alternative to mappings that repeatedly map the results of retrievals through the relational interface from the network database to the relational database. This is in particular the case when the two databases reside on different hosts. Applications on the network database may, under certain restrictions, gradually be moved to the relational database, while the mapping incrementally maintains the relational database for the applications that remain on the network database.
Keywords: Database conversion; Database gateway; Database mapping; Incremental database mapping

Intersection detection and separators for simple polygons - Mount, Dave (Proceedings of the eighth annual symposium on Computational geometry, 1992)
A simple algorithm is presented for detecting whether two preprocessed simple polygons intersect one another. Given a simple polygon, A, in O(n log n) time and O(n) space we preprocess A constructing an enveloping triangulation called a scaffold. To determine whether two preprocessed polygons A and B overlap another, we start with these two envelopes and successively strip away overlapping triangles of the scaffolds until we either detect an intersection between the objects or until we have succeeded in separating them spatially. The running time of the intersection query depends on the complexity of the minimum link polygonal curve separating the two objects. Given two preprocessed simple polygons A and B, placed at arbitrary locations in the plane we can determine whether these polygons intersect one another in O(m log2n is the total number of vertices and m is the complexity of a minimum link polygonal curve separating A from B. We generalize this to the problem of computing arbitrary Boolean functions of two preprocessed polygons.

A parallel algorithm for enclosed and enclosing triangles - Chandran,S.; Mount, Dave (International Journal of Computational Geometry and Applications, 1992)
We consider the problems of computing the largest area triangle enclosed within a given n-sided convex polygon and the smallest area triangle which encloses a given convex polygon. We show that these problems are closely related by presenting a single sequential linear time algorithm which essentially solves both problems simultaneously. We also present a cost-optimal parallel algorithm that solves both of these problems in O(log log n) time using n/log log n processors on a CRCW PRAM. In order to achieve these bounds we develop new techniques for the design of parallel algorithms for computational problems involving the rotating calipers method.

Parallel computational geometry of rectangles - Chandran,S.; Kim,S. K; Mount, Dave (Algorithmica, 1992)
Rectangles in a plane provide a very useful abstraction for a number of problems in diverse fields. In this paper we consider the problem of computing geometric properties of a set of rectangles in the plane. We give parallel algorithms for a number of problems usingn processors wheren is the number of upright rectangles. Specifically, we present algorithms for computing the area, perimeter, eccentricity, and moment of inertia of the region covered by the rectangles inO(logn) time. We also present algorithms for computing the maximum clique and connected components of the rectangles inO(logn) time. Finally, we give algorithms for finding the entire contour of the rectangles and the medial axis representation of a givenn × n binary image inO(n) time. Our results are faster than previous results and optimal (to within a constant factor).

Parallel program performance metrics: a comprison and validation - Hollingsworth, Jeffrey K; Miller, B. P (Proceedings of the 1992 ACM/IEEE conference on Supercomputing, 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.

On the Precise Loop Transfer Recovery and Transmission Zeroes - Monahemi,M.; Barlow,J.; O'Leary, Dianne P. (First IEEE Conference on Control ApplicationsFirst IEEE Conference on Control Applications, 1992)

Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph - Khuller, Samir; Mitchell,S. G; Vazirani,V. V (SIAM Journal on Computing, 1992)

A randomized algorithm for slope selection - Dillencourt,M. B; Mount, Dave; Netanyahu,N. S (International Journal of Computational Geometry and Applications, 1992)

Randomized range-maxima in nearly-constant parallel time - Berkman,O.; Matias,Y.; Vishkin, Uzi (Computational Complexity, 1992)

Splicing signals in Drosophila: intron size, information content, and consensus sequences - Mount, Stephen M.; Burks,Christian; Herts,Gerald; Stormo,Gary D.; White,Owen; Fields,Chris (Nucleic Acids ResearchNucl. Acids Res., 1992)
A database of 209 Drosophila Introns was extracted from Genbank (release number 64.0) and examined by a number of methods in order to characterize features that might serve as signals for messenger RNA splicing. A tight distribution of sizes was observed: while the smallest introns in the database are 51 nucleotides, more than half are less than 80 nucleotides in length, and most of these have lengths in the range of 59 – 67 nucleotides. Drosophila splice sites found in large and small introns differ in only minor ways from each other and from those found in vertebrate Introns. However, larger introns have greater pyrimidlne-richness in the region between 11 and 21 nucleotides upstream of 3′ splice sites. The Drosophila branchpoint consensus matrix resembles C T A A T (in which branch formation occurs at the underlined A), and differs from the corresponding mammalian signal in the absence of G at the position immediately preceding the branchpoint. The distribution of occurrences of this sequence suggests a minimum distance between 5′ splice shies and branchpoints of about 38 nucleotides, and a minimum distance between 3′ splice sites and branchpoints of 15 nucleotides. The methods we have used detect no information in exon sequences other than in the few nucleotides immediately adjacent to the splice sites. However, Drosophila resembles many other species in that there is a discontinuity in A + T content between exons and introns, which are A + T rich.

Combinatorial and computational aspects of Minkowski decompositions - Mount, Dave; Silverman,R. (Contemporary Mathematics, 1991)

Computing generalized Voronoi diagrams in improved time and space bounds - Kao,Thomas C.; Mount, Dave (University of Maryland at College Park, 1991)

Considerations on Loop Transfer Recovery for Non-minimum Phase Plants - Monahemi,M.; Barlow,J.; O'Leary, Dianne P. (Proceedings of the AIAA Aircraft Design Systems and Operations MeetingProceedings of the AIAA Aircraft Design Systems and Operations Meeting, 1991)

Converting high probability into nearly-constant time—with applications to parallel hashing - Matias,Y.; Vishkin, Uzi (Proceedings of the twenty-third annual ACM symposium on Theory of computing, 1991)

Data parallel algorithms for the numerical modeling of semiconductor devices - Darling,J. P.; Mayergoyz, Issak D (Proceedings of the 5th SIAM Conference on Parallel Processing for Scientific Computing, 1991)

Demonstrational interfaces: Coming soon? - Myers,Brad A.; Cypher,Allen; Maulsby,David; Smith,David C.; Shneiderman, Ben (Proceedings of the SIGCHI conference on Human factors in computing systems: Reaching through technology, 1991)

The densest double-lattice packing of a convex polygon - Mount, Dave (Discrete and Computational Geometry: Papers from the DIMACS Special Year, 1991)

The Design of Reduced Order Luenberger Observers with Precise LTR - Monahemi,M.; Barlow,J.; O'Leary, Dianne P. (Proceedings of the AIAA Meeting on Guidance, Navigation and ControlProceedings of the AIAA Meeting on Guidance, Navigation and Control, 1991)
This work concerns the design of reduced-order observers for controllable, observable, and regular systems in which the number of measurements is more than the number of controls. It uses eigenstructure assignment whereas other approaches use Kalman filter (LQG/LTR) methods. The advantages of this approach are: (1) precise LTR rather than approximate LTR, (2) no restriction to minimum phase systems, (3) finite observer gain rather than asymptotic observer gain, and (4) simpler and more efficient numerical calculation. Case studies are presented illustrating these features in aircraft control applications.

On finding the minimum bandwidth of interval graphs - Mahesh,R.; Rangan,C.Pandu; Srinivasan, Aravind (Information and Computation, 1991)
Let G = (V, E) be an interval graph, with |V| = n, and |E| = m. An O(n2 log n) algorithm was proposed in Kratsch (Inform Comput. 74, 140–158 (1987)) to find the bandwidth of G. We show that this algorithm is wrong, and provide a corrected version of the same. Also, it was observed in [4] that the bandwidth of a proper interval graph can be computed in O(n log n + m) time. We show how this idea can be modified slightly to yield an O(n = m) algorithm.

Incremental implementation model for relational databases with transaction time - Jensen,C. S; Mark,L.; Roussopoulos, Nick (IEEE Transactions on Knowledge and Data Engineering, 1991)
An implementation model for the standard relational data model extended with transaction time is presented. The implementation model integrates techniques of view materialization, differential computation, and deferred update into a coherent whole. It is capable of storing any view (reflecting past or present states) and subsequently using stored views as outsets for incremental and decremental computations of requested views, making it more flexible than previously proposed partitioned storage models. The working and the expressiveness of the model are demonstrated by sample queries that show how historical data are retrieved
Keywords: Computational modeling; Computer science; Data models; data retrieval; Database languages; Database systems; database theory; decremental computations; deferred update; Degradation; differential computation; historical data; History; incremental computations; Information retrieval; partitioned storage models; queries; relational data model; Relational databases; stored views; Transaction databases; transaction time; view materialization

The integration of application and system based metrics in a parallel program performance tool - Hollingsworth, Jeffrey K; Irvin, R. B; Miller, B. P (ACM Sigplan Notices, 1991)

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

On parallel hashing and integer sorting - Matias,Y.; Vishkin, Uzi (Journal of Algorithms, 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.

Pyramid computation of neighbor distance statistics in dot patterns - Banerjee,Saibal; Mount, Dave; Rosenfeld,Azriel (CVGIP: Graphical Models and Image Processing, 1991)
This paper describes an algorithm for computing statistics of Voronoi neighbor distances in a dot pattern, using a cellular pyramid computer, in a logarithmic number of computational steps. Given a set of dots in a square region of the digital plane, the algorithm determines with high probability the Voronoi neighbors of the dots in the interior of the region and then computes statistics of the neighbor distances. An algorithm of this type may account for the ability of humans to perceive at a glance whether the dots in a pattern are randomly or regularly spaced, i.e., their neighbor distances have high or low variance.

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

Towards a theory of nearly constant time parallel algorithms - Gil,J.; Matias,Y.; Vishkin, Uzi (Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on, 1991)
It is demonstrated that randomization is an extremely powerful tool for designing very fast and efficient parallel algorithms. Specifically, a running time of <e1>O</e1>(lg* <e1>n</e1>) (nearly-constant), with high probability, is achieved using <e1>n</e1>/lg* <e1>n</e1> (optimal speedup) processors for a wide range of fundamental problems. Also given is a constant time algorithm which, using <e1>n</e1> processors, approximates the sum of <e1>n</e1> positive numbers to within an error which is smaller than the sum by an order of magnitude. A variety of known and new techniques are used. New techniques, which are of independent interest, include estimation of the size of a set in constant time for several settings, and ways for deriving superfast optimal algorithms from superfast nonoptimal ones
Keywords: computational complexity; Estimation; nearly constant time parallel algorithms; Parallel algorithms; positive numbers; randomization; running time; superfast optimal algorithms

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)

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.

Competitive learning using competitive activation rules - Sutton III,G. G.; Reggia, James A.; Maisog,J. M (Neural Networks, 1990., 1990 IJCNN International Joint Conference on, 1990)

Drosophila melanogaster genes for U1 snRNA variants and their expression during development - Lo,Partick C. H.; Mount, Stephen M. (Nucleic Acids ResearchNucl. Acids Res., 1990)
We have cloned and characterized a complete set of seven U1-related sequences from Drosophila melanogaster. These sequences are located at the three cytogenetic loci 21D, 82E, and 95C. Three of these sequences have been previously studied: one U1 gene at 21D which encodes the prototype U1 sequence (U1a), one U1 gene at 82E which encodes a U1 variant with a single nucleotide substitution (1Mb), and a pseudogene at 82E. The four previously uncharacterized genes are another U1b gene at 82E, two additional U1 a genes at 95C, and a U1 gene at 95C which encodes a new variant (U1c) with a distinct single nucleotide change relative to U1a. Three blocks of 5′ flanking sequence similarity are common to all six full length genes. Using specific primer extension assays, we have observed that the 1Mb RNA is expressed in Drosophila Kc cells and is associated with snRNP proteins, suggesting that the U1b-contalning snRNP particles are able to participate in the process of premRNA splicing. We have also examined the expression throughout Drosophila development of the two U1 variants relative to the prototype sequence. The U1c variant is undetectable by our methods, while the U1b variant exhibits a primarily embryonic pattern reminiscent of the expression of certain U1 variants in sea urchin, Xenopus, and mouse.

EVALUATING HYPERMEDIA SYSTEMS - Ehrlich,K.; Microsytems,S.; Marchionini,G.; Nielsen,J.; Shneiderman, Ben (Human factors in computing systems: CHI'90 Conference proceedings, April 1-5, Seattle, 1990)

Information interchange between self-describing databases - Mark,Leo; Roussopoulos, Nick (Information Systems, 1990)
Within the framework of a self-describing database system we describe a set of data management tools and a data dictionary supporting information interchange. The concepts are based on our experience from a project on standardized information interchange in NASA.

Interoperability of multiple autonomous databases - Litwin,Witold; Mark,Leo; Roussopoulos, Nick (ACM Computing SurveysACM Comput. Surv., 1990)

Investigation of the threshold voltage of MOSFETs with position and potential-dependent interface trap distributions using a fixed-point iteration method - Gaitan,M.; Mayergoyz, Issak D; Korman,C.E. (Electron Devices, IEEE Transactions on, 1990)
Simulation results are presented for a MOSFET with position- and energy- (potential-) dependent interface trap distributions that may be typical for devices subjected to interface-trap-producing processes such as hot-electron degradation. The interface-trap distribution is modeled as a Gaussian peak at a given position along the channel, and the energy dependence is derived from <e1>C</e1>-<e1>V</e1> measurements from an MOS capacitor exposed to ionizing radiation. A novel fixed-point technique is used to solve the two-dimensional boundary-value problem. The technique is shown to be globally convergent for arbitrary distributions of interface traps. A comparison of the convergence properties of the Newton and fixed-point methods is presented, and it is shown that for some important cases the Newton technique fails to converge while the fixed-point technique converges with a geometric convergence rate
Keywords: boundary-value; C-V; carriers; insulated; characteristics; Gaussian; Convergence; convergence; hot-electron; degradation; position; dependence; fixed-point; dependent; device; distribution; potential-dependent; distributions; simulation; threshold; effect; electron; field; gate; interface; iteration; method; fixed-point; methods; hot; methods; semiconductor; models; numerical; of; peak; MOSFET; energy; problem; boundary-value; problems; convergence; rate; global; states; iterative; technique; geometric; transistors; interface; trap; voltage; two-dimensional

IPS-2: the second generation of a parallel program measurement system - Miller, B. P; Clark, M.; Hollingsworth, Jeffrey K; Kierstead, S.; Lim,S. -S; Torzewski, T. (IEEE Transactions on Parallel and Distributed Systems, 1990)
IPS, a performance measurement system for parallel and distributed programs, is currently running on its second implementation. IPS's model of parallel programs uses knowledge about the semantics of a program's structure to provide two important features. First, IPS provides a large amount of performance data about the execution of a parallel program, and this information is organized so that access to it is easy and intuitive. Secondly, IPS provides performance analysis techniques that help to guide the programmer automatically to the location of program bottlenecks. The first implementation of IPS was a testbed for the basic design concepts, providing experience with a hierarchical program and measurement model, interactive program analysis, and automatic guidance techniques. It was built on the Charlotte distributed operating system. The second implementation, IPS-2, extends the basic system with new instrumentation techniques, an interactive and graphical user interface, and new automatic guidance analysis techniques. This implementation runs on 4.3BSD UNIX systems, on the VAX, DECstation, Sun 4, and Sequent Symmetry multiprocessor
Keywords: 4.3BSD UNIX systems; automatic guidance techniques; Automatic testing; Charlotte distributed operating system; CPA; DECstation; design concepts; distributed programs; graphical user interface; Graphical user interfaces; Instruments; interactive program analysis; IPS-2; measurement; message systems; network operating systems; Operating systems; parallel program measurement system; parallel programming; parallel programs; Performance analysis; performance analysis techniques; performance evaluation; performance measurement system; Power system modeling; program bottlenecks; program diagnostics; Programming profession; semantics; Sequent Symmetry multiprocessor; shared-memory systems; software tools; Springs; Sun; Sun 4; Unix; VAX

The number of shortest paths on the surface of a polyhedron - Mount, Dave (SIAM Journal on Computing, 1990)

On-line algorithms for weighted matching and stable marriages - Khuller, Samir; Mitchell,S. G; Vazirani,V. V (Cornell University, 1990)
We give an on-line deterministic algorithm for the bipartite weighted matching problem that achieves a competitive ratio of $O(n)$. In fact, this algorithm is almost optimal - the lower bound on the performance ratio of any deterministic online algorithm is $Ω (n/ \sqrt{log n})$. We also study the stable marriage problem, where we are interested in the number of unstable pairs produced. We show that the simple "first come, first served" deterministic algorithm yields on the average $O(n$ log $n$) unstable pairs, but in the worst case no deterministic or randomized on-line algorithm can do better that $Ω(n^{2})$ unstable pairs.

Packing and covering the plane with translates of a convex polygon - Mount, Dave; Silverman,Ruth (Journal of Algorithms, 1990)
A covering of the Euclidean plane by a polygon P is a system of translated copies of P whose union is the plane, and a packing of P in the plane is a system of translated copies of P whose interiors are disjoint. A lattice covering is a covering in which the translates are defined by the points of a lattice, and a lattice packing is defined similarly. We show that, given a convex polygon P with n vertices, the densest lattice packing of P in the plane can be found in O(n) time. We also show that the sparsest lattice covering of the plane by a centrally symmetric convex polygon can be solved in O(n) time. Our approach utilizes results from classical geometry that reduce these packing and covering problems to the problems of finding certain extremal enclosed figures within the polygon.

Parallel algorithm for the solution of nonlinear poisson equation of semiconductor device theory and its implementation on the IVIPP - Darling,J. P.; Mayergoyz, Issak D (Journal of Parallel and Distributed Computing, 1990)
The solution of the nonlinear Poisson equation of semiconductor device theory is important for the design of submicron devices used in VLSI circuits. The conventional technique applied for the solution of this equation is based on the application of Newton's method to simultaneous discretized equations. This technique requires large computational and storage capacities to handle the fine meshes associated with the modeling of submicron semiconductor devices. A new algorithm for the numerical solution of this equation has recently been developed. One advantage that this algorithm has over conventional techniques is that it is inherently parallel, and is thus well suited to implementation on a computer with large parallelism. This paper describes the initial implementation and testing of this algorithm on NASA's Massively Parallel Processor (MPP).

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

Structure and expression of the Drosophila melanogaster gene for the U1 small nuclear ribonucleoprotein particle 70K protein. - Mancebo,R.; Lo,P. C.; Mount, Stephen M. (Molecular and Cellular BiologyMol. Cell. Biol., 1990)
A genomic clone encoding the Drosophila U1 small nuclear ribonucleoprotein particle 70K protein was isolated by hybridization with a human U1 small nuclear ribonucleoprotein particle 70K protein cDNA. Southern blot and in situ hybridizations showed that this U1 70K gene is unique in the Drosophila genome, residing at cytological position 27D1,2. Polyadenylated transcripts of 1.9 and 3.1 kilobases were observed. While the 1.9-kilobase mRNA is always more abundant, the ratio of these two transcripts is developmentally regulated. Analysis of cDNA and genomic sequences indicated that these two RNAs encode an identical protein with a predicted molecular weight of 52,879. Comparison of the U1 70K proteins predicted from Drosophila, human, and Xenopus cDNAs revealed 68% amino acid identity in the most amino-terminal 214 amino acids, which include a sequence motif common to many proteins which bind RNA. The carboxy-terminal half is less well conserved but is highly charged and contains distinctive arginine-rich regions in all three species. These arginine-rich regions contain stretches of arginine-serine dipeptides like those found in transformer, transformer-2, and suppressor-of-white-apricot proteins, all of which have been identified as regulators of mRNA splicing in Drosophila melanogaster.

Supervised and reinforced competitive learning - Sutton III,G. G.; Reggia, James A.; Maisog,J. M (Neural Networks, 1990., 1990 IJCNN International Joint Conference on, 1990)

On a triangle counting problem - Khuller, Samir; Mitchell,Joseph S.B. (Information Processing Letters, 1990)
We consider the following problem: given a set S of n points in the plane, we would like to compute for each point pϵS, how many triangles with corners at points in set S contain p. We give an O(n2) algorithm to solve the problem.
Keywords: combinatorics; computational geometry; Range query

Dynamic versus static menus: an exploratory comparison - Mitchell,J.; Shneiderman, Ben (ACM SIGCHI Bulletin, 1989)
Sixty-three subjects completed 24 tasks using a menu driven computer program. The menu items appeared in a fixed (static) order during 12 of the tasks. During the other 12 tasks the menu item order changed dynamically such that the most frequently selected items always appeared at the top of the menu. All the subjects tried both dynamic and static menus.The subjects that used adaptive dynamic menus for the first set of tasks were significantly slower than those who used static menus on the first set of tasks. Subjects' performance during the second set of tasks was not affected by menu style. Eighty-one percent of the subjects preferred working with static menus to working with dynamic menus.

A numerical analysis for the small-signal response of the MOS capacitor - Gaitan,Michael; Mayergoyz, Issak D (Solid-State Electronics, 1989)
Simulation results for the small-signal sinusoidal steady-state response of the MOS capacitor using time perturbation analysis of the basic semiconductor equations are presented. The effects of interface and bulk trap dynamics are included. The model uses Fermi-Dirac statistics and Shockley-Read-Hall recombination to describe the traps. This analysis is an improvement over previous techniques since it can simulate the effect of trap dynamics on the small-signal sinusoidal steady-state response of a semiconductor device with arbitrary geometry, doping and trap distributions.

Competitive dynamics in a dual-route connectionist model of print-to-sound transformation - Reggia, James A.; Marsland,P. M; Berndt,R. S (Complex Systems, 1988)

The decomposition of a rectangle into rectangles of minimal perimeter - Kong,T.Y; Mount, Dave; Roscoe,AW (SIAM Journal on Computing, 1988)
This paper solves the problem of subdividing a unit square into p rectangles of area 1/p in such a way that the maximal perimeter of a rectangle is as small as possible. The correctness of the solution is proved using the well-known theorems of Menger and Dilworth.

Expert database systems: Efficient support for engineering environments - Sellis,T.; Roussopoulos, Nick; Mark,L.; Faloutsos,C. (Data & Knowledge Engineering, 1988)
Manufacturing and Engineering processes use both large scale data and knowledge bases, and the use of expert systems in such environments has become a necessity. Expert Database Systems have evolved from conventional database systems to meet the requirements of current Artificial Intelligence applications. However, future Expert Database Systems will contain knowledge bases of significant size which makes main memory insufficient and the use of a database system a necessity. We propose an effective way of building High Performance Expert Database Systems to support manufacturing and engineering environments. These systems are based on Incremental Computation Models; such models utilize results of previous computations by merging them with newly derived results of computations on small increments representing changes in the database. Our system will be able to support very large knowledge bases by utilizing novel structures and access methods and by using a very sophisticated inference engine based on incremental computation models.
Keywords: engineering databases; Expert database systems; high performance systems; incremental computation models

On finding a minimum dominating set in a tournament - Megiddo,N.; Vishkin, Uzi (Theoretical Computer Science, 1988)

Finding facts vs. browsing knowledge in hypertext systems - Marchionini,G.; Shneiderman, Ben (Computer, 1988)
The authors discuss the role of information retrieval, interface design, and cognitive science in hypertext research. They present a user-centered framework for information-seeking that has been used in evaluating two hypertext systems. They apply the framework to key design issues related to information retrieval in hypertext systems.<>
Keywords: browsing knowledge; Cognitive science; cognitive systems; Electronic publishing; hypertext research; hypertext systems; Information retrieval; information retrieval systems; information-seeking; interface design; User interfaces; word processing

Globally-Equiangular triangulations of co-circular points in 0(n log n) time - Mount, Dave; Saalfeld,A. (Proceedings of the fourth annual symposium on Computational geometry, 1988)

Partial Revertants of the Transposable Element-Associated Suppressible Allele White-Apricot in Drosophila Melanogaster: Structures and Responsiveness to Genetic Modifiers - Mount, Stephen M.; Green,M. M.; Rubin,G. M. (GeneticsGenetics, 1988)
The eye color phenotype of white-apricot (w(a)), a mutant allele of the white locus caused by the insertion of the transposable element copia into a small intron, is suppressed by the extragenic suppressor suppressor-of-white-apricot (su(w(a))) and enhanced by the extragenic enhancers suppressor-of-forked su(f)) and Enhancer-of-white-apricot (E(w(a))). Derivatives of w(a) have been analyzed molecularly and genetically in order to correlate the structure of these derivatives with their response to modifiers. Derivatives in which the copia element is replaced precisely by a solo long terminal repeat (sLTR) were generated in vitro and returned to the germline by P-element mediated transformation; flies carrying this allele within a P transposon show a nearly wild-type phenotype and no response to either su(f) or su(w(a)). In addition, eleven partial phenotypic revertants of w(a) were analyzed. Of these, one appears to be a duplication of a large region which includes w(a), three are new alleles of su(w(a)), two are sLTR derivatives whose properties confirm results obtained using transformation, and five are secondary insertions into the copia element within w(a). One of these, w(aR84h), differs from w(a) by the insertion of the most 3' 83 nucleotides of the I factor. The five insertion derivatives show a variety of phenotypes and modes of interaction with su((f) and su(w(a)). The eye pigmentation of w(aR84h) is affected by su(f) and E(w(a)), but not su(w(a)). These results demonstrate that copia (as opposed to the interruption of white sequences) is essential for the w(a) phenotype and its response to genetic modifiers, and that there are multiple mechanisms for the alteration of the w(a) phenotype by modifiers.

A united approach to finding enclosing and enclosed triangles - Mount, Dave; Chandran,S. (Proceedings of 26th Allerton Conference on Communication, Control and Computing, 1988)