Serveur d'exploration sur la recherche en informatique en Lorraine

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Learning Tree Languages from Positive Examples and Membership Queries

Identifieur interne : 002505 ( Istex/Curation ); précédent : 002504; suivant : 002506

Learning Tree Languages from Positive Examples and Membership Queries

Auteurs : Jérôme Besombes [France] ; Jean-Yves Marion [France]

Source :

RBID : ISTEX:9ED8A39B6A7395F13C3FC3DE8F07901FA48F8656

Abstract

Abstract: We investigate regular tree languages exact learning from positive examples and membership queries. Input data are trees of the language to infer. The learner computes new trees from the inputs and asks to the oracle whether or not they belong to the language. From the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. This paradigm was introduced by Angluin in the seminal work [1] for the case of regular word language. Neither negative examples, equivalence queries nor counter examples are allowed in this paradigm. We describe an efficient algorithm which is polynomial in the size of the examples for learning the whole class of regular tree languages. The convergence is insured when the set of examples contains a representative sample of the language to guess. A finite subset $\mathcal{E}$ of a regular tree language $\mathcal{L}$ is representative for $\mathcal{L}$ if every transition of the minimal tree automaton for $\mathcal{L}$ is used at least once for the derivation of an element of the set $\mathcal{E}$ .

Url:
DOI: 10.1007/978-3-540-30215-5_33

Links toward previous steps (curation, corpus...)


Links to Exploration step

ISTEX:9ED8A39B6A7395F13C3FC3DE8F07901FA48F8656

Le document en format XML

<record>
<TEI wicri:istexFullTextTei="biblStruct">
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="en">Learning Tree Languages from Positive Examples and Membership Queries</title>
<author>
<name sortKey="Besombes, Jerome" sort="Besombes, Jerome" uniqKey="Besombes J" first="Jérôme" last="Besombes">Jérôme Besombes</name>
<affiliation wicri:level="1">
<mods:affiliation>LORIA – INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique, 54602, Villers-lès-Nancy, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LORIA – INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique, 54602, Villers-lès-Nancy</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: Jerome.Besombes@loria.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name>
<affiliation wicri:level="1">
<mods:affiliation>LORIA – INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique, 54602, Villers-lès-Nancy, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LORIA – INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique, 54602, Villers-lès-Nancy</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: Jean-Yves.Marion@loria.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:9ED8A39B6A7395F13C3FC3DE8F07901FA48F8656</idno>
<date when="2004" year="2004">2004</date>
<idno type="doi">10.1007/978-3-540-30215-5_33</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-JR3SFL3B-0/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002536</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002536</idno>
<idno type="wicri:Area/Istex/Curation">002505</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title level="a" type="main" xml:lang="en">Learning Tree Languages from Positive Examples and Membership Queries</title>
<author>
<name sortKey="Besombes, Jerome" sort="Besombes, Jerome" uniqKey="Besombes J" first="Jérôme" last="Besombes">Jérôme Besombes</name>
<affiliation wicri:level="1">
<mods:affiliation>LORIA – INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique, 54602, Villers-lès-Nancy, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LORIA – INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique, 54602, Villers-lès-Nancy</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: Jerome.Besombes@loria.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name>
<affiliation wicri:level="1">
<mods:affiliation>LORIA – INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique, 54602, Villers-lès-Nancy, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LORIA – INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique, 54602, Villers-lès-Nancy</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: Jean-Yves.Marion@loria.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series>
<title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt>
<idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc>
<textClass></textClass>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="en">Abstract: We investigate regular tree languages exact learning from positive examples and membership queries. Input data are trees of the language to infer. The learner computes new trees from the inputs and asks to the oracle whether or not they belong to the language. From the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. This paradigm was introduced by Angluin in the seminal work [1] for the case of regular word language. Neither negative examples, equivalence queries nor counter examples are allowed in this paradigm. We describe an efficient algorithm which is polynomial in the size of the examples for learning the whole class of regular tree languages. The convergence is insured when the set of examples contains a representative sample of the language to guess. A finite subset $\mathcal{E}$ of a regular tree language $\mathcal{L}$ is representative for $\mathcal{L}$ if every transition of the minimal tree automaton for $\mathcal{L}$ is used at least once for the derivation of an element of the set $\mathcal{E}$ .</div>
</front>
</TEI>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002505 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 002505 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Istex
   |étape=   Curation
   |type=    RBID
   |clé=     ISTEX:9ED8A39B6A7395F13C3FC3DE8F07901FA48F8656
   |texte=   Learning Tree Languages from Positive Examples and Membership Queries
}}

Wicri

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022