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




@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{Duchier:1999,
      AUTHOR = {Duchier, Denys},
      TITLE = {Axiomatizing Dependency Parsing using Set Constraints},
      YEAR = {1999},
      BOOKTITLE = {6th Meeting on Mathematics of Language (MOL6), July 23-25},
      PAGES = {115-126},
      ADDRESS = {Orlando, Florida, USA},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/duchier-mol6.ps.gz},
      ABSTRACT = {We propose a new formulation of dependency grammar and develop a corresponding axiomatization of syntactic well-formedness with a natural reading as a concurrent constraint program. We demonstrate the expressivity and effectiveness of set constraints, and describe a treatment of ambiguity with wide applicability. Further, we provide a constraint programming account of dependent disjunctions that is both simple and efficient and additionally provides the benefits of constructive disjunctions. Our approach was implemented in Oz and yields parsers with very good performance for our currently middle scale grammars. Constraint propagation can be observed to be remarkably effective in pruning the search space.},
      ANNOTE = {COLIURL : Duchier:1999:ADP.pdf Duchier:1999:ADP.ps}
}

@InProceedings{Duchier:1999_1,
      AUTHOR = {Duchier, Denys},
      TITLE = {Set Constraints in Computational Linguistics - Solving Tree Descriptions},
      YEAR = {1999},
      BOOKTITLE = {Workshop on Declarative Programming with Sets (DPS '99), September 28},
      PAGES = {91-98},
      ADDRESS = {Paris, France},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/duchier-wdps99.ps.gz},
      ABSTRACT = {We describe our application of set constraints to the problem of finding solutions of tree descriptions. The encoding that turns a description into a CSP is given here in full in an axiomatic style.},
      ANNOTE = {COLIURL : Duchier:1999:SCC.pdf Duchier:1999:SCC.ps}
}

@InProceedings{Duchier:2000,
      AUTHOR = {Duchier, Denys},
      TITLE = {A Model-Eliminative Treatment of Quantifier-Free Tree Descriptions},
      YEAR = {2000},
      BOOKTITLE = {Algebraic Methods in Language Processing (AMILP '00). 16th Twente Workshop on Language Technology (TWLT 16) and 2nd AMAST Workshop, May 20-22},
      PAGES = {55-66},
      EDITOR = {Heylen, D. and Nijholt, Anton and Scollo, G.},
      ADDRESS = {Iowa City, Iowa, USA},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/duchier-amilp.ps.gz},
      ABSTRACT = {Tree descriptions are widely used in computational linguistics for talking and reasoning about trees. For practical applications, it is essential to be able to decide satisfiability and enumerate solutions efficiently. This challenge cannot realistically be met by brute force enumeration. However it can be addressed very effectively by constraint propagation as provided by modern constraint technology. Previously, we studied the conjunctive fragment of tree descriptions and showed how the problem of finding minimal models of a conjunctive tree description could be transformed into a constraint satisfaction problem (CSP) on finite set variables. In this paper, we extend our account to the fragment that admits both negation and disjunction, but still leaves out quantification. Again we provide a reduction to a CSP. While our previous encoding introduced the reader to set constraints and disjunctive propagators, we now extend our arsenal with selection propagators.},
      ANNOTE = {COLIURL : Duchier:2000:MET.pdf Duchier:2000:MET.ps}
}

@InProceedings{Duchier:2000_1,
      AUTHOR = {Duchier, Denys},
      TITLE = {Constraint Programming for Natural Language Processing},
      YEAR = {2000},
      BOOKTITLE = {European Summer School in Logic, Language, and Information (ESSLLI '00), August 6-18},
      ADDRESS = {Birmingham, England},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/duchier-esslli2000.ps.gz},
      ABSTRACT = {This course demonstrates how constraint programming can be used effectively in practice, for linguistic applications. It shows how many forms of ambiguity arising in linguistic can be represented compactly and elegantly, and processed efficiently with constraints. A key idea to derive the most benefit from constraint propagation is that intended models should be characterized as solutions of emphConstraint Satisfaction Problems (CSPs) rather than defined inductively or in a generative fashion. We examine several topics in detail: encodings of finite domains, tree descriptions using dominance constraints, and parsing with dependency grammars. In each case, we present a formal characterization of the problem as a CSP and illustrate how to derive a corresponding constraint program. The course includes 4 complete interactive applications written in Oz, with full code supplied. Through these programmatic vignettes the reader is exposed to the practice of constraint programming with emphfinite domain and emphfinite set variables, and introduced to some of the more powerful types of constraints available today, such as reified constraints, disjunctive propagators, and selection constraints.},
      ANNOTE = {COLIURL : Duchier:2000:CPN.pdf Duchier:2000:CPN.ps}
}

@Article{Duchier:2002,
      AUTHOR = {Duchier, Denys},
      TITLE = {Dominance Constraints with Boolean Connectives: A Model-Eliminative Treatment},
      YEAR = {2002},
      JOURNAL = {Journal of Theoretical Computer Science},
      VOLUME = {293},
      NUMBER = {2},
      PAGES = {321-343},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/duchier-dcbc2000.ps.gz},
      ABSTRACT = {Dominance constraints are a language of tree descriptions. Tree descriptions are widely used in computational linguistics for talking and reasoning about trees. While previous research has focused on the conjunctive fragment, we now extend the account to all Boolean connectives and propose a new formalism that combines dominance constraints with a feature tree logic. Although the satisfiability problem in the conjunctive fragment is known to be NP-complete, we have previously demonstrated that it can be addressed very effectively by constraint propagation: we developed an encoding that transforms a dominance constraint into a constraint satisfaction problem on finite sets solvable by constraint programming. We present a generalization of this encoding for our more expressive formalism, and prove soundness and completeness. Our main contribution is a treatment of disjunction suitable for constraint propagation.},
      ANNOTE = {COLIURL : Duchier:2002:DCB.pdf Duchier:2002:DCB.ps}
}

@TechReport{Duchier_Gardent:1998,
      AUTHOR = {Duchier, Denys and Gardent, Claire},
      TITLE = {A constraint-based treatment of descriptions},
      YEAR = {1998},
      MONTH = {November},
      NUMBER = {105},
      PAGES = {15},
      ADDRESS = {Saarbrücken},
      TYPE = {CLAUS-Report},
      INSTITUTION = {Universität des Saarlandes},
      URL = {ftp://ftp.coli.uni-sb.de/pub/people/claire/constraints.ps},
      ABSTRACT = {Both in computational linguistics and in formal semantics, descriptions have been used which are stated in terms of dominance . Yet the issue of how such descriptions are processed has been little explored. In this paper, we present a constraint-based treatment of descriptions and apply it to the description-based treatment of discourse advocated in Gardent and Webber 1998.},
      ANNOTE = {COLIURL : Duchier:1998:CBT.pdf Duchier:1998:CBT.ps}
}

@InProceedings{Duchier_Gardent:1999,
      AUTHOR = {Duchier, Denys and Gardent, Claire},
      TITLE = {A Constraint-Based Treatment of Descriptions},
      YEAR = {1999},
      BOOKTITLE = {3rd International Workshop on Computational Semantics (IWCS 3), January 13-15},
      PAGES = {71-85},
      EDITOR = {Bunt, Harry and Thijsse, Elias},
      ADDRESS = {Tilburg, The Netherlands},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/iwcs99.ps.gz},
      ABSTRACT = {Both in computational linguistics and in formal semantics, tree (or graph) descriptions stated in terms of <i>dominance</i> have become common. Yet the issue of how such descriptions are processed has been little explored. In this paper, we present a constraint-based treatment of descriptions: we develop a formulation in terms of sets, which is simple and declarative, and, at the same time, constitutes an efficient implementation. We further show how the treatement of tree descriptions can be extended to DAG descriptions and apply it to a description-based account of discourse.},
      ANNOTE = {COLIURL : Duchier:1999:CBT.pdf Duchier:1999:CBT.ps}
}

@InCollection{Duchier_Gardent:2001,
      AUTHOR = {Duchier, Denys and Gardent, Claire},
      TITLE = {Tree Descriptions, Constraints and Incrementality},
      YEAR = {2001},
      BOOKTITLE = {Computing Meaning, Volume 2},
      VOLUME = {77},
      PAGES = {205-227},
      EDITOR = {Bunt, Harry and Muskens, Reinhard and Thijsse, Elias},
      SERIES = {Studies In Linguistics And Philosophy},
      ADDRESS = {Dordrecht},
      PUBLISHER = {Kluwer Academic Publishers},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/iwcs3-book.ps.gz},
      ABSTRACT = {In 	extitA Constraint-Based Treatment of Descriptions, we presented a constraint-based method for enumerating the models satisfying a given tree description and described its application to the underspecified semantic representation of discourse advocated by Gardent \& Webber (1998). In this paper, we indicate how the approach may be further extended to support discourse level 	extitincremental processing. 	extbfKeywords: incremental processing, underspecified representations, tree descriptions, dominance constraints, constraint programming, discourse semantics.},
      ANNOTE = {COLIURL : Duchier:2001:TDC.pdf Duchier:2001:TDC.ps}
}

@TechReport{Duchier_et_al:1998,
      AUTHOR = {Duchier, Denys and Kornstaedt, Leif and Schulte, Christian and Smolka, Gert},
      TITLE = {A Higher-Order Module Discipline with Separate Compilation, Dynamic Linking, and Pickling},
      YEAR = {1998},
      ADDRESS = {Saarbrücken},
      TYPE = {Technical Report},
      INSTITUTION = {Programming Systems Lab, DFKI and Universität des Saarlandes},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/modules-98.ps.gz},
      ABSTRACT = {We present a higher-order module discipline with separate compilation and concurrent dynamic linking. Based on first-order modules one can program security policies for systems that link modules from untrusted locations (e.g., Java). We introduce a pickling operation that writes persistent clones of volatile, possibly higher-order data structures on the file system. Our pickling operation respects lexical binding. Our module discipline is based on functors, which are annotated functions that are applied to modules and return modules. Pickled computed functors can be used interchangeably with compiled functors. In contrast to compiled functors, pickled computed functors can carry computed data structures with them, which has significant practical applications.},
      ANNOTE = {COLIURL : Duchier:1998:HOM.pdf Duchier:1998:HOM.ps}
}

@InProceedings{Duchier_Niehren:2000,
      AUTHOR = {Duchier, Denys and Niehren, Joachim},
      TITLE = {Dominance Constraints with Set Operators},
      YEAR = {2000},
      BOOKTITLE = {1st International Conference on Computational Logic (CL '00), July 24-28},
      NUMBER = {1861},
      PAGES = {326-341},
      EDITOR = {Lloyd, J. and Dahl, V.},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {Imperial College, London, UK},
      PUBLISHER = {Springer},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/dombool.ps.gz},
      ABSTRACT = {Dominance constraints are widely used in computational linguistics as a language for talking and reasoning about trees. In this paper, we extend dominance constraints by admitting set operators. Set operators contribute a controlled form of disjunction that is emminently well-suited for constraint propagation. We present a solver for dominance constraints with set operators as a system of abstract propagation and distribution rules, and prove its soundness and completeness. We then derive an efficient implementation in a constraint programming language with finite sets and prove its faithfullness to the abstract inference rules.},
      ANNOTE = {COLIURL : Duchier:2000:DCS.pdf Duchier:2000:DCS.ps}
}

@InProceedings{Duchier_Thater:1999,
      AUTHOR = {Duchier, Denys and Thater, Stefan},
      TITLE = {Parsing with Tree Descriptions: A Constraint-Based Approach},
      YEAR = {1999},
      BOOKTITLE = {6th International Workshop on Natural Language Understanding and Logic Programming (NLULP '99), December 3-4},
      PAGES = {17-32},
      ADDRESS = {Las Cruces, New Mexico, USA},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/duchier-thater-nlulp99.ps.gz},
      ABSTRACT = {We describe a grammatical formalism based on tree descriptions and develop a constraint-based treatment of parsing in that framework. We introduce the language of electrostatic tree descriptions to write lexical entries: these are tree descriptions using neutral, as well as positively and negatively charged variables. We develop an appropriate notion of model. We then extend the framework to disjunctive systems of electrostatic descriptions, and we correspondingly extend the notion of model. Then we show how the search for minimal models can be realized by reduction to a CSP solvable by constraint programming and we provide the full encoding in an axiomatic style.},
      ANNOTE = {COLIURL : Duchier:1999:PTD.pdf Duchier:1999:PTD.ps}
}

@Article{Uszkoreit_et_al:1998,
      AUTHOR = {Uszkoreit, Hans and Brants, Thorsten and Duchier, Denys and Krenn, Brigitte and Konieczny, Lars and Oepen, Stefan and Skut, Wojciech},
      TITLE = {Studien zur performanzorientierten Linguistik: Aspekte der Relativsatzextraposition im Deutschen},
      YEAR = {1998},
      JOURNAL = {Kognitionswissenschaft},
      VOLUME = {7},
      NUMBER = {3},
      PAGES = {129-133},
      ABSTRACT = {Am Beispiel der Relativsatzextraposition im Deutschen zeigt das Papier wie Verfahren der sprachwissenschaftlichen Modellbildung, korpuslinguistischen Untersuchung und des psycholinguistischen Experiments in einem integrativen Forschungsansatz zusammenwirken, der auf ein verbessertes Verständnis und die linguistisch wie kognitiv adäquate Modellierung sprachlicher Performanzprobleme zielt. Ausgehend von der von Hawkins (1994) formulierten Theorie zur Wortstellung werden Hypothesen über die positionelle Verteilung von Relativsätzen formuliert und in Bezug auf Korpusdaten und Akzeptabilitätsmessungen überprüft. Alle beschriebenen empirischen Untersuchungen bestätigen den erwarteten Einfluss von Längenfaktoren auf die Relativsatzdistribution, zeigen gleichzeitig aber eine interessante Asymmetrie zwischen Produktions- und Rezeptionsdaten.}
}

@TechReport{Uszkoreit_et_al:1998_1,
      AUTHOR = {Uszkoreit, Hans and Brants, Thorsten and Duchier, Denys and Krenn, Brigitte and Konieczny, Lars and Oepen, Stephan and Skut, Wojciech},
      TITLE = {Studien zur performanzorientierten Linguistik. Aspekte der Relativsatzextraposition im Deutschen},
      YEAR = {1998},
      MONTH = {April},
      NUMBER = {99},
      ADDRESS = {Saarbrücken.},
      TYPE = {CLAUS-Report},
      INSTITUTION = {Universität des Saarlandes},
      URL = {https://www.coli.uni-saarland.de/~thorsten/publications/Uszkoreit-ea-CLAUS99.pdf ftp://ftp.coli.uni-sb.de/pub/coli/claus/claus99.ps ftp://ftp.coli.uni-sb.de/pub/coli/claus/claus99.dvi},
      ABSTRACT = {Am Beispiel der Relativsatzextraposition im Deutschen zeigt das Papier wie Verfahren der sprachwissenschaftlichen Modellbildung, korpuslinguistischen Untersuchung und des psycholinguistischen Experiments in einem integrativen Forschungsansatz zusammenwirken, der auf ein verbessertes Verständnis und die linguistisch wie kognitiv adäquate Modellierung sprachlicher Performanzprobleme zielt. Ausgehend von der von Hawkins (1994) formulierten Theorie zur Wortstellung werden Hypothesen über die positionelle Verteilung von Relativsätzen formuliert und in Bezug auf Korpusdaten und Akzeptabilitätsmessungen überprüft. Alle beschriebenen empirischen Untersuchungen bestätigen den erwarteten Einfluß von Längenfaktoren auf die Relativsatzdistribution, zeigen gleichzeitig aber eine interessante Asymmetrie zwischen Produktions- und Rezeptionsdaten. Ein gekürzte Fassung erscheint in Kognitionswissenschaft, Themenheft SFB 378, 1998.},
      ANNOTE = {COLIURL : Uszkoreit:1998:SPLb.pdf Uszkoreit:1998:SPLb.ps}
}

@InProceedings{Debusmann_et_al:2004,
      AUTHOR = {Debusmann, Ralph and Duchier, Denys and Koller, Alexander and Kuhlmann, Marco and Smolka, Gert and Thater, Stefan},
      TITLE = {A Relational Syntax-Semantics Interface Based on Dependency Grammar},
      YEAR = {2004},
      BOOKTITLE = {Proceedings of the 20th COLING},
      ADDRESS = {Geneva}
}

@InProceedings{Fliedner:2003,
      AUTHOR = {Fliedner, Gerhard},
      TITLE = {Tools for Building a Lexical Semantic Annotation},
      YEAR = {2003},
      BOOKTITLE = {Prospects and Advances in the Syntax/Semantic Interface. Lorraine-Saarland Workshop Series.},
      PAGES = {5-9},
      EDITOR = {Duchier, Denys},
      ADDRESS = {Loria, Nancy}
}

@InProceedings{Wolska_Kruijff-Korbayova:2003,
      AUTHOR = {Wolska, Magdalena and Kruijff-Korbayova, Ivana},
      TITLE = {Issues in the interpretation of input in mathematical dialogs},
      YEAR = {2003},
      BOOKTITLE = {Prospects and advances in the syntax/semantics interface. Lorraine-Saarland Workshop Series proceedings.},
      PAGES = {45-50},
      EDITOR = {Duchier, Denys},
      ADDRESS = {Nancy, France}
}

@InProceedings{Kruijff_Duchier:2003,
      AUTHOR = {Kruijff, Geert-Jan M. and Duchier, Denys},
      TITLE = {Information Structure in Topological Dependency Grammar},
      YEAR = {2003},
      BOOKTITLE = {Proceedings EACL'03},
      ADDRESS = {Budapest Hungary},
      NOTE = {Kruijff:2003:IST}
}

@InProceedings{Braun:2003,
      AUTHOR = {Braun, Christian},
      TITLE = {Parsing German text for syntacto-semantic structures},
      YEAR = {2003},
      BOOKTITLE = {Prospects and Advances in the Syntax/Semantics Interface},
      PAGES = {99--102},
      EDITOR = {Duchier, Denys},
      SERIES = {Lorraine-Saarland Workshop Series},
      ADDRESS = {Nancy, Frankreich}
}

@InProceedings{Erk_et_al:2003_5,
      AUTHOR = {Erk, Katrin and Kowalski, Andrea and Pado, Sebastian},
      TITLE = {The SALSA Annotation Tool},
      YEAR = {2003},
      BOOKTITLE = {Proceedings of the Workshop on Prospects and Advances in the Syntax/Semantics Interface},
      EDITOR = {Duchier, Denys and Kruijff, Geert-Jan M.},
      ADDRESS = {Nancy, France},
      URL = {https://www.coli.uni-saarland.de/~erk/OnlinePapers/lorrainesaarland.ps}
}

@InProceedings{Kordoni:2003_4,
      AUTHOR = {Kordoni, Valia},
      TITLE = {Syntax-Semantics Interface in Lexicalist Theories},
      YEAR = {2003},
      MONTH = {20 October},
      BOOKTITLE = {Proceedings of the Workshop on Prospects and Advances in the Syntax/Semantics Interface},
      EDITOR = {Duchier, Denys and Kruijff, Geert-Jan M.},
      ADDRESS = {Nancy},
      URL = {http://www.loria.fr/~duchier/Lorraine-Saarland/}
}

@InProceedings{Pado_Torrent:2003,
      AUTHOR = {Pado, Sebastian and Torrent, Gemma Boleda},
      TITLE = {Towards a better understanding of frame element assignment errors},
      YEAR = {2003},
      BOOKTITLE = {Proceedings of the Workshop on Prospects and Advances in the Syntax/Semantics Interface},
      EDITOR = {Duchier, Denys and Kruijff, Geert-Jan M.},
      ADDRESS = {Nancy, France}
}

@InProceedings{FokkAvg2013,
      AUTHOR = {Fokkens, Antske and Avgustinova, Tania},
      TITLE = {SlaviCLIMB: combining expertise for Slavic grammar development using a metagrammar},
      YEAR = {2013},
      MONTH = {12-16 August},
      BOOKTITLE = {Workshop on High-level Methodologies for Grammar Engineering @ ESSLLI 2013},
      PAGES = {87-92},
      EDITOR = {Duchier, Denys and Parmentier, Yannick},
      ADDRESS = {Düsseldorf},
      NOTE = {HU}
}