%
% GENERATED FROM https://www.coli.uni-saarland.de
%    by   : anonymous
%    IP   : coli2006.lst.uni-saarland.de
%    at   : Mon, 05 Feb 2024 15:42:54 +0100 GMT
%    
% Selection : Author: Kurt_Mehlhorn
%




@InProceedings{Althaus_et_al:2001,
      AUTHOR = {Althaus, Ernst and Duchier, Denys and Koller, Alexander and Mehlhorn, Kurt and Niehren, Joachim and Thiel, Sven},
      TITLE = {An Efficient Algorithm for the Configuration Problem of Dominance Graphs},
      YEAR = {2001},
      BOOKTITLE = {12th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 7-9},
      ADDRESS = {Washington D.C., USA},
      PUBLISHER = {ACM Press},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/dom-graph.ps.gz},
      ABSTRACT = {Dominance constraints are logical tree descriptions originating from automata theory that have multiple applications in computational linguistics. The satisfiability problem of dominance constraints is NP-complete. In most applications, however, only emph(normal) dominance constraints are used. The satisfiability problem of normal dominance constraints can be reduced in linear time to the configuration problem of dominance graphs, as shown recently. In this paper, we give a polynomial time algorithm testing configurability of dominance graphs (and thus satisfiability of normal dominance constraints). Previous to our work no polynomial time algorithms were known.},
      ANNOTE = {COLIURL : Althaus:2001:EAC.pdf Althaus:2001:EAC.ps}
}

@Article{Althaus_et_al:2003,
      AUTHOR = {Althaus, Ernst and Duchier, Denys and Koller, Alexander and Mehlhorn, Kurt and Niehren, Joachim and Thiel, Sven},
      TITLE = {An Efficient Graph Algorithm for Dominance Constraints},
      YEAR = {2003},
      JOURNAL = {Journal of Algorithms},
      VOLUME = {48},
      PAGES = {194--219},
      URL = {https://www.coli.uni-saarland.de/~koller/papers/eff-dom.ps.gz},
      ABSTRACT = {Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal dominance constraints and present an efficient graph algorithm for testing their satisfiablity in deterministic polynomial time. Previously, no polynomial time algorithm was known.},
      ANNOTE = {COLIURL : Althaus:19xx:EGA.pdf Althaus:19xx:EGA.ps}
}

@InProceedings{Erk:2000,
      AUTHOR = {Erk, Katrin},
      TITLE = {Die Verarbeitung von Parallelismus-Constraints},
      YEAR = {2000},
      BOOKTITLE = {Informatik 2000 - 30. Jahrestagung der Gesellschaft für Informatik, 19.-22. September},
      EDITOR = {Mehlhorn, Kurt and Snelting, G.},
      SERIES = {Informatik Aktuell},
      ADDRESS = {Berlin, Germany},
      PUBLISHER = {Springer},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/GI00.ps.gz},
      ABSTRACT = {Parallelismus-Constraints sind partielle Beschreibungen von Bäumen. Wir verwenden sie als Repräsentationsformalismus in der unterspezifizierten natürlichsprachlichen Semantik. Parallelismus-Constraints sind gleichmächtig wie Kontext-Unifikation, deren Entscheidbarkeit ein bekanntes offenes Problem ist. Dieser Text beschreibt ein Semi-Entscheidungs-Verfahren für Parallelismus-Constraints und eine erste Implementierung. Anders als alle bekannten Verfahren für Kontext-Unifikation terminiert diese Prozedur für Dominanz-Constraints, eine für die linguistische Anwendung wichtige Teilklasse.},
      ANNOTE = {COLIURL : Erk:2000:VPC.pdf Erk:2000:VPC.ps}
}

@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}
}