Slipped-strand mispairing in a plastid gene: ıt rpoC2 in grasses (Poaceae) - Cummings, Michael P.; King,L. M; Kellogg,E. A (Mol Biol Evol, 1994)
An exception to the generally conservative nature of plastid gene evolution is the gene coding for the beta" subunit of RNA polymerase, rpoC2. Previous work by others has shown that maize and rice have an insertion in the coding region of rpoC2, relative to spinach and tobacco. To assess the distribution of this extra coding sequence, we surveyed a broad phylogenetic sample comprising 55 species from 17 angiosperm families by using Southern hybridization. The extra coding sequence is restricted to the grasses (Poaceae). DNA sequence analysis of 11 species from all five subfamilies within the grass family demonstrates that the extra sequence in the coding region of rpoC2 is a repetitive array that exhibits more than a twofold increase in nucleotide substitution, as well as a large number of insertion/deletion events, relative to the adjacent flanking sequences. The structure of the array suggests that slipped-strand mispairing causes the repeated motifs and adds to the mechanisms through which the coding sequence of plastid genes are known to evolve. Phylogenetic analyses based on the sequence data from grass species support several relationships previously suggested by morphological work, but they are ambiguous about broad relationships within the family.

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

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

Transforming queries from a relational schema to an object schema: A prototype based on F-logic - Chang,Yahui; Raschid, Louiqa; Dorr, Bonnie J (Methodologies for Intelligent SystemsMethodologies for Intelligent Systems, 1994)

Transmission patterns of eukaryotic transposable elements - arguments for and against horizontal transfer - Cummings, Michael P. (Trends Ecol Evol, 1994)
Recent studies have demonstrated that several classes of transposable elements are widely distributed within eukaryotes. Horizontal transmission of these transposable elements has often been invoked in order to explain the observed variation and relationships within and between species. These same patterns of variation and relationships, however, may originate from processes that do not involve the lateral transfer of genetic material across species.

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

Verifying an intelligent structural control system: a case study - Elseaidy,W. M; Cleaveland, Rance; Baugh,J. W. (Real-Time Systems Symposium, 1994., Proceedings., 1994)
Describes the formal verification of the timing properties of the design of an intelligent structural control system using the Concurrency Workbench, an automatic verification tool for finite-state processes. The high-level design of the system is first given in Modechart, a graphical specification language for real-time systems, and then translated into a temporal process algebra supported by the Workbench. The facilities provided by this tool are then used to analyze the system and ultimately show it to be correct
Keywords: automatic verification tool; case study; Concurrency Workbench; Distributed computing; Distributed control; distributed processing; finite automata; finite-state processes; formal verification; graphical specification language; high-level design; intelligent control; intelligent structural control system verification; Logic; Modechart; Process algebra; Real time systems; real-time systems; Specification languages; structural engineering computing; temporal logic; temporal process algebra; time-varying systems; Timing; timing properties; visual languages

Visualization in the information highway - Gershon,Nahum; Card,Stuart K.; Roth,Steven F.; Shneiderman, Ben (Proceedings of the conference on Visualization '94, 1994)

Analyzing concurrent systems using the Concurrency Workbench - Cleaveland, Rance (Functional Programming, Concurrency, Simulation and Automated Reasoning, 1993)

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

Costs of Solving the Discrete Convection-diffusion Equation by Relaxation Methods - Chernesky, M. P; Elman, Howard (University of Maryland, 1993)

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

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

A generalized approach to real-time schedulability analysis - Fredette,A. N; Cleaveland, Rance (IEEE Real-Time Systems Newsletter, 1993)

Interoperable query processing with multiple heterogeneous knowledge servers - Raschid, Louiqa; Chang,Yahui; Dorr, Bonnie J (Proceedings of the second international conference on Information and knowledge management, 1993)

Investigating touchscreen typing: the effect of keyboard size on typing speed - Sears,Andrew; REVIS,DOREEN; SWATSKI,JANET; CRITTENDEN,ROB; Shneiderman, Ben (Behaviour & Information Technology, 1993)
Abstract Two studies investigated the effect keyboard size has on typing speed and error rates for touchscreen keyboards using the lift-off strategy. A cursor appeared when users touched the screen and a key was selected when they lifted their finger from the screen. Four keyboard sizes were investigated ranging from 24.6 cm to 6.8 cm wide. Results indicate that novices can type approximately 10 words per minute (WPM) on the smallest keyboard and 20 WPM on the largest. Experienced users improved to 21 WPM on the smallest keyboard and 32 WPM on the largest. These results indicate that, although slower, small touchscreen keyboards can be used for limited data entry when the presence of a regular keyboard is not practical. Applications include portable pocket-sized or palmtop computers, messaging systems, and personal information resources. Results also suggest the increased importance of experience on these smaller keyboards. Research directions are suggested.Abstract Two studies investigated the effect keyboard size has on typing speed and error rates for touchscreen keyboards using the lift-off strategy. A cursor appeared when users touched the screen and a key was selected when they lifted their finger from the screen. Four keyboard sizes were investigated ranging from 24.6 cm to 6.8 cm wide. Results indicate that novices can type approximately 10 words per minute (WPM) on the smallest keyboard and 20 WPM on the largest. Experienced users improved to 21 WPM on the smallest keyboard and 32 WPM on the largest. These results indicate that, although slower, small touchscreen keyboards can be used for limited data entry when the presence of a regular keyboard is not practical. Applications include portable pocket-sized or palmtop computers, messaging systems, and personal information resources. Results also suggest the increased importance of experience on these smaller keyboards. Research directions are suggested.

Learning competition and cooperation - Cho,S.; Reggia, James A. (Neural computation, 1993)

A linear-time model-checking algorithm for the alternation-free modal mu-calculus - Cleaveland, Rance; Steffen,B. (Formal methods in system design, 1993)

Multiple disorder diagnosis with adaptive competitive neural networks - Cho,S.; Reggia, James A. (Artificial intelligence in medicine, 1993)

An operational semantics of value passing - Cleaveland, Rance (Proceedings 2nd North American Process Algebra Workshop, Ithaca, New York, 1993)

Ordering Effects on Relaxation Methods Applied to the Discrete One- Dimensional Convection-Diffusion Equation - Elman, Howard; Chernesky, Michael P. (SIAM Journal on Numerical Analysis, 1993)
The authors present an analysis of relaxation methods for the one-dimensional discrete convection-diffusion equation based on norms of the iteration matrices. In contrast to standard analytic techniques that use spectral radii, these results show how the performance of iterative solvers is affected by directions of flow associated with the underlying operator, and by orderings of the discrete grid points. In particular, for problems of size n, relaxation against the flow incurs a latency of approximately n steps in which convergence is slow, and red-black relaxation incurs a latency of approximately n/2 steps. There is no latency associated with relaxation that follows that flow. These results are largely independent of the choice of discretization.

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.

Query mapping and transformation techniques for problem solving with multiple knowledge servers - Raschid, Louiqa; Chang,Y.; Dorr, Bonnie J (Proceedings of the Second International Conference on Information and Knowledge Management (CIKM-93), 1993)
This paper describes a technique for infor-mation mediation when multiple heterogeneous knowl- edge and data servers are to be accessed during query processing. One problem is building an intelligent in- terface between each knowledge server (KS) and its processor (KP); and the second is to provide interoper- ability among multiple KP/KS so that a query may be answered using information from multiple sources. We present example scenarios which highlight these prob- lems and then outline query mapping and transforma- tion techniques that are applicable. The techniques for solving the interoperability problems involve rep- resentations in some canonical form. This includes a canonical representation (CR) corresponding to each KP/KS pair and a merged CR (MCR) to represent the mapping among the CRs. The MCR and CRs include relevant information obtained from a source query, and heterogeneous mapping (het-map) information, for all possible mappings among the multiple servers. The knowledge in the canonical form must be represented so that it can be easily accessed during query transfor- mation. We use an example of translating queries from an object schema to a relational schema to illustrate typical knowledge that must be represented in some canonical form. We use a high level logical language, F-logic, to represent the heterogeneous mapping (het- map) and query transformation information as a set of declarative rules, in the canonical form.

RTSL: a language for real-time schedulability analysis - Fredette,A. N; Cleaveland, Rance (Real-Time Systems Symposium, 1993., Proceedings., 1993)
The paper develops a generalized approach to schedulability analysis that is mathematically founded in a process algebra called RTSL. Within RTSL one may describe the functional behavior, timing behavior, timing constraints (or deadlines), and scheduling discipline for real-time systems. The formal semantics of RTSL then allows the reachable state space of finite state systems to be automatically generated and searched for timing exceptions. We provide a generalized schedulability analysis technique to perform this state-based analysis
Keywords: Algebra; Algorithm design and analysis; Dynamic scheduling; Failure analysis; finite state machines; finite state systems; formal logic; formal semantics; functional behavior; generalized approach; generalized schedulability analysis technique; Process algebra; Processor scheduling; reachable state space; Real time systems; real-time schedulability analysis; Real-Time Specification Language; real-time systems; RTSL; scheduling; Scheduling algorithm; scheduling discipline; Specification languages; state-based analysis; State-space methods; Time factors; Timing; timing behavior; timing constraints; timing exceptions

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

User interface consistency: an evaluation of original and revised interfaces for a videodisk library - Chimera,R.; Shneiderman, Ben (Sparks of innovation in human-computer interaction, 1993)

An application of decision theory for the evaluation of software prototypes - Cárdenas,S. R; Tian,J.; Zelkowitz, Marvin V (Journal of Systems and Software, 1992)

Computing diagnostic tests for incorrect processes - Celikkan,U.; Cleaveland, Rance (Proc. IFIP WG6. 1 12th Intl. Symp. on Protocol Specification, Testing, and Verification, 1992)

copia-like retrotransposons are ubiquitous among plants - Voytas,D. F; Cummings, Michael P.; Koniczny,A.; Ausubel,F. M; Rodermel,S. R (Proc Natl Acad Sci USA, 1992)
Transposable genetic elements are assumed to be a feature of all eukaryotic genomes. Their identification, however, has largely been haphazard, limited principally to organisms subjected to molecular or genetic scrutiny. We assessed the phylogenetic distribution of copia-like retrotransposons, a class of transposable element that proliferates by reverse transcription, using a polymerase chain reaction assay designed to detect copia-like element reverse transcriptase sequences. copia-like retrotransposons were identified in 64 plant species as well as the photosynthetic protist Volvox carteri. The plant species included representatives from 9 of 10 plant divisions, including bryophytes, lycopods, ferns, gymnosperms, and angiosperms. DNA sequence analysis of 29 cloned PCR products and of a maize retrotransposon cDNA confirmed the identity of these sequences as copia-like reverse transcriptase sequences, thereby demonstrating that this class of retrotransposons is a ubiquitous component of plant genomes.

Copia-like retrotransposons in plants: a brief introduction - Cummings, Michael P. (The Plant Genetics Newsletter, 1992)

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

Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs - Chandrasekharan,N.; Hannenhalli, Sridhar (, Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92, 1992)
The authors present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Their algorithm for computing the matching polynomial generalizes an existing result from Lovasz, Plummer (1986) and the chromatic polynomial algorithm improves the result given by Hunt, Ravi, Stearn (1988) from O(n4) time
Keywords: chromatic polynomials; computational complexity; Computer science; graph colouring; graph theory; matching polynomial; Polynomials; series-parallel graphs; Terminology; Tree data structures; Tree graphs

Learning visual coordinate transformations with competition - Cho,S.; Reggia, James A. (Neural Networks, 1992. IJCNN., International Joint Conference on, 1992)

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

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.

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

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

Testing preorders for probabilistic processes - Cleaveland, Rance; Smolka,S.; Zwarico,A. (Automata, Languages and Programming, 1992)

VLSI Implementation of Real-Time Parallel DCT/DST Lattice Structures for Video - Chiu,Ching-Te; Kolagotla,Ravi K.; Liu,K. J. Ray; JaJa, Joseph F. (Institute for Systems Research, University of Maryland, College Park, 1992)
The alternate use [1] of the discrete cosine transform (DCT) and the discrete sine transform (DST) can achieve a higher data compression rate and less block effect in image processing. A parallel lattice structure that can dually generate the 1-D DCT and DST is proposed. We also develop a fully-pipelined 2-D DCT lattice architecture that consists of two 1-D DCT/DST arrays without transposition. Both architectures are ideally suited for VLSI implementation because they are modular, regular, and have only local interconnections. the VLSI implementation of the lattice module using the distributed arithmetic approach is described. This realization of the lattice module using 2 um CMOS technology can achieve an 80Mb/s data rate.
Keywords: Parallel architectures; Signal processing; Systems Integration; VLSI architectures

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

Approximate parallel scheduling. II. Applications to logarithmic-time optimal parallel graph algorithms - Cole,R.; Vishkin, Uzi (Information and Computation, 1991)

Competitive activation mechanisms in connectionist models - Reggia, James A.; Sutton,G.; Cho,S. (Advances in control networks and large-scale parallel distributed processing models, 1991)

Computing behavioural relations, logically - Cleaveland, Rance; Steffen,B. (Automata, Languages and Programming, 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)

ESP'91 Panel on The Best of ESP - Zweben,S.; Curtis,B.; Shneiderman, Ben (Empirical studies of programmers: fourth workshop, 1991)

Gdr: A visualization tool for graph algorithms - Stallmann,M.; Cleaveland, Rance; Hebbar,P. (Citeseer, 1991)

A management tool for evaluation of software design - Cardenas-Garcia,S.; Zelkowitz, Marvin V (Software Engineering, IEEE Transactions on, 1991)
A model for evaluating software designs based on extending the functional model of program verification with concepts from economic decision theory has been proposed. The authors describe the method, and discuss a prototype implementation of a tool, called Selector, which implements this technique. It is suggested that a system like Selector can be used in two ways: as a decision support system for management to be used in the process of making choices among various alternatives; and as a prototyping investigative system for proposing and answering a series of `what if' scenarios. The proposed model depends on a risk analysis, of each potential solution and aspects of decision theory to modify the evaluation strategy. The model depends on equilibrium probabilities for generating answers
Keywords: analysis; software; decision; designs; decision; investigative; model; management; probabilities; evaluation; prototyping; software; Selector; decision; strategy; functional; Support; system; economic; system; risk; systems; program; theory; equilibrium; tool; program; tools; verification; prototyping; verification; software

Model group indexing for recognition - Clemens,D. T; Jacobs, David W. (Computer Vision and Pattern Recognition, 1991. Proceedings CVPR '91., IEEE Computer Society Conference on, 1991)
It is shown that an index space can be a powerful tool for reducing the image-model match search by a factor of <e1>k</e1>G-3 , but only when accompanied by some mechanism, such as grouping, that prevents the system from having to consider all matches between image groups of size G and model groups of size <e1>G</e1>. It is also shown that if image groups are to index a single point at recognition time, then the index space must contain pointers to each model group over a 2-D sheet, and should therefore be 2<e1>G</e1>-4 dimensional. A simple indexing system has been implemented to demonstrate these concepts, and a series of experiments have been conducted to investigate the tradeoffs between space and time. They indicate that the speedups are achievable, but require a large amount of space
Keywords: 2-D; dimensional; image; group; groups; image-model; indexing; pattern; lookup; match; pattern; recognition; data; recognition; pointers; computer; search; index; sheet; 2G-4; space; indexing; structures; table; system; model; vision; computerised

Parallel Algorithms for Channel Routing in the Knock-Knee Model - JaJa, Joseph F.; Chang,Shing-Chong (SIAM Journal on Computing, 1991)
The channel routing problem of a set of two-terminal nets in the knock-knee model is considered. A new approach to route all the nets within $d$ tracks, where $d$ is the density, such that the corresponding layout can be realized with three layers is developed. The routing and the layer assignment algorithms run in $O(\log n)$ time with $n / \log n$ processors on the CREW PRAM model under the reasonable assumption that all terminals lie in the range $[1,N]$, where $N = O(n)$.
Keywords: channel routing; Layout; left-edge algorithm; line packing; Parallel algorithms; VLSI design

Review of Fundamentals of Molecular Evolution, by Li. W.-H. and D. Graur - Cummings, Michael P. (Cladistics, 1991)

The role for executable specifications in system maintenance - Zelkowitz, Marvin V; Cardenas,Sergio (Information Sciences, 1991)
As software becomes increasingly complex, two attributes of the system life cycle are taking on more important roles. We need the ability to formally specify the functionality of the systems we build in order to minimize costly development problems and, with long life times, we need the ability to enhance existing systems with new features in order to prolong their usefulness. This enhancement process also needs a mechanism for formally defining any new functionality on data objects placed upon the system. This paper describes the AS∗ research project which is addressing this issue. AS∗ is a language-independent specification language embedded within an existing programming language for the purpose of providing extensions to existing systems. This paper discusses the designs of AS∗, the structure of the prototype implementation and describes some early experiences using the system.

Space and time bounds on indexing 3D models from 2D images - Clemens,D. T; Jacobs, David W. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1991)
Model-based visual recognition systems often match groups of image features to groups of model features to form initial hypotheses, which are then verified. In order to accelerate recognition considerably, the model groups can be arranged in an index space (hashed) offline such that feasible matches are found by indexing into this space. For the case of 2D images and 3D models consisting of point features, bounds on the space required for indexing and on the speedup that such indexing can achieve are demonstrated. It is proved that, even in the absence of image error, each model must be represented by a 2D surface in the index space. This places an unexpected lower bound on the space required to implement indexing and proves that no quantity is invariant for all projections of a model into the image. Theoretical bounds on the speedup achieved by indexing in the presence of image error are also determined, and an implementation of indexing for measuring this speedup empirically is presented. It is found that indexing can produce only a minimal speedup on its own. However, when accompanied by a grouping operation, indexing can provide significant speedups that grow exponentially with the number of features in the groups
Keywords: 2D; bounds; time; bounds; visual; extraction; grouping; features; model; features; model-based; images; 3D; indexing; feature; model; operation; image; pattern; picture; processing; recognition; recognition; computerised; recognition; space; systems; computerised

A superfamily of ıt Arabidopsis thaliana retrotransposons - Konieczny,A; Voytas,D. F; Cummings, Michael P.; Ausubel,F. M (Genetics, 1991)
We describe a superfamily of Arabidopsis thaliana retrotransposable elements that consists of at least ten related families designated Ta1-Ta10. The Ta1 family has been described previously. Two genomic clones representing the Ta2 and Ta3 elements were isolated from an A. thaliana (race Landsberg erecta) lambda library using sequences derived from the reverse transcriptase region of Ta1 as hybridization probes. Nucleotide sequence analysis showed that the Ta1, Ta2 and Ta3 families share greater than 75% amino acid identity in pairwise comparisons of their reverse transcriptase and RNase H genes. In addition to Ta1, Ta2 and Ta3, we identified seven other related retrotransposon families in Landsberg erecta, Ta4-Ta10, using degenerate primers and the polymerase chain reaction to amplify a highly conserved region of retrotransposon-encoded reverse transcriptase. One to two copies of elements Ta2-Ta10 are present in the genomes of the A. thaliana races Landsberg erecta and Columbia indicating that the superfamily comprises at least 0.1% of the A. thaliana genome. The nucleotide sequences of the reverse transcriptase regions of the ten element families place them in the category of copia-like retrotransposons and phylogenetic analysis of the amino acid sequences suggests that horizontal transfer may have played a role in their evolution.

A theory of testing for real-time - Cleaveland, Rance; Zwarico,A. E (, Proceedings of Sixth Annual IEEE Symposium on Logic in Computer Science, 1991. LICS '91, 1991)
A framework for generating testing preorders that relate processes on the basis of their timing behavior as well as their degree of relative nondeterminism is developed. The basic concepts of transition systems and testing are reviewed, and timed testing, which takes account of the delay exhibited by a process as it attempts to pass a test, is introduced. The framework is then applied to two different scenarios. In the first, relations are constructed that relate processes on the basis of all timing considerations. In the second, relations are constructed that relate processes on the basis of their relative speeds. In both cases, alternative denotational characterizations of the resulting preorders are presented, and examples are given to illustrate the utility of the approach
Keywords: Algebra; Character generation; Computer science; Delay; formal logic; Licenses; nondeterminism; Process control; Protocols; Real time systems; real-time; System testing; testing preorders; testing theory; timed testing; Timing; timing behavior; transition systems

VLSI architectures for multidimensional transforms - Chakrabarti,C.; JaJa, Joseph F. (Computers, IEEE Transactions on, 1991)
The authors propose a family of VLSI architectures with area-time tradeoffs for computing (<e1>N</e1> times;<e1>N</e1> times; . . . times;<e1>N</e1>) <e1>d</e1>-dimensional linear separable transforms. For fixed-precision arithmetic with <e1>b</e1> bits, the architectures have an area <e1>A</e1>=<e1>O</e1>(<e1>N</e1>d+2a) and computation time <e1>T</e1>=<e1>O</e1>(<e1>dN</e1>d/2-a<e1>b </e1>), and achieve the <e1>AT</e1>2 bound of <e1>AT</e1>2=<e1>O</e1>(<e1>n</e1>2<e1>b</e1> 2) for constant <e1>d</e1>, where <e1>n</e1>=<e1>N</e1>d and <e1>O</e1> lt;<e1>a</e1> les;<e1>d</e1>/2
Keywords: architecture; architectures; arithmetic; complexity; computational; Computer; digital; fixed-precision; linear; multidimensional; separable; transforms; VLSI

VLSI architectures for template matching and block matching - Chakrabarti,C.; JaJa, Joseph F. (Parallel architectures and algorithms for image understanding, 1991)

On automatically distinguishing inequivalent processes - Cleaveland, Rance (Workshop on Computer-Aided Verification, 1990)

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

Diagnostic reasoning at multiple levels of abstraction - Chu,B. T.B; Reggia, James A. (AI Systems in Government Conference, 1990. Proceedings., Fifth Annual, 1990)

Evaluation criteria for functional specifications - Cardenas,S.; Zelkowitz, Marvin V (Proceedings of the 12th international conference on Software engineering, 1990)

Evolution of avocados as revealed by DNA restriction fragment variation - Furnier,GR; Cummings, Michael P.; Clegg,M. T (J Hered, 1990)
Individuals representing the genus ıt Persea, subgenus ıt Persea were assayed for restriction fragment length polymorphisms in their chloroplast genome, nuclear ribosomal DNA, and the genes coding for the enzyme cellulase. The subgenus ıt Persea appears to consist of ıt P. schiedeana and a separate taxon containing the remaining species. ıt P. americana does not appear to be a monophyletic group. If ıt P. americana is to be maintained as a species containing var. ıt americana, var. ıt drymifolia, and var. ıt guatemalensis, then our data suggest that it should also contain varieties corresponding to ıt P. floccosa, ıt P. nubigena, and ıt P. steyermarkii. ıt P. americana var. ıt guatemalensis appears to have originated as a hybrid between ıt P. steyermarkii and ıt P. nubigena. The root-rot-resistant cultivar G755A is a hybrid progeny of ıt P. schiedeana and ıt P. americana var. guatemalensis. The three varieties of ıt P. americana were all distinguished by mutations.

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

Modeling diagnostic problem-solving at multiple levels of abstraction - Chu,B.-T.B.; Reggia, James A. (Artificial Intelligence Applications, 1990., Sixth Conference on, 1990)
A precise domain-independent computational model for diagnostic problem-solving at multiple levels of abstraction is presented. The knowledge representation framework allows causal knowledge to be represented in a precise yet natural way that reflects a human diagnostician's experience in guiding diagnostic reasoning at multiple levels of abstraction. The inference mechanism clearly defines how to form plausible diagnostic hypotheses guided by explicit causal links and the principle of parsimonious covering. It permits the efficient formation of high-level diagnostic hypotheses while at the same time ensuring that all plausible diagnostic alternatives will be considered if one wishes to reason at sufficiently detailed levels. A prototype implementation is described to demonstrate that the proposed inference model is natural for capturing a small but representative fragment of medical causal knowledge, and, with the addition of reasonable heuristics, that the inference mechanism exhibits desirable problem-solving behavior
Keywords: causal knowledge; diagnostic problem-solving; diagnostic reasoning; domain-independent computational model; explicit causal links; heuristic programming; heuristics; inference mechanism; inference mechanisms; knowledge capture; knowledge representation; knowledge representation framework; medical knowledge; multiple abstraction levels; parsimonious covering; plausible diagnostic hypotheses; problem solving

A preorder for partial process specifications - Cleaveland, Rance; Steffen,B. (CONCUR'90 Theories of Concurrency: Unification and Extension, 1990)

Priorities in process algebras - Cleaveland, Rance; Hennessy,Matthew (Information and Computation, 1990)
An operational semantics for an algebraic theory of concurrency that incorporates a notion of priority into the definition of the execution of actions is developed. An equivalence based on strong observational equivalence is defined and shown to be a congruence, and a complete axiomatization is given for finite terms. Several examples higlight the novelty and usefulness of our approach.

The structure, distribution and evolution of the ıt Ta1 retrotransposable element family of ıt Arabidopsis thaliana - Voytas,D. F; Konieczny,A; Cummings, Michael P.; Ausubel,F. M (Genetics, 1990)
The Ta1 elements are a low copy number, copia-like retrotransposable element family of Arabidopsis thaliana. Six Ta1 insertions comprise all of the Ta1 element copies found in three geographically diverse A. thaliana races. These six elements occupy three distinct target sites: Ta1-1 is located on chromosome 5 and is common to all three races (Col-0, Kas-1 and La-0). Ta1-2 is present in two races on chromosome 4 (Kas-1 and La-0), and Ta1-3, also located on chromosome 4, is present only in one race (La-0). The six Ta1 insertions share greater than 96% nucleotide identity, yet are likely to be incapable of further transposition due to deletions or nucleotide changes that alter either the coding capacity of the elements or conserved protein domains required for retrotransposition. Nucleotide sequence comparisons of these elements and the distribution of Ta1 among 12 additional A. thaliana geographical races suggest that Ta1-1 predated the global dispersal of A. thaliana. As the species spread throughout the world, two additional transposition events occurred which gave rise first to Ta1-2 and finally to Ta1-3.

Systolic architectures for the computation of the discrete Hartley and the discrete cosine transforms based on prime factor decomposition - Chakrabarti,C.; JaJa, Joseph F. (Computers, IEEE Transactions on, 1990)
Two-dimensional systolic array implementations for computing the discrete Hartley transform (DHT) and the discrete cosine transform (DCT) when the transform size <e1>N</e1> is decomposable into mutually prime factors are proposed. The existing two-dimensional formulations for DHT and DCT are modified, and the corresponding algorithms are mapped into two-dimensional systolic arrays. The resulting architecture is fully pipelined with no control units. The hardware design is based on bit serial left to right MSB (most significant bit) to LSB (least significant bit) binary arithmetic
Keywords: architectures; architectures; two-dimensional; arithmetic; discrete; arrays; fast; binary; cosine; decomposition; systolic; design; prime; factor; Fourier; Hartley; discrete; systolic; transforms; hardware; transforms; parallel

Tableau-based model checking in the propositional mu-calculus - Cleaveland, Rance (Acta Informatica, 1990)

Testing equivalence as a bisimulation equivalence - Cleaveland, Rance; Hennessy,M. (Automatic Verification Methods for Finite State Systems, 1990)

When is `partial' adequate? A logic-based proof technique using partial specifications - Cleaveland, Rance; Steffen,B. (Logic in Computer Science, 1990. LICS '90, Proceedings., Fifth Annual IEEE Symposium on e, 1990)
A technique is presented for ascertaining when a (finite-state) partial process specification is adequate, in the sense of being specified enough, for contexts in which it is to be used. The method relies on the automatic generation of a modal formula from the partial specification; if the remainder of the network satisfies this formula, then any process that meets the specification is guaranteed to ensure correct behavior of the overall system. Using the results, the authors develop compositional proof rules for establishing the correctness of networks of parallel processes and illustrate their use with several examples
Keywords: Calculus; Carbon capture and storage; compositional proof rules; Computer science; Concurrent computing; Context; correctness; formal specification; logic-based proof technique; modal formula; parallel processes; partial process specification; partial specifications; specification adequacy; State-space methods; Technological innovation

Faster optimal parallel prefix sums and list ranking - Cole,R.; Vishkin, Uzi (Information and Computation, 1989)

Fourier Analysis of Iterative Methods for Elliptic Problems - Chan, Tony F.; Elman, Howard (SIAM Review, 1989)
This paper presents a Fourier method for analyzing stationary iterative methods and preconditioners for discretized elliptic boundary value problems. As in the von Neumann stability analysis of hyperbolic and parabolic problems, the approach is easier to apply, reveals more details about convergence properties than about standard techniques, and can be applied in a systematic way to a wide class of numerical methods. Although the analysis is applicable only to periodic problems, the results essentially reproduce those of classical convergence and condition number analysis for problems with other boundary conditions, such as the Dirichlet problem. In addition, they give suggestive new evidence of the strengths and weaknesses of methods such as incomplete factorization preconditioners in the Dirichlet case.

Functional and psychosocial effects of multimodality limb-sparing therapy in patients with soft tissue sarcomas - Chang,A. E; Steinberg,S. M; Culnane,M.; Lampert,M. H; Reggia, James A.; Simpson,C. G; Hicks,J. E; White,D. E; Yang,J. J; Glatstein,E. (Journal of Clinical Oncology, 1989)

Optimal parallel algorithms for one-layer routing - Chang,S. C.; JaJa, Joseph F.; Ryu,K. W. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1989)

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

The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time - Cole,R.; Vishkin, Uzi (Algorithmica, 1988)

Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time - Cole,R.; Vishkin, Uzi (SIAM Journal on Computing, 1988)

Ecological studies of professional programmers - Shneiderman, Ben; Carroll,John M. (Commun. ACM, 1988)
For over two decades, software psychology researchers have been developing insights to software productivity and quality by investigating builders and users of software. This research has been diverse in both its approach and its impacts. It has introduced systematic behavioral measurement into the software development process and into research on new software techniques and technologies, and has also opened up new social and cognitive interpretations of software processes [5, 12].We now see evidence of a new thrust in software psychology coming to the fore, one in which usability researchers are direct participants in the definition and creation of new software artifacts. We call this paradigm Ecological Design, to emphasize (1) that realistic software situations are being confronted on their own terms, and (2) that the work is directed toward design results, not merely toward evaluation and description in the service of design goals. The reorientation towards studying teamwork was prompted in 1971 by Weinberg and followed by a few researchers at that time, but the movement has accelerated with the recent and intense interest in computer supported collaborative work [15]. This was apparent in the papers presented at the two workshops on Empirical Studies of Programmers [10, 13]. An accompanying shift has also occurred in the software engineering community. The traditional waterfall model of software development with the precise specification of a provable topdown design is giving way to newer exploratory styles of program development that emphasize rapid prototyping and iterative refinement. The shift from product to process also puts greater emphasis on team organization, group processes, management policies, reusability, development tools, design methods, debugging strategies, and maintenance [6]. The three papers in this special section exemplify this new paradigm. Rosson, Maass, and Kellogg and Curtis, Krasner, and Iscoe describe highly qualitative studies of professional designers that produced specific technical proposals for improving software tools and the coordination of project management, an assessment of major bottlenecks, and a new framework for thinking about software design as a learning and communication process. Soloway, Pinto, Letovsky, Littman, and Lampert describe the design and exploration of software documentation that grew out of similarly qualitative studies of program maintenance. We caution that this research paradigm is still in its infancy: setting design requirements and developing prototypes are not traditional activities of psychological researchers. These roles are still emerging, still being reconciled with the earlier paradigms. The particular projects highlighted here are only the beginning; the field continues to evolve, as more researchers are attracted, as more topics are explored, as more methods are developed. Thus, despite the shortcomings of any particular project, the trajectory of this paradigm seems clear to us: it is the development of ideas that directly impact productivity and quality in software. Indeed, part of our intention in presenting this special section is to encourage more and more rapid development of the new paradigm.

An empirical comparison of pie vs. linear menus - Callahan,J.; Hopkins,D.; Weiser,M.; Shneiderman, Ben (Proceedings of the SIGCHI conference on Human factors in computing systems, 1988)
Menus are largely formatted in a linear fashion listing items from the top to bottom of the screen or window. Pull down menus are a common example of this format. Bitmapped computer displays, however, allow greater freedom in the placement, font, and general presentation of menus. A pie menu is a format where the items are placed along the circumference of a circle at equal radial distances from the center. Pie menus gain over traditional linear menus by reducing target seek time, lowering error rates by fixing the distance factor and increasing the target size in Fitts's Law, minimizing the drift distance after target selection, and are, in general, subjectively equivalent to the linear style.

Optimal Architectures for Multidimensional Transforms - Chakrabarti,Chaitali; JaJa, Joseph F. (Institute for Systems Research, University of Maryland, College Park, 1988)
Multidimensional transforms have widespread applications in computer vision, pattern analysis and image processing. The only existing optimal architecture for computing multidimensional DFT on data of size n = Nd requires very large rotator units of area O(n^2) and pipeline-time O(log n). In this paper we propose a family of optimal architectures with areatime trade-offs for computing multidimensional transforms. The large rotator unit is replaced by a combination of a small rotator unit, a transpose unit and a block rotator unit. The combination has an area of O(N^(d+2a)) and a pipeline time of O(N^(d/2-a)log n), for 0 < a < d/2. We apply this scheme to design optimal architectures for two-dimensional DFT, DHT and DCT. The computation is made efficient by mapping each of the one-dimensional transforms involved into two dimensions.
Keywords: Technical Report

Optimal parallel algorithms for expression tree evaluation and list ranking - Cole,R.; Vishkin, Uzi (VLSI Algorithms and Architectures, 1988)

Optimal Systolic Designs for the Computation of the Discrete Hartley and the Discrete Cosine Transforms - Chakrabarti,Chaitali; JaJa, Joseph F. (Institute for Systems Research, University of Maryland, College Park, 1988)
In this paper, we propose new algorithms for computing the Discrete Hartley and the Discrete Cosine Transform. The algorithms are based on iterative applications of the modified small n algorithms of DFT. The one dimensional transforms are mapped into two dimensions first and then implemented on two dimensional systolic arrays. Pipelined bit serial architectures operating on left to right LSB to MSB binary arithmetic is the basis of the hardware design. Different hardware schemes for implementing these transforms are studied. We show that our schemes achieve a substantial speed-up over existing schemes.
Keywords: *ALGORITHMS; *BINARY ARITHMETIC; Computer architecture; DCT(DISCRETE COSINE TRANSFORM); DISCRETE FOURIER TRANSFORMS; ITERATIONS; NUMERICAL MATHEMATICS; TWO DIMENSIONAL

Parallel Algorithms for Wiring Module Pins to Frame Pads - Chang,Shing-Chong; JaJa, Joseph F. (Institute for Systems Research, University of Maryland, College Park, 1988)
We present fast and efficient parallel algorithms for several problems related to wiring a set of pins on a module to a set of pads lying on the houndary of a chip. The one-layer model is used to perform the wiring. Our basic model of parallel processing is the CREW-PRAM model which is characterized by the presence of an unlimited number processors sharing the main memory. Concurrent reads are allowed while concurrent writes are not. All our algorithms use 0(n) processors, where n is the input length. Our algorithms have fast implementations on other parallel models such as the mesh or the hypercube.
Keywords: *ALGORITHMS; *PARALLEL PROCESSING; COMPUTER PROGRAMMING AND SOFTWARE; efficiency; INPUT; LAYERS; length; MEMORY DEVICES; MODELS; MODULAR CONSTRUCTION; NUMERICAL MATHEMATICS; PARALLEL ORIENTATION; PINS; WIRE

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

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

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

Computer-supported cooperative work (panel): is this REALLY a new field of research? - Greif,Irene; Curtis,Bill; Krasner,Herb; Malone,Thomas W.; Shneiderman, Ben (Proceedings of the SIGCHI/GI conference on Human factors in computing systems and graphics interface, 1987)

Shared memory algorithms and the medial axis transform - Chandran,S.; Mount, Dave (IEEE Workshop on Computer Architecture for PAMI, 1987)

Subjective user evaluation of CF PASCAL programming tools - Chin,JP; Norman,K. L; Shneiderman, Ben (Department of Computer Science and Human-Computer Interaction Laboratory Working Paper, 1987)
This study investigated subjective evaluations of two programming environments: 1) SUPPORT, an interactive programming environment with a syntax directed editor on a personal computer and 2) a batch run environment on a large mainframe computer. Participants were students in a 15 week introductory computer science course. In Part 1, one group of 128 first used SUPPORT, while another group of 85 programmed on a mainframe environment. After 6 weeks they were given an evaluative questionnaire and then switched programming environments. In Part 2, 68 used SUPPORT and 60 used the mainframe. At the twelfth week of the course, they were given two questionnaires, one evaluating the environment they had used in the last 6 weeks and one comparing both enviro nments. A measure of programming performance (exam and programming project grades) was also collected. SUPPORT was predicted to reduce the burden of remembering syntactic details resulting in better performance and higher subjective evaluations. Unexpectedly, the SUPPORT users did not earn statistically significantly higher grades. Furthermore, participants expressed a preference for the mainframe over SUPPORT. Specific items on the questionnaires were used to diagnose the strengths and weaknesses of each environment. Designers of syntax directed editors should focus on reducing the syntactic burden not only in programming , but also in the user interface of these tools.

The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time, Ultracomputer Note-108 - Cole,R.; Vishkin, Uzi (TR-242, Department of Computer Science, Courant Institute NYU, 1986)

Approximate and exact parallel scheduling with applications to list, tree and graph problems - Cole,R.; Vishkin, Uzi (27th Annual Symposium on Foundations of Computer Science, 1986)

Approximate scheduling, exact scheduling, and applications to parallel algorithms - Cole,R.; Vishkin, Uzi (Proceedings Symposium on Foundations of Computer Science, 1986)

Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms - Cole,R.; Vishkin, Uzi (Proceedings of the eighteenth annual ACM symposium on Theory of computing, 1986)

Deterministic coin tossing with applications to optimal parallel list ranking - Cole,R.; Vishkin, Uzi (Information and Control, 1986)

Detection of Surface Orientation and Motion from Texture: The Case of Planes - Aloimonos, J.; Chou, P. B; Science, University of Rochester. Dept. of Computer (Dept. of Computer Science, University of Rochester, 1985)

Solving NP-hard problems in [] almost trees': Vertex cover - Coppersmith,D.; Vishkin, Uzi (Discrete applied mathematics, 1985)

A timed petri net methodolgoy for specifying real-time system timing requirements - Coolahan Jr,J. E; Roussopoulos, Nick (International Workshop on Timed Petri Nets, 1985)

Monitoring an Ada software development - Basili, Victor R.; Chang,Shih; Gannon,John; Katz,Elizabeth; Panlilio-Yap,N. Monina; Ramsey,Connie Loggia; Zelkowitz, Marvin V; Bailey,John; Kruesi,Elizabeth; Sheppard,Sylvia (ACM SIG Ada Letters, 1984)

Timing Requirements for Time-Driven Systems Using Augmented Petri Nets - Coolahan,J. E.; Roussopoulos, Nick (IEEE Transactions on Software Engineering, 1983)
A methodology for the statement of timing requirements is presented for a class of embedded computer systems. The notion of a "time-driven" system is introduced which is formalized using a Petri net model augmented with timing information. Several subclasses of time-driven systems are defined with increasing levels of complexity. By deriving the conditions under which the Petri net model can be proven to be safe in the presence of time, timing requirements for modules in the system can be obtained. Analytical techniques are developed for proving safeness in the presence of time for the net constructions used in the defined subclasses of time-driven systems.
Keywords: Application software; Concurrent computing; Control systems; Embedded computing; Embedded system; Helium; Modeling methodology; performance specifications; Petri nets; Power system modeling; Real time systems; real-time systems; Timing; timing requirements

A complexity theory for unbounded fan-in parallelism - Chandra,A. K; Stockmeyer,L. J; Vishkin, Uzi (23rd Annual Symposium on Foundations of Computer Science, 1982)

Use of cluster analysis to evaluate software engineering methodologies - Chen,Eric; Zelkowitz, Marvin V (Proceedings of the 5th international conference on Software engineering, 1981)
The development of quantitative measures to evaluate software development techniques is necessary if we are going to develop appropriate methodologies for software production. Data is collected by the Software Engineering Laboratory at NASA Goddard Space Flight Center on developing medium scale projects of up to ten man years effort. In this study, cluster analysis was used on this collected data and several measures are proposed. These measurements are objective, quantifiable, are the results of the methodology, and most important, seem relevant.

Systematic Derivation of Software Requirements - Yeh,R. Y; Roussopoulos, Nick; Chang,P. (Proceedings of the 1st International Conference on the Entity-Relationship Approach to Systems Analysis and Design, 1980)

Numerical Solution of Nonlinear Elliptic Partial Differential Equations by a Generalized Conjugate Gradient Method - Concus,Paul; Golub, Gene H.; O'Leary, Dianne P. (Computing, 1978)
We have studied previously a generalized conjugate gradient method for solving sparse positive-definite systems of linear equations arising from the discretization of elliptic partial-differential boundary-value problems. Here, extensions to the nonlinear case are considered. We split the original discretized operator into the sum of two operators, one of which corresponds to a more easily solvable system of equations, and accelerate the associated iteration based on this splitting by (nonlinear) conjugate gradients. The behavior of the method is illustrated for the minimal surface equation with splittings corresponding to nonlinear SSOR, to approximate factorization of the Jacobian matrix, and to elliptic operators suitable for use with fast direct methods. The results of numerical experiments are given as well for a mildy nonlinear example, for which, in the corresponding linear case, the finite termination property of the conjugate gradient algorithm is crucial.

A Generalized Conjugate Gradient Method for the Numerical Solution of Elliptic Partial Differential Equations - Concus,Paul; Golub, Gene H.; O'Leary, Dianne P. (Sparse Matrix ComputationsSparse Matrix Computations, 1976)
We consider a generalized conjugate gradient method for solvingsparse, symmetric, positive-definite systems of linear equations, principally those arising from the discretization of boundary value problems for elliptic partial differential equations. The method is based on splitting off from the original coefficient matrix a symmetric, positive-definiteonethat corresponds to a more easily solvable system of equations, and then accelerating the associated iteration using conjugate gradients. Optimality and convergence properties are presented, and the relation to other methods is discussed. Several splittings for which the method seems particularly effective are also discussed, and for some, numerical examples are given

TORUS: A step towards bridging the gap between data bases and the casual user - Mylopoulos,J.; Borgida,A.; Cohen,P.; Roussopoulos, Nick; Tsotsos,J.; Wong,H. (Information Systems, 1976)
This paper describes TORUS, a natural language understanding system that serves as a front end to a data base management system in order to facilitate communication with casual users. The system employs a semantic network to store knowledge about a data base of student files. This knowledge is used to find the meaning of each input statement, to decide what action to take with respect to the data base, and to select information that must be output in response to the input statement. A prototype version of TORUS has been implemented.

TORUS-a natural language understanding system for data management - Mylopoulos,J.; Borgida,A.; Cohen,P.; Roussopoulos, Nick; Tsotsos,J.; Wong,H. (Proceedings of the Fourth International Conference on Artificial Intelligence, 1975)