A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness
Identifieur interne : 001A91 ( Istex/Corpus ); précédent : 001A90; suivant : 001A92A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness
Auteurs : Anna KasprzikSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2008.
Abstract
Abstract: We generalize a learning algorithm by Drewes and Högberg [1] for regular tree languages based on a learning model proposed by Angluin [2] to recognizable tree languages of arbitrarily many dimensions, so-called multi-dimensional trees. Trees over multi-dimensional tree domains have been defined by Rogers [3,4]. However, since the algorithm by Drewes and Högberg relies on classical finite state automata, these structures have to be represented in another form to make them a suitable input for the algorithm: We give a new representation for multi-dimensional trees which establishes them as a direct generalization of classical trees over a partitioned alphabet, and show that with this notation Drewes’ and Högberg’s algorithm is able to learn tree languages of arbitrarily many dimensions. Via the correspondence between trees and string languages (“yield operation”) this is equivalent to the statement that this way even some string language classes beyond context-freeness have become learnable with respect to Angluin’s learning model as well.
Url:
DOI: 10.1007/978-3-540-88009-7_9
Links to Exploration step
ISTEX:9B9B6722B6D98E85B9A749F3660D735BBD244882Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct:series"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness</title><author><name sortKey="Kasprzik, Anna" sort="Kasprzik, Anna" uniqKey="Kasprzik A" first="Anna" last="Kasprzik">Anna Kasprzik</name><affiliation><mods:affiliation>University of Trier</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:9B9B6722B6D98E85B9A749F3660D735BBD244882</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1007/978-3-540-88009-7_9</idno><idno type="url">https://api.istex.fr/document/9B9B6722B6D98E85B9A749F3660D735BBD244882/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001A91</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001A91</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness</title><author><name sortKey="Kasprzik, Anna" sort="Kasprzik, Anna" uniqKey="Kasprzik A" first="Anna" last="Kasprzik">Anna Kasprzik</name><affiliation><mods:affiliation>University of Trier</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2008</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">9B9B6722B6D98E85B9A749F3660D735BBD244882</idno><idno type="DOI">10.1007/978-3-540-88009-7_9</idno><idno type="ChapterID">9</idno><idno type="ChapterID">Chap9</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 generalize a learning algorithm by Drewes and Högberg [1] for regular tree languages based on a learning model proposed by Angluin [2] to recognizable tree languages of arbitrarily many dimensions, so-called multi-dimensional trees. Trees over multi-dimensional tree domains have been defined by Rogers [3,4]. However, since the algorithm by Drewes and Högberg relies on classical finite state automata, these structures have to be represented in another form to make them a suitable input for the algorithm: We give a new representation for multi-dimensional trees which establishes them as a direct generalization of classical trees over a partitioned alphabet, and show that with this notation Drewes’ and Högberg’s algorithm is able to learn tree languages of arbitrarily many dimensions. Via the correspondence between trees and string languages (“yield operation”) this is equivalent to the statement that this way even some string language classes beyond context-freeness have become learnable with respect to Angluin’s learning model as well.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Anna Kasprzik</name><affiliations><json:string>University of Trier,</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: We generalize a learning algorithm by Drewes and Högberg [1] for regular tree languages based on a learning model proposed by Angluin [2] to recognizable tree languages of arbitrarily many dimensions, so-called multi-dimensional trees. Trees over multi-dimensional tree domains have been defined by Rogers [3,4]. However, since the algorithm by Drewes and Högberg relies on classical finite state automata, these structures have to be represented in another form to make them a suitable input for the algorithm: We give a new representation for multi-dimensional trees which establishes them as a direct generalization of classical trees over a partitioned alphabet, and show that with this notation Drewes’ and Högberg’s algorithm is able to learn tree languages of arbitrarily many dimensions. Via the correspondence between trees and string languages (“yield operation”) this is equivalent to the statement that this way even some string language classes beyond context-freeness have become learnable with respect to Angluin’s learning model as well.</abstract><qualityIndicators><score>8.384</score><pdfVersion>1.6</pdfVersion><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>1063</abstractCharCount><pdfWordCount>7732</pdfWordCount><pdfCharCount>32744</pdfCharCount><pdfPageCount>14</pdfPageCount><abstractWordCount>157</abstractWordCount></qualityIndicators><title>A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness</title><chapterId><json:string>9</json:string><json:string>Chap9</json:string></chapterId><refBibs><json:item><author><json:item><name>F Drewes</name></json:item><json:item><name>J Högberg</name></json:item></author><host><pages><last>291</last><first>279</first></pages><author></author><title>DLT 2003</title><publicationDate>2003</publicationDate></host><title>Learning a Regular Tree Language from a Teacher</title><publicationDate>2003</publicationDate></json:item><json:item><author><json:item><name>D Angluin</name></json:item></author><host><volume>75</volume><pages><last>106</last><first>87</first></pages><issue>2</issue><author></author><title>Information and Computation</title><publicationDate>1987</publicationDate></host><title>Learning regular sets from queries and counterexamples</title><publicationDate>1987</publicationDate></json:item><json:item><author><json:item><name>J Rogers</name></json:item></author><host><volume>1</volume><pages><last>305</last><first>265</first></pages><author></author><title>Research on Language and Computation</title><publicationDate>2003</publicationDate></host><title>Syntactic Structures as Multi-dimensional Trees</title><publicationDate>2003</publicationDate></json:item><json:item><author><json:item><name>J Rogers</name></json:item></author><host><volume>293</volume><pages><last>320</last><first>291</first></pages><issue>762–3</issue><author></author><title>TCS Theoretical Computer Science</title><publicationDate>1990</publicationDate></host><title>wMSO Theories as Grammar Formalisms Learning context-free grammars from structural data in polynomial time</title><publicationDate>1990</publicationDate></json:item><json:item><host><author><json:item><name>A,K Joshi</name></json:item></author><title>Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural description Natural Language Processing</title><publicationDate>1985</publicationDate></host></json:item><json:item><author><json:item><name>D,J Weir</name></json:item></author><host><volume>104</volume><pages><last>261</last><first>235</first></pages><issue>2</issue><author></author><title>Theoretical Computer Science</title><publicationDate>1992</publicationDate></host><title>A geometric hierarchy beyond context-free languages</title><publicationDate>1992</publicationDate></json:item><json:item><host><author><json:item><name>A Kasprzik</name></json:item></author><title>Two Equivalent Regularizations of Tree Adjoining Grammars</title><publicationDate>2008</publicationDate></host></json:item><json:item><host><author><json:item><name>A Kasprzik</name></json:item></author><title>Making Finite-State Methods Applicable to Languages Beyond Context-Freeness via Multi-dimensional Trees</title><publicationDate>2008</publicationDate></host></json:item><json:item><author><json:item><name>O Maler</name></json:item><json:item><name>A Pnueli</name></json:item></author><host><pages><last>136</last><first>128</first></pages><author></author><title>Proc. 4th Annual Workshop on Comp. Learning Th</title><publicationDate>1991</publicationDate></host><title>On the learnability of infinitary regular sets</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>F Drewes</name></json:item><json:item><name>J Högberg</name></json:item></author><host><volume>40</volume><pages><last>185</last><first>163</first></pages><issue>2</issue><author></author><title>Theory of Computing Systems</title><publicationDate>2007</publicationDate></host><title>Query Learning of Regular Tree Languages: How to Avoid Dead States</title><publicationDate>2007</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><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>2008</copyrightDate></serie><host><editor><json:item><name>Alexander Clark</name></json:item><json:item><name>François Coste</name></json:item><json:item><name>Laurent Miclet</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Artificial Intelligence (incl. Robotics)</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item></subject><isbn><json:string>978-3-540-88008-0</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Grammatical Inference: Algorithms and Applications</title><bookId><json:string>978-3-540-88009-7</json:string></bookId><volume>5278</volume><pages><last>124</last><first>111</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-88009-7</json:string></eisbn><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-88009-7</json:string></doi></host><publicationDate>2008</publicationDate><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-88009-7_9</json:string></doi><id>9B9B6722B6D98E85B9A749F3660D735BBD244882</id><score>1.8148637</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/9B9B6722B6D98E85B9A749F3660D735BBD244882/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/9B9B6722B6D98E85B9A749F3660D735BBD244882/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/9B9B6722B6D98E85B9A749F3660D735BBD244882/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness</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, 2008</p></availability><date>2008</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness</title><author xml:id="author-1"><persName><forename type="first">Anna</forename><surname>Kasprzik</surname></persName><affiliation>University of Trier,</affiliation></author></analytic><monogr><title level="m">Grammatical Inference: Algorithms and Applications</title><title level="m" type="sub">9th International Colloquium, ICGI 2008 Saint-Malo, France, September 22-24, 2008 Proceedings</title><idno type="pISBN">978-3-540-88008-0</idno><idno type="eISBN">978-3-540-88009-7</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/978-3-540-88009-7</idno><idno type="book-ID">978-3-540-88009-7</idno><idno type="book-title-ID">182834</idno><idno type="book-sequence-number">5278</idno><idno type="book-volume-number">5278</idno><idno type="book-chapter-count">29</idno><editor><persName><forename type="first">Alexander</forename><surname>Clark</surname></persName></editor><editor><persName><forename type="first">François</forename><surname>Coste</surname></persName></editor><editor><persName><forename type="first">Laurent</forename><surname>Miclet</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2008"></date><biblScope unit="volume">5278</biblScope><biblScope unit="page" from="111">111</biblScope><biblScope unit="page" to="124">124</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><biblScope><date>2008</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><series><title level="s">Lecture Notes in Artificial Intelligence</title><editor><persName><forename type="first">Jaime</forename><forename type="first">G.</forename><surname>Carbonell</surname></persName></editor><editor><persName><forename type="first">J\"org</forename><surname>Siekmann</surname></persName></editor><editor><persName><forename type="first">Alexander</forename><surname>Clark</surname></persName></editor><editor><persName><forename type="first">François</forename><surname>Coste</surname></persName></editor><editor><persName><forename type="first">Laurent</forename><surname>Miclet</surname></persName></editor><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><biblScope unit="seriesId">1244</biblScope></series><idno type="istex">9B9B6722B6D98E85B9A749F3660D735BBD244882</idno><idno type="DOI">10.1007/978-3-540-88009-7_9</idno><idno type="ChapterID">9</idno><idno type="ChapterID">Chap9</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2008</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: We generalize a learning algorithm by Drewes and Högberg [1] for regular tree languages based on a learning model proposed by Angluin [2] to recognizable tree languages of arbitrarily many dimensions, so-called multi-dimensional trees. Trees over multi-dimensional tree domains have been defined by Rogers [3,4]. However, since the algorithm by Drewes and Högberg relies on classical finite state automata, these structures have to be represented in another form to make them a suitable input for the algorithm: We give a new representation for multi-dimensional trees which establishes them as a direct generalization of classical trees over a partitioned alphabet, and show that with this notation Drewes’ and Högberg’s algorithm is able to learn tree languages of arbitrarily many dimensions. Via the correspondence between trees and string languages (“yield operation”) this is equivalent to the statement that this way even some string language classes beyond context-freeness have become learnable with respect to Angluin’s learning model as well.</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>I21017</label><label>I16048</label><label>I1603X</label><item><term>Computer Science</term></item><item><term>Artificial Intelligence (incl. Robotics)</term></item><item><term>Mathematical Logic and Formal Languages</term></item><item><term>Logics and Meanings of Programs</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2008">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-20">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/9B9B6722B6D98E85B9A749F3660D735BBD244882/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><SubSeries><SubSeriesInfo><SubSeriesID>1244</SubSeriesID><SubSeriesPrintISSN>0302-9743</SubSeriesPrintISSN><SubSeriesElectronicISSN>1611-3349</SubSeriesElectronicISSN><SubSeriesTitle Language="En">Lecture Notes in Artificial Intelligence</SubSeriesTitle></SubSeriesInfo><SubSeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Jaime</GivenName><GivenName>G.</GivenName><FamilyName>Carbonell</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>J\"org</GivenName><FamilyName>Siekmann</FamilyName></EditorName></Editor></EditorGroup></SubSeriesHeader></SubSeries><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" OutputMedium="All" TocLevels="0"><BookID>978-3-540-88009-7</BookID><BookTitle>Grammatical Inference: Algorithms and Applications</BookTitle><BookSubTitle>9th International Colloquium, ICGI 2008 Saint-Malo, France, September 22-24, 2008 Proceedings</BookSubTitle><BookVolumeNumber>5278</BookVolumeNumber><BookSequenceNumber>5278</BookSequenceNumber><BookDOI>10.1007/978-3-540-88009-7</BookDOI><BookTitleID>182834</BookTitleID><BookPrintISBN>978-3-540-88008-0</BookPrintISBN><BookElectronicISBN>978-3-540-88009-7</BookElectronicISBN><BookChapterCount>29</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I21017" Priority="1" Type="Secondary">Artificial Intelligence (incl. Robotics)</BookSubject><BookSubject Code="I16048" Priority="2" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><BookSubject Code="I1603X" Priority="3" Type="Secondary">Logics and Meanings of Programs</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Alexander</GivenName><FamilyName>Clark</FamilyName></EditorName><Contact><Email>alexc@cs.rhul.ac.uk</Email></Contact></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>François</GivenName><FamilyName>Coste</FamilyName></EditorName><Contact><Email>Francois.Coste@irisa.fr</Email></Contact></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Laurent</GivenName><FamilyName>Miclet</FamilyName></EditorName><Contact><Email>miclet@enssat.fr</Email></Contact></Editor></EditorGroup></BookHeader><Part ID="Part1"><PartInfo TocLevels="0"><PartID>1</PartID><PartSequenceNumber>1</PartSequenceNumber><PartTitle>Regular Papers</PartTitle><PartChapterCount>21</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Grammatical Inference: Algorithms and Applications</BookTitle></PartContext></PartInfo><Chapter ID="Chap9" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>9</ChapterID><ChapterDOI>10.1007/978-3-540-88009-7_9</ChapterDOI><ChapterSequenceNumber>9</ChapterSequenceNumber><ChapterTitle Language="En">A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness</ChapterTitle><ChapterFirstPage>111</ChapterFirstPage><ChapterLastPage>124</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</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>1</PartID><BookID>978-3-540-88009-7</BookID><BookTitle>Grammatical Inference: Algorithms and Applications</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Anna</GivenName><FamilyName>Kasprzik</FamilyName></AuthorName></Author><Affiliation ID="Aff1"><OrgName>University of Trier</OrgName><OrgAddress><Country> </Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>We generalize a learning algorithm by Drewes and Högberg [1] for regular tree languages based on a learning model proposed by Angluin [2] to recognizable tree languages of arbitrarily many dimensions, so-called multi-dimensional trees. Trees over multi-dimensional tree domains have been defined by Rogers [3,4]. However, since the algorithm by Drewes and Högberg relies on classical finite state automata, these structures have to be represented in another form to make them a suitable input for the algorithm: We give a new representation for multi-dimensional trees which establishes them as a direct generalization of classical trees over a partitioned alphabet, and show that with this notation Drewes’ and Högberg’s algorithm is able to learn tree languages of arbitrarily many dimensions. Via the correspondence between trees and string languages (“yield operation”) this is equivalent to the statement that this way even some string language classes beyond context-freeness have become learnable with respect to Angluin’s learning model as well.</Para></Abstract><KeywordGroup Language="En"><Heading>Keywords</Heading><Keyword>MAT learning</Keyword><Keyword>multi-dimensional trees</Keyword><Keyword>finite-state</Keyword></KeywordGroup></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness</title></titleInfo><name type="personal"><namePart type="given">Anna</namePart><namePart type="family">Kasprzik</namePart><affiliation>University of Trier</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">2008</dateIssued><copyrightDate encoding="w3cdtf">2008</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 generalize a learning algorithm by Drewes and Högberg [1] for regular tree languages based on a learning model proposed by Angluin [2] to recognizable tree languages of arbitrarily many dimensions, so-called multi-dimensional trees. Trees over multi-dimensional tree domains have been defined by Rogers [3,4]. However, since the algorithm by Drewes and Högberg relies on classical finite state automata, these structures have to be represented in another form to make them a suitable input for the algorithm: We give a new representation for multi-dimensional trees which establishes them as a direct generalization of classical trees over a partitioned alphabet, and show that with this notation Drewes’ and Högberg’s algorithm is able to learn tree languages of arbitrarily many dimensions. Via the correspondence between trees and string languages (“yield operation”) this is equivalent to the statement that this way even some string language classes beyond context-freeness have become learnable with respect to Angluin’s learning model as well.</abstract><relatedItem type="host"><titleInfo><title>Grammatical Inference: Algorithms and Applications</title><subTitle>9th International Colloquium, ICGI 2008 Saint-Malo, France, September 22-24, 2008 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Alexander</namePart><namePart type="family">Clark</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">François</namePart><namePart type="family">Coste</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Laurent</namePart><namePart type="family">Miclet</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2008</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="I21017">Artificial Intelligence (incl. Robotics)</topic><topic authority="SpringerSubjectCodes" authorityURI="I16048">Mathematical Logic and Formal Languages</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic></subject><identifier type="DOI">10.1007/978-3-540-88009-7</identifier><identifier type="ISBN">978-3-540-88008-0</identifier><identifier type="eISBN">978-3-540-88009-7</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">182834</identifier><identifier type="BookID">978-3-540-88009-7</identifier><identifier type="BookChapterCount">29</identifier><identifier type="BookVolumeNumber">5278</identifier><identifier type="BookSequenceNumber">5278</identifier><identifier type="PartChapterCount">21</identifier><part><date>2008</date><detail type="part"><title>Regular Papers</title></detail><detail type="volume"><number>5278</number><caption>vol.</caption></detail><extent unit="pages"><start>111</start><end>124</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><originInfo><copyrightDate encoding="w3cdtf">2008</copyrightDate><issuance>serial</issuance></originInfo><relatedItem type="constituent"><titleInfo><title>Lecture Notes in Artificial Intelligence</title></titleInfo><name type="personal"><namePart type="given">Jaime</namePart><namePart type="given">G.</namePart><namePart type="family">Carbonell</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J\"org</namePart><namePart type="family">Siekmann</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Alexander</namePart><namePart type="family">Clark</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">François</namePart><namePart type="family">Coste</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Laurent</namePart><namePart type="family">Miclet</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="sub-series"></genre><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SubSeriesID">1244</identifier></relatedItem><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><identifier type="istex">9B9B6722B6D98E85B9A749F3660D735BBD244882</identifier><identifier type="DOI">10.1007/978-3-540-88009-7_9</identifier><identifier type="ChapterID">9</identifier><identifier type="ChapterID">Chap9</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2008</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</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 001A91 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001A91 | 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:9B9B6722B6D98E85B9A749F3660D735BBD244882
|texte= A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness
}}
| This area was generated with Dilib version V0.6.31. |  |