Abstract
Polynomial Tree Substitution Grammars, a subclass of STSGs for which finding the most probable parse is no longer NP-hard but polynomial, are defined and characterized in terms of general properties on the elementary trees in the grammar. Various sufficient and easy to compute properties for a STSG to be polynomial are presented. The min-max selection principle is shown to be one such sufficient property. In addition, another, new, instance of a sufficient property, based on lexical heads, is presented. The performances of both models are evaluated on several corpora.- Anthology ID:
- 2002.jeptalnrecital-poster.7
- Volume:
- Actes de la 9ème conférence sur le Traitement Automatique des Langues Naturelles. Posters
- Month:
- June
- Year:
- 2002
- Address:
- Nancy, France
- Editor:
- Jean-Marie Pierrel
- Venue:
- JEP/TALN/RECITAL
- SIG:
- Publisher:
- ATALA
- Note:
- Pages:
- 357–362
- Language:
- URL:
- https://aclanthology.org/2002.jeptalnrecital-poster.7
- DOI:
- Cite (ACL):
- Jean-Cédric Chappelier, Martin Rajman, and Antoine Rozenknop. 2002. Polynomial Tree Substitution Grammars: Characterization and New Examples. In Actes de la 9ème conférence sur le Traitement Automatique des Langues Naturelles. Posters, pages 357–362, Nancy, France. ATALA.
- Cite (Informal):
- Polynomial Tree Substitution Grammars: Characterization and New Examples (Chappelier et al., JEP/TALN/RECITAL 2002)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-2/2002.jeptalnrecital-poster.7.pdf