Patterns and pattern-matching in trees: An analysis

DOI10.1016/S0019-9958(83)80056-4MaRDI QIDQ3683556zbMATH OpenFDO

Authors Jean-Marc Steyaert, Philippe Flajolet

Publication date 1983

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(83)80056-4

zbMATH Keywords

algorithmaverage case performance analysispattern treesequential tree- matchingtext tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10)

Recommendations

• Average-case analysis of pattern-matching in trees under the BST probability model
• scientific article; zbMATH DE number 4053042
• scientific article; zbMATH DE number 4060735
• Nonlinear pattern matching in trees
• An efficient algorithm for some tree matching problems

Cited in

(38)

• Complexity of matching problems
• Complexity analysis of term-rewriting systems
• Finding tree patterns consistent with positive and negative examples using queries
• On sets of integers with prescribed gaps
• Local limit approximations for Lagrangian distributions
• On the number of induced subgraphs of trees
• The depth first processes of Galton-Watson trees converge to the same Brownian excursion
• Rooted forests that avoid sets of permutations
• On coincidences of tuples in a \(q\)-ary tree with random labels of vertices
• The asymptotic behaviour of coefficients of powers of certain generating functions
• On an asymptotic method in enumeration
• Tree pattern matching with a more general notion of occurrence of the pattern.
• Some results on the asymptotic behaviour of coefficients of large powers of functions
• Supertrees
• Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves
• Noncontiguous pattern containment in binary trees
• Backward linearised tree pattern matching
• Patterns with Bounded Treewidth
• On coincidences of tuples in a binary tree with random labels of vertices
• scientific article; zbMATH DE number 3883604 (Why is no real title available?)
• scientific article; zbMATH DE number 3854413 (Why is no real title available?)
• TWO RELATED ALGORITHMS FOR ROOT-TO-FRONTIER TREE PATTERN MATCHING
• scientific article; zbMATH DE number 4053042 (Why is no real title available?)
• scientific article; zbMATH DE number 4058881 (Why is no real title available?)
• scientific article; zbMATH DE number 4060735 (Why is no real title available?)
• A complexity calculus for recursive tree algorithms
• Nonlinear pattern matching in trees
• scientific article; zbMATH DE number 7029315 (Why is no real title available?)
• Average-case analysis of pattern-matching in trees under the BST probability model
• scientific article; zbMATH DE number 1881087 (Why is no real title available?)
• On the asymptotic normality in the problem on the tuples repetitions in a marked complete tree
• scientific article; zbMATH DE number 7561480 (Why is no real title available?)
• Analytic analysis of algorithms
• The Distribution of Patterns in Random Trees
• Conditions for asymptotic normality of the number of multiple repetitions of chains in marked complete trees and forests;Условия асимптотической нормальности числа кратных повторений цепочек в помеченных полных деревьях и лесах
• Undesignable motifs in structural RNAs and combinatorial consequences
• Asymptotic normality of number of multiple coincidences of chains in complete q-ary trees and forests with randomly marked vertices
• Pattern avoidance in binary trees

This page was built for publication: Patterns and pattern-matching in trees: An analysis

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