Locating matches of tree patterns in forests

Andreas Neumann; Helmut Seidl

doi:10.1007/978-3-540-49382-2_12

Locating matches of tree patterns in forests

Andreas Neumann, Helmut Seidl

University of Trier

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

64 Scopus citations

Abstract

We deal with matching and locating of patterns in forests of variable arity. A pattern consists of a structural and a contextual condition for subtrees of a forest, both of which are given as tree or forest regular languages. We use the notation of constraint systems to uniformly specify both kinds of conditions. In order to implement pattern matching we introduce the class of pushdown forest automata.We identify a special class of contexts such that not only pattern matching but also locating all of a forest's subtrees matching in context can be performed in a single traversal. We also give a method for computing the reachable states of an automaton in order to minimize the size of transition tables.

Original language	English
Title of host publication	Foundations of Software Technology and Theoretical Computer Science - 18th Conference, Proceedings
Pages	134-146
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-540-49382-2_12
State	Published - 1998
Externally published	Yes
Event	18th Foundations of Software Technology and Theoretical Computer Science Conference, FST and TCS 1998 - Chennai, India Duration: 17 Dec 1998 → 19 Dec 1998

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1530 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th Foundations of Software Technology and Theoretical Computer Science Conference, FST and TCS 1998
Country/Territory	India
City	Chennai
Period	17/12/98 → 19/12/98

Access to Document

10.1007/978-3-540-49382-2_12

Cite this

Neumann, A., & Seidl, H. (1998). Locating matches of tree patterns in forests. In Foundations of Software Technology and Theoretical Computer Science - 18th Conference, Proceedings (pp. 134-146). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1530 LNCS). https://doi.org/10.1007/978-3-540-49382-2_12

@inproceedings{91e7c80ead74487b98bd700d0bfba523,

title = "Locating matches of tree patterns in forests",

abstract = "We deal with matching and locating of patterns in forests of variable arity. A pattern consists of a structural and a contextual condition for subtrees of a forest, both of which are given as tree or forest regular languages. We use the notation of constraint systems to uniformly specify both kinds of conditions. In order to implement pattern matching we introduce the class of pushdown forest automata.We identify a special class of contexts such that not only pattern matching but also locating all of a forest's subtrees matching in context can be performed in a single traversal. We also give a method for computing the reachable states of an automaton in order to minimize the size of transition tables.",

author = "Andreas Neumann and Helmut Seidl",

year = "1998",

doi = "10.1007/978-3-540-49382-2_12",

language = "English",

isbn = "3540653848",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "134--146",

booktitle = "Foundations of Software Technology and Theoretical Computer Science - 18th Conference, Proceedings",

note = "18th Foundations of Software Technology and Theoretical Computer Science Conference, FST and TCS 1998 ; Conference date: 17-12-1998 Through 19-12-1998",

}

Neumann, A & Seidl, H 1998, Locating matches of tree patterns in forests. in Foundations of Software Technology and Theoretical Computer Science - 18th Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1530 LNCS, pp. 134-146, 18th Foundations of Software Technology and Theoretical Computer Science Conference, FST and TCS 1998, Chennai, India, 17/12/98. https://doi.org/10.1007/978-3-540-49382-2_12

Locating matches of tree patterns in forests. / Neumann, Andreas; Seidl, Helmut.
Foundations of Software Technology and Theoretical Computer Science - 18th Conference, Proceedings. 1998. p. 134-146 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1530 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Locating matches of tree patterns in forests

AU - Neumann, Andreas

AU - Seidl, Helmut

PY - 1998

Y1 - 1998

N2 - We deal with matching and locating of patterns in forests of variable arity. A pattern consists of a structural and a contextual condition for subtrees of a forest, both of which are given as tree or forest regular languages. We use the notation of constraint systems to uniformly specify both kinds of conditions. In order to implement pattern matching we introduce the class of pushdown forest automata.We identify a special class of contexts such that not only pattern matching but also locating all of a forest's subtrees matching in context can be performed in a single traversal. We also give a method for computing the reachable states of an automaton in order to minimize the size of transition tables.

AB - We deal with matching and locating of patterns in forests of variable arity. A pattern consists of a structural and a contextual condition for subtrees of a forest, both of which are given as tree or forest regular languages. We use the notation of constraint systems to uniformly specify both kinds of conditions. In order to implement pattern matching we introduce the class of pushdown forest automata.We identify a special class of contexts such that not only pattern matching but also locating all of a forest's subtrees matching in context can be performed in a single traversal. We also give a method for computing the reachable states of an automaton in order to minimize the size of transition tables.

UR - http://www.scopus.com/inward/record.url?scp=84887122289&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-49382-2_12

DO - 10.1007/978-3-540-49382-2_12

M3 - Conference contribution

AN - SCOPUS:84887122289

SN - 3540653848

SN - 9783540653844

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 134

EP - 146

BT - Foundations of Software Technology and Theoretical Computer Science - 18th Conference, Proceedings

T2 - 18th Foundations of Software Technology and Theoretical Computer Science Conference, FST and TCS 1998

Y2 - 17 December 1998 through 19 December 1998

ER -

Locating matches of tree patterns in forests

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this