IndexBrowse   BibliographiesMy selection
 Search: in   (word length ≥ 3)
Reference no #714   Download bibtex file Type :   Html | Bib | Both
    Created: 2007-12-12 11:30:33
714 Add to my selection
      AUTHOR = {Koller, Alexander and Mehlhorn, Kurt and Niehren, Joachim},
      TITLE = {A Polynomial-Time Fragment of Dominance Constraints},
      YEAR = {2000},
      BOOKTITLE = {38th Annual Meeting of the Association of Computational Linguistics (ACL '00), October 1-8},
      ADDRESS = {Hong Kong},
      URL = {},
      ABSTRACT = {Dominance constraints are a logical language for describing trees that is widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify emphnormal dominance constraints, a natural fragment whose satisfiability problem we show to be in polynomial time. We present a quadratic satisfiability algorithm and use it in another algorithm that enumerates solutions efficiently. Our result is useful for various applications of dominance constraints and related formalisms.},
      ANNOTE = {COLIURL : Koller:2000:PTF.pdf}
Last modified: Thu October 16 2014 19:11:34         BibAdmin