Efficient techniques for parsing with tree automata

Jonas Groschwitz; Alexander Koller; Mark Johnson

doi:10.18653/v1/p16-1192

Efficient techniques for parsing with tree automata

Jonas Groschwitz, Alexander Koller, Mark Johnson

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

7 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	54th Annual Meeting of the Association for Computational Linguistics, ACL 2016 - Long Papers
Publisher	Association for Computational Linguistics (ACL)
Pages	2042-2051
Number of pages	10
Volume	4
ISBN (Electronic)	9781510827585
DOIs	https://doi.org/10.18653/v1/p16-1192
Publication status	Published - 2016
Event	54th Annual Meeting of the Association for Computational Linguistics, ACL 2016 - Berlin, Germany Duration: 7 Aug 2016 → 12 Aug 2016

Other

Other	54th Annual Meeting of the Association for Computational Linguistics, ACL 2016
Country/Territory	Germany
City	Berlin
Period	7/08/16 → 12/08/16

Bibliographical note

Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

Access to Document

10.18653/v1/p16-1192Licence: CC BY

Cite this

@inproceedings{4b953b39fc82496dbf4c3aa9e8cfa649,

title = "Efficient techniques for parsing with tree automata",

abstract = "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.",

author = "Jonas Groschwitz and Alexander Koller and Mark Johnson",

note = "Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher. ; 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016 ; Conference date: 07-08-2016 Through 12-08-2016",

year = "2016",

doi = "10.18653/v1/p16-1192",

language = "English",

volume = "4",

pages = "2042--2051",

booktitle = "54th Annual Meeting of the Association for Computational Linguistics, ACL 2016 - Long Papers",

publisher = "Association for Computational Linguistics (ACL)",

}

Groschwitz, J, Koller, A & Johnson, M 2016, Efficient techniques for parsing with tree automata. in 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016 - Long Papers. vol. 4, Association for Computational Linguistics (ACL), pp. 2042-2051, 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, Berlin, Germany, 7/08/16. https://doi.org/10.18653/v1/p16-1192

Efficient techniques for parsing with tree automata. / Groschwitz, Jonas; Koller, Alexander; Johnson, Mark.
54th Annual Meeting of the Association for Computational Linguistics, ACL 2016 - Long Papers. Vol. 4 Association for Computational Linguistics (ACL), 2016. p. 2042-2051.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Efficient techniques for parsing with tree automata

AU - Groschwitz, Jonas

AU - Koller, Alexander

AU - Johnson, Mark

N1 - Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85012014448&partnerID=8YFLogxK

U2 - 10.18653/v1/p16-1192

DO - 10.18653/v1/p16-1192

M3 - Conference proceeding contribution

AN - SCOPUS:85012014448

VL - 4

SP - 2042

EP - 2051

BT - 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016 - Long Papers

PB - Association for Computational Linguistics (ACL)

T2 - 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016

Y2 - 7 August 2016 through 12 August 2016

ER -

Efficient techniques for parsing with tree automata

Abstract

Other

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this