Pattern Matching in Trees
Journal of the ACMPublished 1 January 1982Open access
Christoph M. Hoffmann, Michael J. O’Donnell
Citations440
SJR quartileQ1
SJR score2.25
SNIP3.16
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Five new techniques for tree pattern matching are presented, analyzed for time and space complexity, and compared with previously known methods.
Abstract
ABSTgACT. Tree pattern matching is an interesting special problem which occurs as a crucial step m a number of programmmg tasks, for instance, design of interpreters for nonprocedural programming languages, automatic implementations of abstract data types, code optimization m compilers, symbohc computation, context searching in structure editors, and automatic theorem provmg. As with the sorting problem, the variations in requirements and resources for each application seem to preclude a uniform, umversal solution to the tree-pattern-matching problem. Instead, a collection of well-analyzed techmques, from which specific applications may be selected and adapted, should be sought. Five new techniques for tree pattern matching are presented, analyzed for time and space complexity, and compared with previously known methods. Particularly important are applications where the same patterns are matched against many subjects and where a subject may be modified incrementally Therefore, methods which spend some tune preprocessmg patterns in order to improve the actual matching time are included Categories and SubJect Descriptors' F.2.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
CYBRA (Lodz University of Technology)The Art of Computer Programming: Volume 3: Sorting and Searching
3,961 Citations1973Donald Knuth
Journal of the ACMA Machine-Oriented Logic Based on the Resolution Principle
3,885 Citations1965John A. Robinson
The paper concludes with a discussion of several principles which are applicable to the design of efficient proof-procedures employing resolution as the basle logical process.
Communications of the ACMEfficient string matching
2,946 Citations1975Alfred V. Aho, Margaret J. Corasick
A simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text that has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
SIAM Journal on ComputingFast Pattern Matching in Strings
2,917 Citations1977Donald E. Knuth, James H. Morris +1 more
An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time.
Communications of the ACMA fast string searching algorithm
2,292 Citations1977Robert S. Boyer, J Strother Moore
The algorithm has the unusual property that, in most cases, not all of the first i.” in another string, are inspected.
Simple Word Problems in Universal Algebras
1,373 Citations1983Donald E. Knuth, PETER B. BENDIX
Journal of the ACMFast Decision Procedures Based on Congruence Closure
509 Citations1980Greg Nelson, Derek C. Oppen
A simple proof is given that the congruence closure algorithm provides a decision procedure for the quantifier-free theory of equality and the problem of determining the satisfiability of a conjunction of literals becomes NP-complete if the axiomatization of the theory of list structure is changed slightly.
Elsevier eBooksSimple Word Problems in Universal Algebras††The work reported in this paper was supported in part by the U.S. Office of Naval Research.
468 Citations1970Donald E. Knuth, PETER B. BENDIX
Communications of the ACMAbstract data types and software validation
410 Citations1978John V. Guttag, Ellis Horowitz +1 more
The major thrust of the paper is shown how the use of algebraic axiomatizations can simplify the process of proving the correctness of an implementation of an abstract data type.
Journal of the ACMTree-Manipulating Systems and Church-Rosser Theorems
352 Citations1973Barry K. Rosen
It is shown that recursively defined functions are single-valued despite the nondeterminism of the evaluation algorithm, and that these functions solve their defining equations in a “canonical” manner.
Universal classes of hash functions (Extended Abstract)
349 Citations1977J. Lawrence Carter, Mark N. Wegman
An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions.
Acta InformaticaProving and applying program transformations expressed with second-order patterns
285 Citations1978G�rard Huet, Bernard Lang
A complete second-order matching algorithm is presented that allows effective use of these rules and it is shown how to formally prove the correctness of the rules using a denotational semantics for the programming language.
Rapid identification of repeated patterns in strings, trees and arrays
276 Citations1972Richard M. Karp, Raymond E. Miller +1 more
This paper describes a strategy for constructing efficient algorithms for solving two types of matching problems and develops explicit algorithms for these two problems applied to strings and arrays.
ACM Transactions on Programming Languages and SystemsProgramming with Equations
172 Citations1982Christoph M. Hoffmann, Michael J. O’Donnell
The goal of the study is a system to automatically transform a set of equations into an efficient program which exactly implements the logical meaning of the equations.
Complexity of finitely presented algebras
158 Citations1977Dexter Kozen
The schema satisfiability problem and schema validity problem are shown to be ≤m m log-complete for NP and co-NP, respectively, and the problem of isomorphism of finitely presented algebras is shown to to be polynomial time many-one equivalent to the issue of graph isomorphicism.
Communications of the ACMPerfect hashing functions
151 Citations1977Renzo Sprugnoli
A refinement of hashing which allows retrieval of an item in a static table with a single probe is considered, and a rough comparison with ordinary hashing is given which shows that this method can be used conveniently in several practical applications.
Linear unification
70 Citations1976Mike Paterson, Mark N. Wegman
A unification algorithm is described which tests a set of expressions for unifiability and which requires time and space which are only linear in the size of the input.
The SAC-1 system
48 Citations1971George E. Collins
SAC-1 is a program system for performing operations on multivariate polynomials and rational functions with infinite-precision coefficients that is extremely accessible, portable, easy to learn, and indeed has been implemented at more than 20 institutions.
An improved algorithm for computing with equations
31 Citations1980Paul Chew
The definition of a nonoverlapping s set of axiom schemata is given and the directed congruence closure algorithm is presented; an algorithm that efficiently solves this kind of problem provided the axiomschemata are non overlapping.
An interpreter generator using tree pattern matching
28 Citations1979Christoph M. Hoffmann, Michael J. O’Donnell
This paper presents techniques for automatically generating interpreters from equations, analagous to well-known techniques for generating parsers from context-free grammars, and believes that the techniques form the beginnings of a useful discipline of interpreting, comparable to the existing discipline of parsing.
Informatik-FachberichteOPTRAN, a Language for the Specification of Program Transformations
20 Citations1980Ingrid Glasner, Ulrich Möncke +1 more
The programming language OPTRAN is based on attributed transformational grammars, but extends these to achieve more compact descriptions, more efficient transformers, and an adequate cooperation of several transformation passes.
Minimal and optimal computations of recursive programs
16 Citations1977Gérard Berry, Jean-Jacques Lévy
The aim is to extend these results, for the three following reasons : first, though every program can be transformed to match Vuillemin's conditions, the transformations may affect the costs of computations : a more direct proof can be investigated.
Off-line and on-line algorithms for deducing equalities
13 Citations1978Peter J. Downey, Hanan Samet +1 more
A linear time algorithm for detecting common subexpressions is derived and algorithms which process equalities, inequalities and deductions on-line are discussed.