7/2011 - Finding a forest in a tree
Giorgio Bacci, Marino Miculan, Romeo Rizzi
| Titolo | Finding a forest in a tree |
|---|---|
| Numero | 7/2011 |
| Sottomesso da | Marino Miculan |
| Sottomesso il | 5/9/2011 |
| Stato | Draft |
| Autori | Giorgio Bacci, Marino Miculan, Romeo Rizzi |
| Abstract | In this paper we consider the problem of finding a forest inside an unordered tree, with no overlaps. This apparently simple problem arises in many situations, in particular in tree transformation systems with parametric rules, like e.g., in models for mobile and distributed computations, where agents can be nested forming a tree-like global state which evolves according to subtree rewriting rules. Another possible application is pattern matching within semi-structured data, like XML. Although the problem is NP-complete in general, using the theory of Fixed Parameter Tractability we show that the exponential explosion depends only on the width of the forest to be found, and not on the size of the global tree. In most practical cases, the forest width is constant and small (e.g. ≤ 3), hence the problem is feasible. |
| File | 7-2011-miculan.pdf |