More efficient bottom-up multi-pattern matching in trees

DOI10.1016/0304-3975(92)90277-MMaRDI QIDQ685356zbMATH OpenOpenAlexFDO

Authors Jiazhen Cai, Robert Paige, Robert E. Tarjan

Publication date 17 October 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(92)90277-m

zbMATH Keywords

pattern preprocessingbottom-up algorithmsimple patterns

Mathematics Subject Classification ID

Theory of programming languages (68N15) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 125882
• Faster tree pattern matching
• Fast multiple pattern Cartesian tree matching
• scientific article; zbMATH DE number 4041265
• Fast algorithms for single and multiple pattern Cartesian tree matching
• Efficient pattern matching on graph patterns of bounded treewidth
• Tree Pattern Matching to Subset Matching in Linear Time
• TWO RELATED ALGORITHMS FOR ROOT-TO-FRONTIER TREE PATTERN MATCHING
• scientific article; zbMATH DE number 4053042
• scientific article; zbMATH DE number 2079422

Cites work

• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 4155917 (Why is no real title available?)
• scientific article; zbMATH DE number 3921984 (Why is no real title available?)
• scientific article; zbMATH DE number 4053042 (Why is no real title available?)
• scientific article; zbMATH DE number 125882 (Why is no real title available?)
• scientific article; zbMATH DE number 3502768 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 194514 (Why is no real title available?)
• scientific article; zbMATH DE number 3299786 (Why is no real title available?)
• Faster tree pattern matching
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Pattern Matching in Trees
• Preserving order in a forest in less than logarithmic time and linear space
• Programming with Equations
• Proving and applying program transformations expressed with second-order patterns
• Storing a Sparse Table with 0 (1) Worst Case Access Time

Cited in

(14)

• Generating tables for bottom-up matching
• TWO RELATED ALGORITHMS FOR ROOT-TO-FRONTIER TREE PATTERN MATCHING
• scientific article; zbMATH DE number 4155861 (Why is no real title available?)
• scientific article; zbMATH DE number 4058881 (Why is no real title available?)
• Left-to-right tree pattern matching
• An NSF proposal
• Tree pattern matching with a more general notion of occurrence of the pattern.
• scientific article; zbMATH DE number 4053042 (Why is no real title available?)
• scientific article; zbMATH DE number 125882 (Why is no real title available?)
• Higher-order matching for program transformation
• Efficient tree pattern unification
• Efficient preprocessing of simple binary pattern forests
• Computational Science and Its Applications – ICCSA 2004
• scientific article; zbMATH DE number 2079422 (Why is no real title available?)

Describes a project that uses

Uses Software

• OPTRAN

This page was built for publication: More efficient bottom-up multi-pattern matching in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685356)