Learning tree languages from text
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 4, pp. 351-374.

Voir la notice de l'article dans Numdam

We study the problem of learning regular tree languages from text. We show that the framework of function distinguishability, as introduced by the author in [Theoret. Comput. Sci. 290 (2003) 1679-1711], can be generalized from the case of string languages towards tree languages. This provides a large source of identifiable classes of regular tree languages. Each of these classes can be characterized in various ways. Moreover, we present a generic inference algorithm with polynomial update time and prove its correctness. In this way, we generalize previous works of Angluin, Sakakibara and ourselves. Moreover, we show that this way all regular tree languages can be approximately identified.

DOI : 10.1051/ita:2007030
Classification : 68Q32, 68Q45 
@article{ITA_2007__41_4_351_0,
     author = {Fernau, Henning},
     title = {Learning tree languages from text},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {351--374},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {4},
     year = {2007},
     doi = {10.1051/ita:2007030},
     zbl = {1144.68031},
     mrnumber = {2377968},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2007030/}
}
TY  - JOUR
AU  - Fernau, Henning
TI  - Learning tree languages from text
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
SP  - 351
EP  - 374
VL  - 41
IS  - 4
PB  - EDP-Sciences
UR  - https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2007030/
DO  - 10.1051/ita:2007030
LA  - en
ID  - ITA_2007__41_4_351_0
ER  - 
%0 Journal Article
%A Fernau, Henning
%T Learning tree languages from text
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2007
%P 351-374
%V 41
%N 4
%I EDP-Sciences
%U https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2007030/
%R 10.1051/ita:2007030
%G en
%F ITA_2007__41_4_351_0
Fernau, Henning. Learning tree languages from text. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 4, pp. 351-374. doi : 10.1051/ita:2007030. https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2007030/

Cité par Sources :