More efficient bottom-up multi-pattern matching in trees

DOI10.1016/0304-3975(92)90277-MzbMath0777.68044OpenAlexW4213337636MaRDI QIDQ685356

Robert Paige, Jiazhen Cai, Robert Endre 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

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

Related Items (3)

Efficient preprocessing of simple binary pattern forests ⋮ Higher-order matching for program transformation ⋮ An NSF proposal

Uses Software

• OPTRAN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Preserving order in a forest in less than logarithmic time and linear space
• Proving and applying program transformations expressed with second-order patterns
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Pattern Matching in Trees
• Programming with Equations
• Faster tree pattern matching

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