A Fast Generic Sequence Matching Algorithm (2008)
Musser, David R., Nishanov, Gor V.
A string matching -- and more generally, sequence matching -- algorithm is presented that has a linear worst-case computing time bound, a low worst-case bound on the number of comparisons (2n), and...
Design patterns for library optimizations (2008)
Douglas Gregor, David R. Musser
We apply the notion of design patterns to optimizations performed by designers of software libraries, focusing especially on object-oriented numerical libraries. We formalize three design patterns...
Design patterns for library optimizations (2008)
Douglas Gregor, David R. Musser
We apply the notion of design patterns to optimizations performed by designers of software libraries, focusing especially on object-oriented numerical libraries. We formalize three design patterns...
An Experimental Analysis of Counting Networks ∗ (2008)
Eric N. Klein, Costas Busch, David R. Musser
Counting networks are highly distributed data structures that provide low contention solutions to distributed coordination problems. Counting networks are structured with balancers interconnected in...
Escuela de Computaci'on, Facultad de Ciencias (2007)
A complete traversal of a container C (such as a set) is informally described by the iteration scheme for all x 2 C F(x; C) where F is a function that might possibly modify C by inserting new...
Text-line Random Shuffling Program (2007)
This little program reads a sequence of text lines and writes them in a scrambled (randomized) order. Given any sequence of items formatted one item per line,
Jeremiah J. Willcock, David R. Musser, Ph. D, Daniel J. Quinlan, Ph. D
iii To my parents, James and Bonnie iv Acknowledgements I wish to thank my advisor, Andrew Lumsdaine, for much help throughout my career. He has provided a great deal of support and guidance during...
The Tecton Concept Library (2004)
Musser, David R., Schupp, Sibylle, Schwarzweller, Christoph, Loos, Rüdiger
Tecton is an algebraic specification language. This report contains a considerable body of Tecton concepts which evolved over a long time. The concepts serve as a test bed for a Tecton translator and...
Examining Committee: EFFICIENT METHODS FOR SOLVING BIOMECHANICAL EQUATIONS By (2003)
Joseph E. Flaherty, Franklin T. Luk, David R. Musser, Robert L. Spilker, Linda R. Petzold, Toshiro K. Ohsumi, ...
A Portable Cache Profiler Based on Source-Level Instrumentation,” tech. rep (2003)
1.2 Algorithms Should Be Cache-Conscious......................... 2
The Design of Data Type Specifications. (2002)
Guttag,John V., Horowitz,Ellis, Musser,David R.
This report concerns the design of data types in the creation of a software system; its major purpose is to explore a means for specifying a data type that is independent of its eventual...
Abstract Data Types and Software Validation. (2002)
Guttag,John V., Horowitz,Ellis, Musser,David R.
A data abstraction can be naturally expressed using algebraic axioms, whose virtue is that they permit a representation-independent formal specification of a data type. A moderately complex example...
Guttag,John V., Kapur,Deepak, Musser,David R.
Starting from the seminal work of Knuth and Bendix, we develop several notions useful in the study of term rewriting systems. In particular we introduce the notions of 'derived pairs' and 'overlap...
David R. Musser, Gor V. Nishanov
A string matching—and more generally, sequence matching—algorithm is presented that has a linear worst-case computing time bound, a low worst-case bound on the number of comparisons (2n), and...
David R. Musser, Gor V. Nishanov
A string matching—and more generally, sequence matching—algorithm is presented that has a linear worst-case computing time bound, a low worst-case bound on the number of comparisons (2n), and...
A Fast Generic Sequence Matching Algorithm (1998)
David R. Musser, Gor V. Nishanov
A string matching---and more generally, sequence matching---algorithm is presented that has a linear worst-case computing time bound, a low worst-case bound on the number of comparisons (2n), and...
A Fast Generic Sequence Matching Algorithm (1998)
David Musser Gor, David R. Musser, Gor V. Nishanov
A string matching---and more generally, sequence matching---algorithm is presented that has a linear worst-case computing time bound, a low worst-case bound on the number of comparisons (2n), and...
Introspective sorting and selection algorithms (1997)
Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is \Theta(N log N) and it is in fact faster than most other...
Dynamic Verification of C++ Generic Algorithms (1997)
Changqing Wang, David R. Musser
Dynamic verification is a new approach to formal verification, applicable to generic algorithms such as those found in the Standard Template Library (STL, part of the Draft ANSI/ISO C++ Standard...
David R. Musser, Changqing Wang
Generic algorithms are algorithms designed to work with a variety of data structures. A software library in which most algorithms are generic can thus provide very extensive capabilities with a...
Rationale for Adding Hash Tables to the C++ Standard Template Library (1995)
In Hash Tables for the Standard Template Library, Barreiro, Fraley, and Musser propose a restructuring and extension of the STL requirements for associative containers to accommodate hash table...
Algorithm-Oriented Generic Libraries (1994)
David R. Musser, Alexander A. Stepanov
We outline an approach to construction of software libraries in which generic algorithms (algorithmic abstractions) play a more central role than in conventional software library technology or in the...
Algorithm-oriented generic libraries (1994)
David R. Musser, Alexander A. Stepanov
We outline an approach to construction of software libraries in which generic algorithms (algorithmic abstractions) play a more central role than in conventional software library technology or in the...
An Overview of the Tecton Proof System (1992)
Deepak Kapur, David R. Musser, Xumin Nie
The Tecton Proof System is an experimental tool for constructing proofs of first order logic formulas and of program specifications expressed using formulas in Hoare's axiomatic proof formalism....
Tecton: A Framework for Specifying and Verifying Generic System Components (1992)
This paper presents the syntax and semantics of a small language for describing and using abstract concepts in formal software development and hardware design. The language provides definition,...
Examples of Tecton Concept Descriptions (1992)
Contents 1 Introduction 2 2 The examples 2 2.1 Boolean and Natural concepts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 2.2 Some algebraic concepts : : : : : : : : : : : : : : : :...
The Tecton Proof System (1992)
Deepak Kapur, David R. Musser, Xumin Nie
The Tecton Proof System is a new verification system designed to support construction of large and complex proofs, using novel user interface methods and extensive automation. We first describe the...
Multivariate polynomial factorization (1975)
grants GJ-239, GJ-30125X, and GJ-1069, the Mathematics Research