Locating Matches of Tree Patterns in Forests
Identifieur interne : 001315 ( Istex/Corpus ); précédent : 001314; suivant : 001316Locating Matches of Tree Patterns in Forests
Auteurs : Andreas Neumann ; Helmut SeidlSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1998.
Abstract
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.
Url:
DOI: 10.1007/978-3-540-49382-2_12
Links to Exploration step
ISTEX:4EBE51C251F9ABCEAB9CB94482DC467C5F02286ALe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Locating Matches of Tree Patterns in Forests</title><author><name sortKey="Neumann, Andreas" sort="Neumann, Andreas" uniqKey="Neumann A" first="Andreas" last="Neumann">Andreas Neumann</name><affiliation><mods:affiliation>Department of Computer Science, University of Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: neumann@psi.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name><affiliation><mods:affiliation>Department of Computer Science, University of Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: seidl@psi.uni-trier.de</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:4EBE51C251F9ABCEAB9CB94482DC467C5F02286A</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1007/978-3-540-49382-2_12</idno><idno type="url">https://api.istex.fr/document/4EBE51C251F9ABCEAB9CB94482DC467C5F02286A/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001315</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001315</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Locating Matches of Tree Patterns in Forests</title><author><name sortKey="Neumann, Andreas" sort="Neumann, Andreas" uniqKey="Neumann A" first="Andreas" last="Neumann">Andreas Neumann</name><affiliation><mods:affiliation>Department of Computer Science, University of Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: neumann@psi.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name><affiliation><mods:affiliation>Department of Computer Science, University of Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: seidl@psi.uni-trier.de</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1998</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">4EBE51C251F9ABCEAB9CB94482DC467C5F02286A</idno><idno type="DOI">10.1007/978-3-540-49382-2_12</idno><idno type="ChapterID">12</idno><idno type="ChapterID">Chap12</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Andreas Neumann</name><affiliations><json:string>Department of Computer Science, University of Trier, Germany</json:string><json:string>E-mail: neumann@psi.uni-trier.de</json:string></affiliations></json:item><json:item><name>Helmut Seidl</name><affiliations><json:string>Department of Computer Science, University of Trier, Germany</json:string><json:string>E-mail: seidl@psi.uni-trier.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>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.</abstract><qualityIndicators><score>6.452</score><pdfVersion>1.3</pdfVersion><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>721</abstractCharCount><pdfWordCount>5897</pdfWordCount><pdfCharCount>26838</pdfCharCount><pdfPageCount>13</pdfPageCount><abstractWordCount>121</abstractWordCount></qualityIndicators><title>Locating Matches of Tree Patterns in Forests</title><chapterId><json:string>12</json:string><json:string>Chap12</json:string></chapterId><refBibs><json:item><author><json:item><name>M Biehl</name></json:item><json:item><name>N Klarlund</name></json:item><json:item><name>T Rauhe</name></json:item></author><host><pages><first>135</first></pages><author></author><title>First International Workshop on Implementing Automata (WIA'96), LNCS 1260</title><publicationDate>1996</publicationDate></host><title>Algorithms for guided tree automata</title><publicationDate>1996</publicationDate></json:item><json:item><author><json:item><name>Bmw91,J Börstler</name></json:item><json:item><name>U Möncke</name></json:item><json:item><name>R Wilhelm</name></json:item></author><host><volume>13</volume><pages><last>314</last><first>295</first></pages><issue>3</issue><author></author><title>ACM TOPLAS</title><publicationDate>1991</publicationDate></host><title>Table Compression for Tree Automata</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>W S Bra69</name></json:item><json:item><name> Brainerd</name></json:item></author><host><volume>14</volume><pages><last>231</last><first>217</first></pages><issue>134</issue><author></author><title>Information and Control</title><publicationDate>1969</publicationDate></host><title>Tree Generating Regular Systems</title><publicationDate>1969</publicationDate></json:item><json:item><author><json:item><name>A,K Chandra</name></json:item><json:item><name>D,C Kozen</name></json:item><json:item><name>L,J Stockmeyer</name></json:item><json:item><name>Fs98,C Fecht</name></json:item><json:item><name>H Seidl</name></json:item></author><host><pages><last>133</last><first>114</first></pages><author></author><title>ESOP '98</title><publicationDate>1981</publicationDate></host><title>Propagating Differences: An Efficient New Fixpoint Algorithm for Distributive Constraint Systems</title><publicationDate>1981</publicationDate></json:item><json:item><author><json:item><name>C F Gol90</name></json:item><json:item><name> Goldfarb</name></json:item></author><host><volume>144</volume><pages><last>121</last><first>117</first></pages><issue>135</issue><author></author><title>E. Moriya. On two-way tree automata. IPL</title><publicationDate>1990</publicationDate></host><title>The SGML Handbook 134 LH92. B. LeCharlier and P. Van Hentenryck. A Universal Top-Down Fixpoint Algorithm</title><publicationDate>1990</publicationDate></json:item><json:item><author><json:item><name>M Murata</name></json:item><json:item><name>Mw95,D Maurer</name></json:item><json:item><name>R Wilhelm</name></json:item></author><host><pages><last>169</last><first>153</first></pages><author></author><title>Transformations of Trees and Schemas by Patterns and Contextual Conditions Principles of Document Processing (PODP'96) LNCS 1293 Tree Automata and Languages</title><publicationDate>1995</publicationDate></host><title>Compiler Design Locating Matches of Tree Patterns in Forests 141 Andreas Neumann and Helmut Seidl Pod92. A. Podelski. A Monoid Approach to Tree Automata</title><publicationDate>1995</publicationDate></json:item><json:item><author><json:item><name>C Pair</name></json:item><json:item><name>A Quere</name></json:item></author><host><volume>13</volume><pages><last>593</last><first>565</first></pages><author></author><title>Information and Control</title><publicationDate>1968</publicationDate></host><title>Définition et Etude des Bilangages Réguliers</title><publicationDate>1968</publicationDate></json:item><json:item><host><pages><last>145</last><first>140</first></pages><author><json:item><name>Sgym98,P Shankar</name></json:item><json:item><name>A Gantait</name></json:item><json:item><name>A,R Yuvaraj</name></json:item><json:item><name>M Madhavan</name></json:item></author><title>A New Algorithm for Linear Regular Tree Pattern Matching</title><publicationDate>1998</publicationDate></host></json:item><json:item><author><json:item><name>M Takahashi</name></json:item></author><host><volume>27</volume><pages><last>36</last><first>1</first></pages><issue>137</issue><author></author><title>Information and Control</title><publicationDate>1975</publicationDate></host><title>Generalizations of Regular Sets and their Application to a Study of Context-Free Languages</title><publicationDate>1975</publicationDate></json:item><json:item><author><json:item><name>J W Tha67</name></json:item><json:item><name> Thatcher</name></json:item></author><host><volume>1</volume><pages><last>322</last><first>317</first></pages><issue>138</issue><author></author><title>JCSS</title><publicationDate>1967</publicationDate></host><title>Characterizing Derivation Trees of Context-Free Grammars through a Generalization of Finite Automata Theory</title><publicationDate>1967</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name><affiliations><json:string>Karlsruhe University, Germany</json:string></affiliations></json:item><json:item><name>Juris Hartmanis</name><affiliations><json:string>Cornell University, NY, USA</json:string></affiliations></json:item><json:item><name>Jan van Leeuwen</name><affiliations><json:string>Utrecht University, The Netherlands</json:string></affiliations></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1998</copyrightDate></serie><host><editor><json:item><name>Vikraman Arvind</name><affiliations><json:string>The Institute of Mathematical Sciences, 600 113, Chennai, India</json:string><json:string>E-mail: arvind@imsc.res.in</json:string></affiliations></json:item><json:item><name>Sundar Ramanujam</name><affiliations><json:string>National Institute of Advanced Studies, Indian Institute of Science Campus, 560012, Bangalore, India</json:string><json:string>E-mail: sarukkai@nias.iisc.erenet.in</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Theory of Computation</value></json:item><json:item><value>Software Engineering</value></json:item><json:item><value>Programming Languages, Compilers, Interpreters</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item></subject><isbn><json:string>978-3-540-65384-4</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Foundations of Software Technology and Theoretical Computer Science</title><bookId><json:string>978-3-540-49382-2</json:string></bookId><volume>1530</volume><pages><last>145</last><first>134</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-49382-2</json:string></eisbn><copyrightDate>1998</copyrightDate><doi><json:string>10.1007/b71635</json:string></doi></host><publicationDate>1998</publicationDate><copyrightDate>1998</copyrightDate><doi><json:string>10.1007/978-3-540-49382-2_12</json:string></doi><id>4EBE51C251F9ABCEAB9CB94482DC467C5F02286A</id><score>1.033432</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/4EBE51C251F9ABCEAB9CB94482DC467C5F02286A/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/4EBE51C251F9ABCEAB9CB94482DC467C5F02286A/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/4EBE51C251F9ABCEAB9CB94482DC467C5F02286A/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Locating Matches of Tree Patterns in Forests</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag Berlin Heidelberg, 1998</p></availability><date>1998</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Locating Matches of Tree Patterns in Forests</title><author xml:id="author-1"><persName><forename type="first">Andreas</forename><surname>Neumann</surname></persName><email>neumann@psi.uni-trier.de</email><affiliation>Department of Computer Science, University of Trier, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">Helmut</forename><surname>Seidl</surname></persName><email>seidl@psi.uni-trier.de</email><affiliation>Department of Computer Science, University of Trier, Germany</affiliation></author></analytic><monogr><title level="m">Foundations of Software Technology and Theoretical Computer Science</title><title level="m" type="sub">18th Conference, Chennai, India, December 17-19, 1998. Proceedings</title><idno type="pISBN">978-3-540-65384-4</idno><idno type="eISBN">978-3-540-49382-2</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/b71635</idno><idno type="book-ID">978-3-540-49382-2</idno><idno type="book-title-ID">59049</idno><idno type="book-sequence-number">1530</idno><idno type="book-volume-number">1530</idno><idno type="book-chapter-count">34</idno><editor><persName><forename type="first">Vikraman</forename><surname>Arvind</surname></persName><email>arvind@imsc.res.in</email><affiliation>The Institute of Mathematical Sciences, 600 113, Chennai, India</affiliation></editor><editor><persName><forename type="first">Sundar</forename><surname>Ramanujam</surname></persName><email>sarukkai@nias.iisc.erenet.in</email><affiliation>National Institute of Advanced Studies, Indian Institute of Science Campus, 560012, Bangalore, India</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="1998"></date><biblScope unit="volume">1530</biblScope><biblScope unit="page" from="134">134</biblScope><biblScope unit="page" to="145">145</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName><affiliation>Karlsruhe University, Germany</affiliation></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName><affiliation>Cornell University, NY, USA</affiliation></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName><affiliation>Utrecht University, The Netherlands</affiliation></editor><biblScope><date>1998</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">4EBE51C251F9ABCEAB9CB94482DC467C5F02286A</idno><idno type="DOI">10.1007/978-3-540-49382-2_12</idno><idno type="ChapterID">12</idno><idno type="ChapterID">Chap12</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1998</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16005</label><label>I14029</label><label>I14037</label><label>I17028</label><item><term>Computer Science</term></item><item><term>Theory of Computation</term></item><item><term>Software Engineering</term></item><item><term>Programming Languages, Compilers, Interpreters</term></item><item><term>Discrete Mathematics in Computer Science</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1998">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-21">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/4EBE51C251F9ABCEAB9CB94482DC467C5F02286A/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Karlsruhe University</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Cornell University</OrgName><OrgAddress><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>Utrecht University</OrgName><OrgAddress><Country>The Netherlands</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingDepth="2" NumberingStyle="ContentOnly" OutputMedium="All" TocLevels="0"><BookID>978-3-540-49382-2</BookID><BookTitle>Foundations of Software Technology and Theoretical Computer Science</BookTitle><BookSubTitle>18th Conference, Chennai, India, December 17-19, 1998. Proceedings</BookSubTitle><BookVolumeNumber>1530</BookVolumeNumber><BookSequenceNumber>1530</BookSequenceNumber><BookDOI>10.1007/b71635</BookDOI><BookTitleID>59049</BookTitleID><BookPrintISBN>978-3-540-65384-4</BookPrintISBN><BookElectronicISBN>978-3-540-49382-2</BookElectronicISBN><BookChapterCount>34</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>1998</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16005" Priority="1" Type="Secondary">Theory of Computation</BookSubject><BookSubject Code="I14029" Priority="2" Type="Secondary">Software Engineering</BookSubject><BookSubject Code="I14037" Priority="3" Type="Secondary">Programming Languages, Compilers, Interpreters</BookSubject><BookSubject Code="I17028" Priority="4" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Vikraman</GivenName><FamilyName>Arvind</FamilyName></EditorName><Contact><Email>arvind@imsc.res.in</Email></Contact></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Sundar</GivenName><FamilyName>Ramanujam</FamilyName></EditorName><Contact><Email>sarukkai@nias.iisc.erenet.in</Email></Contact></Editor><Affiliation ID="Aff4"><OrgName>The Institute of Mathematical Sciences</OrgName><OrgAddress><Postcode>600 113</Postcode><City>Chennai</City><Country>India</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgDivision>National Institute of Advanced Studies</OrgDivision><OrgName>Indian Institute of Science Campus</OrgName><OrgAddress><Postcode>560012</Postcode><City>Bangalore</City><Country>India</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part7"><PartInfo TocLevels="0"><PartID>7</PartID><PartSequenceNumber>7</PartSequenceNumber><PartTitle>Session 3</PartTitle><PartChapterCount>2</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Foundations of Software Technology and Theoretical Computer Science</BookTitle></PartContext></PartInfo><Chapter ID="Chap12" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingDepth="2" NumberingStyle="ContentOnly" TocLevels="0"><ChapterID>12</ChapterID><ChapterDOI>10.1007/978-3-540-49382-2_12</ChapterDOI><ChapterSequenceNumber>12</ChapterSequenceNumber><ChapterTitle Language="En">Locating Matches of Tree Patterns in Forests</ChapterTitle><ChapterFirstPage>134</ChapterFirstPage><ChapterLastPage>145</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>1998</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>7</PartID><BookID>978-3-540-49382-2</BookID><BookTitle>Foundations of Software Technology and Theoretical Computer Science</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Andreas</GivenName><FamilyName>Neumann</FamilyName></AuthorName><Contact><Email>neumann@psi.uni-trier.de</Email></Contact></Author><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Helmut</GivenName><FamilyName>Seidl</FamilyName></AuthorName><Contact><Email>seidl@psi.uni-trier.de</Email></Contact></Author><Affiliation ID="Aff6"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>University of Trier</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>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.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Locating Matches of Tree Patterns in Forests</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Locating Matches of Tree Patterns in Forests</title></titleInfo><name type="personal"><namePart type="given">Andreas</namePart><namePart type="family">Neumann</namePart><affiliation>Department of Computer Science, University of Trier, Germany</affiliation><affiliation>E-mail: neumann@psi.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Helmut</namePart><namePart type="family">Seidl</namePart><affiliation>Department of Computer Science, University of Trier, Germany</affiliation><affiliation>E-mail: seidl@psi.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">1998</dateIssued><copyrightDate encoding="w3cdtf">1998</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">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.</abstract><relatedItem type="host"><titleInfo><title>Foundations of Software Technology and Theoretical Computer Science</title><subTitle>18th Conference, Chennai, India, December 17-19, 1998. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Vikraman</namePart><namePart type="family">Arvind</namePart><affiliation>The Institute of Mathematical Sciences, 600 113, Chennai, India</affiliation><affiliation>E-mail: arvind@imsc.res.in</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Sundar</namePart><namePart type="family">Ramanujam</namePart><affiliation>National Institute of Advanced Studies, Indian Institute of Science Campus, 560012, Bangalore, India</affiliation><affiliation>E-mail: sarukkai@nias.iisc.erenet.in</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1998</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16005">Theory of Computation</topic><topic authority="SpringerSubjectCodes" authorityURI="I14029">Software Engineering</topic><topic authority="SpringerSubjectCodes" authorityURI="I14037">Programming Languages, Compilers, Interpreters</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic></subject><identifier type="DOI">10.1007/b71635</identifier><identifier type="ISBN">978-3-540-65384-4</identifier><identifier type="eISBN">978-3-540-49382-2</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">59049</identifier><identifier type="BookID">978-3-540-49382-2</identifier><identifier type="BookChapterCount">34</identifier><identifier type="BookVolumeNumber">1530</identifier><identifier type="BookSequenceNumber">1530</identifier><identifier type="PartChapterCount">2</identifier><part><date>1998</date><detail type="part"><title>Session 3</title></detail><detail type="volume"><number>1530</number><caption>vol.</caption></detail><extent unit="pages"><start>134</start><end>145</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 1998</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><affiliation>Karlsruhe University, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><affiliation>Cornell University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><affiliation>Utrecht University, The Netherlands</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1998</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 1998</recordOrigin></recordInfo></relatedItem><identifier type="istex">4EBE51C251F9ABCEAB9CB94482DC467C5F02286A</identifier><identifier type="DOI">10.1007/978-3-540-49382-2_12</identifier><identifier type="ChapterID">12</identifier><identifier type="ChapterID">Chap12</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 1998</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 1998</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001315 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001315 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:4EBE51C251F9ABCEAB9CB94482DC467C5F02286A
|texte= Locating Matches of Tree Patterns in Forests
}}
| This area was generated with Dilib version V0.6.31. |  |