Average-case analysis of pattern-matching in trees under the bst probability model

DOI10.1007/3-540-58201-0_67MaRDI QIDQ4632425zbMATH OpenOpenAlexFDO

Authors Jose Ramon Sanchez Couso, María-Inés Fernández-Camacho

Publication date 29 April 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58201-0_67

zbMATH Keywords

binary treefixed patterninternal nodepattern matchingrandom pattern

Mathematics Subject Classification ID

PDEs in connection with computer science (35Q68) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Patterns and pattern-matching in trees: An analysis
• scientific article; zbMATH DE number 1080355
• Average-case analysis on simple families of trees using a balanced probability model
• On the subtrees of random binary search trees
• Analysis of the space of search trees under the random insertion algorithm

Cites work

• A complexity calculus for recursive tree algorithms
• Average-case analysis of pattern-matching in trees under the BST probability model
• Computation and use of data flow information in optimizing compilers
• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 176734 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• On the Average Size of the Intersection of Binary Trees
• Pattern Matching in Trees
• Patterns and pattern-matching in trees: An analysis
• Singularity Analysis of Generating Functions

Cited in

(10)

• Reductions in binary search trees
• Average case analysis for tree labelling schemes
• scientific article; zbMATH DE number 3883604 (Why is no real title available?)
• Patterns and pattern-matching in trees: An analysis
• scientific article; zbMATH DE number 18539 (Why is no real title available?)
• scientific article; zbMATH DE number 1080355 (Why is no real title available?)
• Average-case analysis of pattern-matching in trees under the BST probability model
• Binary search trees, recurrent properties and wave equations
• The effects of semantic simplifications on random \textit{BST}-like expression-trees
• Average-case analysis on simple families of trees using a balanced probability model

This page was built for publication: Average-case analysis of pattern-matching in trees under the bst probability model

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