@inproceedings{chappelier-etal-2002-polynomial,
    title = "Polynomial Tree Substitution Grammars: Characterization and New Examples",
    author = "Chappelier, Jean-C{\'e}dric  and
      Rajman, Martin  and
      Rozenknop, Antoine",
    editor = "Pierrel, Jean-Marie",
    booktitle = "Actes de la 9{\`e}me conf{\'e}rence sur le Traitement Automatique des Langues Naturelles. Posters",
    month = jun,
    year = "2002",
    address = "Nancy, France",
    publisher = "ATALA",
    url = "https://preview.aclanthology.org/fix-sig-urls/2002.jeptalnrecital-poster.7/",
    pages = "357--362",
    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."
}