2010 | OriginalPaper | Buchkapitel
Minimizing Weighted Tree Grammars Using Simulation
verfasst von : Andreas Maletti
Erschienen in: Finite-State Methods and Natural Language Processing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Weighted tree grammars (for short: WTG) are an extension of weighted context-free grammars that generate trees instead of strings. They can be used in natural language parsing to directly generate the parse tree of a sentence or to encode the set of all parse trees of a sentence. Two types of simulations for WTG over idempotent, commutative semirings are introduced. They generalize the existing notions of simulation and bisimulation for WTG. Both simulations can be used to reduce the size of WTG while preserving the semantics, and are thus an important tool in toolkits. Since the new notions are more general than the existing ones, they yield the best reduction rates achievable by all minimization procedures that rely on simulation or bisimulation. However, the existing notions might allow faster minimization.