| dc.contributor.advisor | Shankar, Priti | |
| dc.contributor.author | Yuvaraj, Athur RaGhuvir | |
| dc.date.accessioned | 2025-10-30T10:57:32Z | |
| dc.date.available | 2025-10-30T10:57:32Z | |
| dc.date.submitted | 1996 | |
| dc.identifier.uri | https://etd.iisc.ac.in/handle/2005/7269 | |
| dc.description.abstract | Tree pattern matching is foundational to a wide variety of applications in Computer Science. We consider the problem of linear tree pattern matching and adopt a technique used for parsing context-free languages for this purpose. We exploit the fact that a skeletal parse tree (the subject tree itself) is already available, and view the problem as one of tiling this tree in all possible ways, using productions representing input patterns. Our technique works in a bottom-up fashion, and requires matching time linear in the size of the tree. It offers potential advantages over existing bottom-up techniques in terms of auxiliary space required during pattern matching. We have tested the technique on several input data sets and report the results in this thesis. | |
| dc.language.iso | en_US | |
| dc.relation.ispartofseries | T04049 | |
| dc.rights | I grant Indian Institute of Science the right to archive and to make available my thesis or dissertation in whole or in part in all forms of media, now hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part of this thesis or dissertation | |
| dc.subject | Tree Pattern Matching | |
| dc.subject | Context-Free Languages | |
| dc.subject | Bottom-Up Parsing | |
| dc.title | New algorithm for linear tree pattern matching | |
| dc.degree.name | MSc Engg | |
| dc.degree.level | Masters | |
| dc.degree.grantor | Indian Institute of Science | |
| dc.degree.discipline | Engineering | |
