Efficient techniques for parsing with tree automata

Groschwitz, Jonas, Koller, Alexander, and Johnson, Mark

In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (ACL), Berlin, 2016.

Parsing for a wide variety of grammar formalisms can be performed by intersecting finite tree automata. However, naive implementations of parsing by intersection are very inefficient. We present techniques that speed up tree-automata-based parsing, to the point that it becomes practically feasible on realistic data when applied to context-free, TAG, and graph parsing. For graph parsing, we obtain the best runtimes in the literature.

Download: Download

BibTeX Entry
@inproceedings{irtg-parsing-16,
	title = {Efficient techniques for parsing with tree automata},
	author = {Groschwitz, Jonas and Koller, Alexander and Johnson, Mark},
	year = {2016},
	booktitle = {Proceedings of the 54th Annual Meeting of the
		Association for Computational Linguistics (ACL)},
	address = {Berlin}
}

Back: Publications