Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems
2010 (English)In: Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics: Proceedings of the Main Conference, Stroudsburg, PA, USA: Association for Computational Linguistics, 2010, 276-284 p.Conference paper (Refereed)
The use of well-nested linear context-free rewriting systems has been empirically motivated for modeling of the syntax of languages with discontinuous constituents or relatively free word order. We present a chart-based parsing algorithm that asymptotically improves the known running time upper bound for this class of rewriting systems. Our result is obtained through a linear space construction of a binary normal form for the grammar at hand.
Place, publisher, year, edition, pages
Stroudsburg, PA, USA: Association for Computational Linguistics, 2010. 276-284 p.
Language Technology (Computational Linguistics)
Research subject Computational Linguistics
IdentifiersURN: urn:nbn:se:liu:diva-100285ISBN: 978-1-932432-65-7OAI: oai:DiVA.org:liu-100285DiVA: diva2:661511
The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Los Angeles, California, USA, June 2–4, 2010