Change search
ReferencesLink to record
Permanent link

Direct link
An inference algorithm for regular tree languages
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Formal and natural languages)
2011 (English)In: Natural Language Engineering, ISSN 1351-3249, E-ISSN 1469-8110, Vol. 17, no 2, 203-219 p.Article in journal (Refereed) Published
Abstract [en]

We present a randomized inference algorithm for regular tree languages. The algorithm takes as input two disjoint finite nonempty sets of trees P and N, and outputs a nondeterministic finite tree automaton that accepts every tree in P, and rejects every tree in N. The output automaton typically represents a non-trivial generalisation of the examples given in P and N. To obtain compact output automata, we use a heuristics similar to bisimulation minimization.The algorithm has time complexity of O(|N||P|^2). Experiments are conducted on a prototype implementation, and the empirical results appear to second the theoretical results.

Place, publisher, year, edition, pages
Cambridge: Cambridge University Press , 2011. Vol. 17, no 2, 203-219 p.
Keyword [en]
algorithmic learning, natural language processing
National Category
Computer Science
Research subject
Computing Science
URN: urn:nbn:se:umu:diva-40991DOI: 10.1017/S1351324911000064OAI: diva2:404089
Tree series in language technologies
Available from: 2011-03-15 Created: 2011-03-15 Last updated: 2011-10-19Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Högberg, Johanna
By organisation
Department of Computing Science
In the same journal
Natural Language Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 66 hits
ReferencesLink to record
Permanent link

Direct link