Tree inclusion problems

Patrick Cégielski; Irène Guessarian; Yuri Matiyasevich

RAIRO - Theoretical Informatics and Applications (2008)

  • Volume: 42, Issue: 1, page 5-20
  • ISSN: 0988-3754

Abstract

top
Given two trees (a target T and a pattern P) and a natural number w, window embedded subtree problems consist in deciding whether P occurs as an embedded subtree of T and/or finding the number of size (at most) w windows of T which contain pattern P as an embedded subtree. P is an embedded subtree of T if P can be obtained by deleting some nodes from T (if a node v is deleted, all edges adjacent to v are also deleted, and outgoing edges are replaced by edges going from the parent of v (if it exists) to the children of v). Deciding whether P is an embedded subtree of T is known to be NP-complete. Our algorithms run in time O(|T|22|P|) where |T| (resp. |P|) is the size of T (resp. P).

How to cite

top

Cégielski, Patrick, Guessarian, Irène, and Matiyasevich, Yuri. "Tree inclusion problems." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 5-20. <http://eudml.org/doc/250322>.

@article{Cégielski2008,
abstract = { Given two trees (a target T and a pattern P) and a natural number w, window embedded subtree problems consist in deciding whether P occurs as an embedded subtree of T and/or finding the number of size (at most) w windows of T which contain pattern P as an embedded subtree. P is an embedded subtree of T if P can be obtained by deleting some nodes from T (if a node v is deleted, all edges adjacent to v are also deleted, and outgoing edges are replaced by edges going from the parent of v (if it exists) to the children of v). Deciding whether P is an embedded subtree of T is known to be NP-complete. Our algorithms run in time O(|T|22|P|) where |T| (resp. |P|) is the size of T (resp. P). },
author = {Cégielski, Patrick, Guessarian, Irène, Matiyasevich, Yuri},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Subtree inclusion; algorithm; window embedded subtree problems},
language = {eng},
month = {1},
number = {1},
pages = {5-20},
publisher = {EDP Sciences},
title = {Tree inclusion problems},
url = {http://eudml.org/doc/250322},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Cégielski, Patrick
AU - Guessarian, Irène
AU - Matiyasevich, Yuri
TI - Tree inclusion problems
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/1//
PB - EDP Sciences
VL - 42
IS - 1
SP - 5
EP - 20
AB - Given two trees (a target T and a pattern P) and a natural number w, window embedded subtree problems consist in deciding whether P occurs as an embedded subtree of T and/or finding the number of size (at most) w windows of T which contain pattern P as an embedded subtree. P is an embedded subtree of T if P can be obtained by deleting some nodes from T (if a node v is deleted, all edges adjacent to v are also deleted, and outgoing edges are replaced by edges going from the parent of v (if it exists) to the children of v). Deciding whether P is an embedded subtree of T is known to be NP-complete. Our algorithms run in time O(|T|22|P|) where |T| (resp. |P|) is the size of T (resp. P).
LA - eng
KW - Subtree inclusion; algorithm; window embedded subtree problems
UR - http://eudml.org/doc/250322
ER -

References

top
  1. L. Boasson, P. Cegielski, I. Guessarian and Yu. Matiyasevich, Window accumulated subsequence matching is linear. Ann. Pure Appl. Logic113 (2001) 59–80.  Zbl0998.68042
  2. Y. Chi, R. Muntz, S. Nijssen and J. Kok, Frequent subtree mining – an overview. Fund. Inform.66 (2005) 161–198.  Zbl1096.68044
  3. P. Kilpelainen, Tree matching problems with applications to structured text databases. Ph.D. thesis, Helsinki (1992).  URIhttp://ethesis.helsinki.fi/julkaisut/mat/tieto/vk/kilpelainen/
  4. P. Kilpelainen and H. Mannila, Ordered and unordered tree inclusion. SIAM J. Comput.24 (1995) 340–356.  Zbl0827.68050

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.