Weighted parsing for grammar-based language models over multioperator monoids

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

We develop a general framework for weighted parsing which is built on top of grammar-based language models and employs multioperator monoids (M-monoids) as weight algebras. It generalizes previous work in that area, e.g., semiring parsing and weighted deductive parsing, and also covers applications outside the classical scope of parsing, e.g., algebraic dynamic programming. More specifically, we introduce weighted RTG-based language models (where RTG stands for regular tree grammar) and define the M-monoid parsing problem. We show an algorithm which is supposed to solve this problem and prove in detail that, for a large class of weighted RTG-based language models, the algorithm terminates and, indeed, solves this problem. We compare our algorithm with semiring parsing and weighted deductive parsing regarding applicability and complexity.

Details

Original languageEnglish
Article number104774
JournalInformation and Computation
Volume281
Publication statusPublished - Dec 2021
Peer-reviewedYes

External IDs

Scopus 85109440756

Keywords

Keywords

  • Weighted parsing, Language model, Formal grammar, Formal grammar, Language model