Article contents
Learning tree languages from text
Published online by Cambridge University Press: 25 September 2007
Abstract
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.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 41 , Issue 4 , October 2007 , pp. 351 - 374
- Copyright
- © EDP Sciences, 2007
References
- 1
- Cited by