Pattern Matching in Trees
From MaRDI portal
Publication:3933760
DOI10.1145/322290.322295zbMath0477.68067OpenAlexW2421250929MaRDI QIDQ3933760
Michael J. O'Donnell, Christoph M. Hoffmann
Publication date: 1982
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322290.322295
subtree replacement systemsincremental pattern matchinginterpreter generationbottom-up matchingtop-down matching
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (64)
A set automaton to locate all pattern matches in a term ⋮ The inference of tree languages from finite samples: An algebraic approach ⋮ Tree automata for code selection ⋮ Tree template matching in ranked ordered trees by pushdown automata ⋮ Efficient preprocessing of simple binary pattern forests ⋮ Tree inclusions in windows and slices ⋮ Classes of equational programs that compile into efficient machine code ⋮ Left-to-right tree pattern matching ⋮ Incremental techniques for efficient normalization of nonlinear rewrite systems ⋮ Generating tables for bottom-up matching ⋮ Encompassment properties and automata with constraints ⋮ A compiler for nondeterministic term rewriting systems ⋮ On the Cooperative Graph Searching Problem ⋮ Implementation of an interpreter for abstract equations ⋮ On coincidences of tuples in a binary tree with random labels of vertices ⋮ Complexity of matching problems ⋮ Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees ⋮ Об асимптотической нормальности в задаче о повторениях цепочек в помеченном полном дереве ⋮ A metric normalization of tree edit distance ⋮ Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species ⋮ Tree pattern matching from regular tree expressions ⋮ From searching text to querying XML streams ⋮ On the subtree isomorphism problem for ordered trees ⋮ On modification of Boyer-Moore-Horspool's algorithm for tree pattern matching in linearised trees ⋮ A survey on tree matching and XML retrieval ⋮ Tree template matching in unranked ordered trees ⋮ On the hardness of computing the edit distance of shallow trees ⋮ Unnamed Item ⋮ Conditions for asymptotic normality of the number of multiple repetitions of chains in marked complete trees and forests;Условия асимптотической нормальности числа кратных повторений цепочек в помеченных полных деревьях и лесах ⋮ Parallel tree pattern matching ⋮ State Complexity of Regular Tree Languages for Tree Matching ⋮ Formal verification based on Boolean expression diagrams ⋮ Code selection by inversion of order-sorted derivors ⋮ Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism ⋮ Average-case analysis of pattern-matching in trees under the BST probability model ⋮ On Synchronizing Tree Automata and Their Work–Optimal Parallel Run, Usable for Parallel Tree Pattern Matching ⋮ An efficient algorithm for some tree matching problems ⋮ A note on the subtree isomorphism for ordered trees and related problems ⋮ Strings, trees, and patterns ⋮ Optimal parallel algorithms for forest and term matching ⋮ Simple tree pattern matching for trees in the prefix bar notation ⋮ Using multiset discrimination to solve language processing problems without hashing ⋮ On coincidences of tuples in a \(q\)-ary tree with random labels of vertices ⋮ TOWARDS PARALLEL PROGRAMMING BY TRANSFORMATION: THE FAN SKELETON FRAMEWORK* ⋮ More efficient bottom-up multi-pattern matching in trees ⋮ A sheaf-theoretic approach to pattern matching and related problems ⋮ PATTERN MATCHING CODE MINIMIZATION IN REWRITING-BASED PROGRAMMING LANGUAGES ⋮ On finding common subtrees ⋮ Automata-driven efficient subterm unification ⋮ Structural properties of XPath fragments ⋮ A survey on tree edit distance and related problems ⋮ Data mining in an engineering design environment: OR applications from graph matching ⋮ Linear matching-time algorithm for the directed graph isomorphism problem ⋮ Forward linearised tree pattern matching using tree pattern border array ⋮ An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation ⋮ Tree Template Matching in Ranked Ordered Trees by Pushdown Automata ⋮ Unnamed Item ⋮ On regular tree languages and deterministic pushdown automata ⋮ A new algorithm for linear regular tree pattern matching ⋮ Pattern matching in trees and nets ⋮ More efficient left-to-right matching for overlapping pattern ⋮ TWO RELATED ALGORITHMS FOR ROOT-TO-FRONTIER TREE PATTERN MATCHING ⋮ Tree pattern matching with a more general notion of occurrence of the pattern. ⋮ Distributive ρ-calculus
This page was built for publication: Pattern Matching in Trees
