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, 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
2010. 276-284 p.
Language Technology (Computational Linguistics) Language Technology (Computational Linguistics)
Research subject Computational Linguistics
IdentifiersURN: urn:nbn:se:uu:diva-129367OAI: oai:DiVA.org:uu-129367DiVA: diva2:343099
The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics