%
% GENERATED FROM https://www.coli.uni-saarland.de
%    by   : anonymous
%    IP   : coli2006.lst.uni-saarland.de
%    at   : Mon, 05 Feb 2024 15:43:15 +0100 GMT
%    
% Selection : Reference #714
%




@InProceedings{Koller_et_al:2000,
      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 = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/poly-dom.ps.gz},
      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 Koller:2000:PTF.ps}
}