On finding common subtrees (Q1208722): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(93)90198-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1984570480 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient string matching / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4091421 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3690245 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3690247 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3758253 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Variations on the Common Subexpression Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4038694 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pattern Matching in Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4125823 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5585020 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2736343 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the subtree isomorphism problem for ordered trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Space-Economical Suffix Tree Construction Algorithm / rank | |||
Normal rank |
Latest revision as of 16:28, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On finding common subtrees |
scientific article |
Statements
On finding common subtrees (English)
0 references
16 May 1993
0 references
Let \(T\) and \(R\) be two arbitrary ordered trees, \(| T|\geq| R|\), whose nodes are labelled over an alphabet \(A\). We devise a simple solution for detecting all the common subtree in \(O(| T|)\) time and space if the size of \(A\) is finite, and \(O(| T|\log\min(| A|,| T|))\) time otherwise. We solve the problem of finding in \(T\) and \(R\) all occurrences (if any) of any given tree \(B\) in either \(O(| T|/| B|)\) or \(O(| B|+| T|/| B|)\) time. This requires to set up a simple data structure in \(O(| T|)\) time that allows to find all maximal subtrees of \(B\) in \(O(| B|)\) time and to solve other related problems.
0 references
pattern matching
0 references
suffix tree
0 references
ordered trees
0 references