A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness
Identifieur interne : 001974 ( Istex/Curation ); précédent : 001973; suivant : 001975A Learning Algorithm for Multi-dimensional Trees, or: Learning Beyond Context-Freeness
Auteurs : Anna Kasprzik [Allemagne]Source :
- 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 toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001A91
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 wicri:level="4"><mods:affiliation>University of Trier</mods:affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></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><idno type="wicri:Area/Istex/Curation">001974</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 wicri:level="4"><mods:affiliation>University of Trier</mods:affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></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></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001974 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 001974 | 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= Curation
|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. |  |