Learning tree languages from positive examples and membership queries
Identifieur interne :
000426 ( PascalFrancis/Curation );
précédent :
000425;
suivant :
000427
Learning tree languages from positive examples and membership queries
Auteurs : Jérome Besombes [
France] ;
Jean-Yves Marion [
France]
Source :
-
Lecture notes in computer science [ 0302-9743 ] ; 2004.
RBID : Pascal:04-0542613
Descripteurs français
- Pascal (Inist)
- Algorithme apprentissage,
Intelligence artificielle,
Interrogation base donnée,
Langage rationnel,
Apprentissage à partir d'exemple,
Classe langage,
Automate arbre,
Oracle,
Grammaire,
Langue cible,
Arbre minimal,
Méthode polynomiale,
Langage régulier.
- Wicri :
English descriptors
- KwdEn :
- Artificial intelligence,
Database query,
Grammar,
Language class,
Learning algorithm,
Learning by example,
Minimal tree,
Oracle,
Polynomial method,
Regular language,
Target language,
Tree automaton.
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 ε of a regular tree language £ is representative for L if every transition of the minimal tree automaton for L is used at least once for the derivation of an element of the set ε.
pA |
A01 | 01 | 1 | | @0 0302-9743 |
---|
A05 | | | | @2 3244 |
---|
A08 | 01 | 1 | ENG | @1 Learning tree languages from positive examples and membership queries |
---|
A09 | 01 | 1 | ENG | @1 ALT 2004 : algorithmic learning theory : Padova, 2-5 October 2004 |
---|
A11 | 01 | 1 | | @1 BESOMBES (Jérome) |
---|
A11 | 02 | 1 | | @1 MARION (Jean-Yves) |
---|
A12 | 01 | 1 | | @1 BEN-DAVID (Shai) @9 ed. |
---|
A12 | 02 | 1 | | @1 CASE (John) @9 ed. |
---|
A12 | 03 | 1 | | @1 MARUOKA (Akira) @9 ed. |
---|
A14 | 01 | | | @1 LORIA - INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique @2 54602 Villers-lès-Nancy @3 FRA @Z 1 aut. @Z 2 aut. |
---|
A20 | | | | @1 440-453 |
---|
A21 | | | | @1 2004 |
---|
A23 | 01 | | | @0 ENG |
---|
A26 | 01 | | | @0 3-540-23356-3 |
---|
A43 | 01 | | | @1 INIST @2 16343 @5 354000124353360320 |
---|
A44 | | | | @0 0000 @1 © 2004 INIST-CNRS. All rights reserved. |
---|
A45 | | | | @0 23 ref. |
---|
A47 | 01 | 1 | | @0 04-0542613 |
---|
A60 | | | | @1 P @2 C |
---|
A61 | | | | @0 A |
---|
A64 | 01 | 1 | | @0 Lecture notes in computer science |
---|
A66 | 01 | | | @0 DEU |
---|
C01 | 01 | | ENG | @0 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 ε of a regular tree language £ is representative for L if every transition of the minimal tree automaton for L is used at least once for the derivation of an element of the set ε. |
---|
C02 | 01 | X | | @0 001D02A05 |
---|
C02 | 02 | X | | @0 001D02C02 |
---|
C03 | 01 | X | FRE | @0 Algorithme apprentissage @5 01 |
---|
C03 | 01 | X | ENG | @0 Learning algorithm @5 01 |
---|
C03 | 01 | X | SPA | @0 Algoritmo aprendizaje @5 01 |
---|
C03 | 02 | X | FRE | @0 Intelligence artificielle @5 02 |
---|
C03 | 02 | X | ENG | @0 Artificial intelligence @5 02 |
---|
C03 | 02 | X | SPA | @0 Inteligencia artificial @5 02 |
---|
C03 | 03 | X | FRE | @0 Interrogation base donnée @5 06 |
---|
C03 | 03 | X | ENG | @0 Database query @5 06 |
---|
C03 | 03 | X | SPA | @0 Interrogación base datos @5 06 |
---|
C03 | 04 | X | FRE | @0 Langage rationnel @5 07 |
---|
C03 | 04 | X | ENG | @0 Regular language @5 07 |
---|
C03 | 04 | X | SPA | @0 Lenguaje racional @5 07 |
---|
C03 | 05 | 3 | FRE | @0 Apprentissage à partir d'exemple @5 08 |
---|
C03 | 05 | 3 | ENG | @0 Learning by example @5 08 |
---|
C03 | 06 | X | FRE | @0 Classe langage @5 09 |
---|
C03 | 06 | X | ENG | @0 Language class @5 09 |
---|
C03 | 06 | X | SPA | @0 Clase lenguaje @5 09 |
---|
C03 | 07 | X | FRE | @0 Automate arbre @5 10 |
---|
C03 | 07 | X | ENG | @0 Tree automaton @5 10 |
---|
C03 | 07 | X | SPA | @0 Autómata árbol @5 10 |
---|
C03 | 08 | X | FRE | @0 Oracle @5 18 |
---|
C03 | 08 | X | ENG | @0 Oracle @5 18 |
---|
C03 | 09 | X | FRE | @0 Grammaire @5 19 |
---|
C03 | 09 | X | ENG | @0 Grammar @5 19 |
---|
C03 | 09 | X | SPA | @0 Gramática @5 19 |
---|
C03 | 10 | X | FRE | @0 Langue cible @5 20 |
---|
C03 | 10 | X | ENG | @0 Target language @5 20 |
---|
C03 | 10 | X | SPA | @0 Lengua blanco @5 20 |
---|
C03 | 11 | X | FRE | @0 Arbre minimal @5 21 |
---|
C03 | 11 | X | ENG | @0 Minimal tree @5 21 |
---|
C03 | 11 | X | SPA | @0 Arbol mínimo @5 21 |
---|
C03 | 12 | X | FRE | @0 Méthode polynomiale @5 23 |
---|
C03 | 12 | X | ENG | @0 Polynomial method @5 23 |
---|
C03 | 12 | X | SPA | @0 Método polinomial @5 23 |
---|
C03 | 13 | X | FRE | @0 Langage régulier @4 CD @5 96 |
---|
C03 | 13 | X | ENG | @0 Regular language @4 CD @5 96 |
---|
C03 | 13 | X | SPA | @0 Lenguaje regular @4 CD @5 96 |
---|
N21 | | | | @1 306 |
---|
N44 | 01 | | | @1 OTO |
---|
N82 | | | | @1 OTO |
---|
|
pR |
A30 | 01 | 1 | ENG | @1 International conference on algorithmic learning theory @2 15 @3 Padova ITA @4 2004-10-02 |
---|
|
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000615
Links to Exploration step
Pascal:04-0542613
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Learning tree languages from positive examples and membership queries</title>
<author><name sortKey="Besombes, Jerome" sort="Besombes, Jerome" uniqKey="Besombes J" first="Jérome" last="Besombes">Jérome Besombes</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LORIA - INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>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"><inist:fA14 i1="01"><s1>LORIA - INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">04-0542613</idno>
<date when="2004">2004</date>
<idno type="stanalyst">PASCAL 04-0542613 INIST</idno>
<idno type="RBID">Pascal:04-0542613</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000615</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000426</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Learning tree languages from positive examples and membership queries</title>
<author><name sortKey="Besombes, Jerome" sort="Besombes, Jerome" uniqKey="Besombes J" first="Jérome" last="Besombes">Jérome Besombes</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LORIA - INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>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"><inist:fA14 i1="01"><s1>LORIA - INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="2004">2004</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Artificial intelligence</term>
<term>Database query</term>
<term>Grammar</term>
<term>Language class</term>
<term>Learning algorithm</term>
<term>Learning by example</term>
<term>Minimal tree</term>
<term>Oracle</term>
<term>Polynomial method</term>
<term>Regular language</term>
<term>Target language</term>
<term>Tree automaton</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Algorithme apprentissage</term>
<term>Intelligence artificielle</term>
<term>Interrogation base donnée</term>
<term>Langage rationnel</term>
<term>Apprentissage à partir d'exemple</term>
<term>Classe langage</term>
<term>Automate arbre</term>
<term>Oracle</term>
<term>Grammaire</term>
<term>Langue cible</term>
<term>Arbre minimal</term>
<term>Méthode polynomiale</term>
<term>Langage régulier</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Intelligence artificielle</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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 ε of a regular tree language £ is representative for L if every transition of the minimal tree automaton for L is used at least once for the derivation of an element of the set ε.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01>
<fA05><s2>3244</s2>
</fA05>
<fA08 i1="01" i2="1" l="ENG"><s1>Learning tree languages from positive examples and membership queries</s1>
</fA08>
<fA09 i1="01" i2="1" l="ENG"><s1>ALT 2004 : algorithmic learning theory : Padova, 2-5 October 2004</s1>
</fA09>
<fA11 i1="01" i2="1"><s1>BESOMBES (Jérome)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>MARION (Jean-Yves)</s1>
</fA11>
<fA12 i1="01" i2="1"><s1>BEN-DAVID (Shai)</s1>
<s9>ed.</s9>
</fA12>
<fA12 i1="02" i2="1"><s1>CASE (John)</s1>
<s9>ed.</s9>
</fA12>
<fA12 i1="03" i2="1"><s1>MARUOKA (Akira)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01"><s1>LORIA - INPL, Ecole Nationale Supérieure des Mines de Nancy, 615, rue du jardin botanique</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</fA14>
<fA20><s1>440-453</s1>
</fA20>
<fA21><s1>2004</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA26 i1="01"><s0>3-540-23356-3</s0>
</fA26>
<fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000124353360320</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2004 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>23 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>04-0542613</s0>
</fA47>
<fA60><s1>P</s1>
<s2>C</s2>
</fA60>
<fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64>
<fA66 i1="01"><s0>DEU</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>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 ε of a regular tree language £ is representative for L if every transition of the minimal tree automaton for L is used at least once for the derivation of an element of the set ε.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001D02C02</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Algorithme apprentissage</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Learning algorithm</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Algoritmo aprendizaje</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Intelligence artificielle</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Artificial intelligence</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Inteligencia artificial</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Interrogation base donnée</s0>
<s5>06</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Database query</s0>
<s5>06</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Interrogación base datos</s0>
<s5>06</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Langage rationnel</s0>
<s5>07</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Regular language</s0>
<s5>07</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Lenguaje racional</s0>
<s5>07</s5>
</fC03>
<fC03 i1="05" i2="3" l="FRE"><s0>Apprentissage à partir d'exemple</s0>
<s5>08</s5>
</fC03>
<fC03 i1="05" i2="3" l="ENG"><s0>Learning by example</s0>
<s5>08</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Classe langage</s0>
<s5>09</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Language class</s0>
<s5>09</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Clase lenguaje</s0>
<s5>09</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Automate arbre</s0>
<s5>10</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Tree automaton</s0>
<s5>10</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Autómata árbol</s0>
<s5>10</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Oracle</s0>
<s5>18</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG"><s0>Oracle</s0>
<s5>18</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Grammaire</s0>
<s5>19</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG"><s0>Grammar</s0>
<s5>19</s5>
</fC03>
<fC03 i1="09" i2="X" l="SPA"><s0>Gramática</s0>
<s5>19</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE"><s0>Langue cible</s0>
<s5>20</s5>
</fC03>
<fC03 i1="10" i2="X" l="ENG"><s0>Target language</s0>
<s5>20</s5>
</fC03>
<fC03 i1="10" i2="X" l="SPA"><s0>Lengua blanco</s0>
<s5>20</s5>
</fC03>
<fC03 i1="11" i2="X" l="FRE"><s0>Arbre minimal</s0>
<s5>21</s5>
</fC03>
<fC03 i1="11" i2="X" l="ENG"><s0>Minimal tree</s0>
<s5>21</s5>
</fC03>
<fC03 i1="11" i2="X" l="SPA"><s0>Arbol mínimo</s0>
<s5>21</s5>
</fC03>
<fC03 i1="12" i2="X" l="FRE"><s0>Méthode polynomiale</s0>
<s5>23</s5>
</fC03>
<fC03 i1="12" i2="X" l="ENG"><s0>Polynomial method</s0>
<s5>23</s5>
</fC03>
<fC03 i1="12" i2="X" l="SPA"><s0>Método polinomial</s0>
<s5>23</s5>
</fC03>
<fC03 i1="13" i2="X" l="FRE"><s0>Langage régulier</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="13" i2="X" l="ENG"><s0>Regular language</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="13" i2="X" l="SPA"><s0>Lenguaje regular</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fN21><s1>306</s1>
</fN21>
<fN44 i1="01"><s1>OTO</s1>
</fN44>
<fN82><s1>OTO</s1>
</fN82>
</pA>
<pR><fA30 i1="01" i2="1" l="ENG"><s1>International conference on algorithmic learning theory</s1>
<s2>15</s2>
<s3>Padova ITA</s3>
<s4>2004-10-02</s4>
</fA30>
</pR>
</standard>
</inist>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000426 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000426 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Curation
|type= RBID
|clé= Pascal:04-0542613
|texte= Learning tree languages from positive examples and membership queries
}}
| 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 | ![](Common/icons/LogoDilib.gif) |