# Publications of Alexander Koller

### 2007

Alexander Koller and Owen Rambow Relating dominance formalisms. Proceedings of the 12th Conference on Formal Grammar, Dublin.Alexander Koller and Stefan Thater. Solving unrestricted dominance graphs. Proceedings of the 12th Conference on Formal Grammar, Dublin.

Alexander Koller and Matthew Stone. Sentence generation as planning. Proceedings of ACL-07, Prague.

Donna Byron, Alexander Koller, Jon Oberlander, Laura Stoia, and Kristina Striegnitz. Generating Instructions in Virtual Environments (GIVE): A challenge and evaluation testbed for NLG. Proceedings of the Workshop on Shared Tasks and Comparative Evaluation in Natural Language Generation, Arlington.

### 2006

Alexander Koller and Stefan Thater. An improved redundancy elimination algorithm for underspecified descriptions. Proceedings of COLING/ACL-2006, Sydney.Alexander Koller and Stefan Thater. Towards a redundancy elimination algorithm for underspecified descriptions. Proceedings of the 5th Intl. Workshop on Inference in Computational Semantics (ICoS-5), Buxton, England.

### 2005

Dan Flickinger, Alexander Koller, and Stefan Thater. A new well-formedness criterion for semantics debugging. Proceedings of the 12th International Conference on HPSG, Lisbon.Alexander Koller and Stefan Thater. The Evolution of Dominance Constraint Solvers. Proceedings of the ACL-05 Workshop on Software, Ann Arbor.

Alexander Koller and Stefan Thater. Efficient solving and exploration of scope ambiguities. Proceedings of the ACL-05 Demo Session.

### 2004

Alexander Koller. Constraint-based and graph-based resolution of ambiguities in natural language. PhD Thesis, Universität des Saarlandes.Ralph Debusmann, Denys Duchier, Alexander Koller, Marco Kuhlmann, Gert Smolka, and Stefan Thater. A Relational Syntax-Semantics Interface Based on Dependency Grammar. Proceedings of the 20th COLING, Geneva.

Alexander Koller and Geert-Jan Kruijff. Talking Robots With LEGO MindStorms. Proceedings of the 20th COLING, Geneva.

Ruth Fuchss, Alexander Koller, Joachim Niehren, and Stefan Thater. Minimal Recursion Semantics as Dominance Constraints: Translation, Evaluation, and Analysis. Proceedings of the 42nd ACL, Barcelona.

Ernst Althaus, Nikiforos Karamanis, and Alexander Koller. Computing Locally Coherent Discourses. Proceedings of the 42nd ACL, Barcelona.

Alexander Koller, Ralph Debusmann, Malte Gabsdil, and Kristina Striegnitz.
Put my galakmid coin into the dispenser and kick it: Computational Linguistics and Theorem Proving in a Computer Game.
*Journal of Logic, Language, and Information.* To appear.

### 2003

Peter Dienes, Alexander Koller, and Marco Kuhlmann. Statistical A* Dependency Parsing. Proceedings of the Workshop on Prospects and Advances in the Syntax/Semantics Interface, Nancy.Alexander Koller, Joachim Niehren, and Stefan Thater. Bridging the Gap Between Underspecification Formalisms: Hole Semantics as Dominance Constraints. Proceedings of the 11th EACL, Budapest.

Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, and Sven Thiel.
An Efficient Graph Algorithm for Dominance Constraints.
*Journal of Algorithms.* To appear.

### 2002

Michael Kohlhase and Alexander Koller. Resource-Adaptive Model Generation as a Performance Model.*Journal of Language and Computation.*To appear.

Katrin Erk, Alexander Koller, and Joachim Niehren.
Processing Underspecified Semantic Descriptions in the Constraint Language for Lambda Structures.
*Journal of Language & Computation.* To appear.

Malte Gabsdil, Alexander Koller, and Kristina Striegnitz. Natural Language and Inference in a Computer Game. Proceedings of the 19th COLING, Taipei.

Alexander Koller and Kristina Striegnitz. Generation as Dependency Parsing. Proceedings of the 40th ACL, Philadelphia.

### 2001

Malte Gabsdil, Alexander Koller, and Kristina Striegnitz. Playing With Description Logic. Proceedings of Second Workshop on Methods for Modalities (Application Description), Amsterdam.Malte Gabsdil, Alexander Koller, and Kristina Striegnitz. Building a Text Adventure on Description Logic. Proceedings of KI-2001 Workshop on Applications of Description Logics, Vienna.

Katrin Erk and Alexander Koller. VP Ellipsis by Tree Surgery. Proceedings of the 13th Amsterdam Colloquium, Amsterdam.

Manuel Bodirsky, Katrin Erk, Alexander Koller, and Joachim Niehren. Underspecified Beta Reduction. Proceedings of the 39th ACL, Toulouse.

Manuel Bodirsky, Katrin Erk, Alexander Koller, and Joachim Niehren. Beta Reduction Constraints. Proceedings of the 12th International Conference on Rewriting Techniques and Applications, Utrecht.

Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, and Sven Thiel. An Efficient Algorithm for the Configuration Problem of Dominance Graphs. Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, Washington, DC.

Markus Egg, Alexander Koller, and Joachim Niehren.
The Constraint Language for Lambda Structures.
*Journal of Logic, Language, and Information.* To appear.

### 2000

Alexander Koller, Kurt Mehlhorn, and Joachim Niehren. A Polynomial-Time Fragment of Dominance Constraints. Proceedings of the 38th ACL, Hong Kong.Michael Kohlhase and Alexander Koller. Towards A Tableaux Machine for Language Understanding. Proceedings of ICOS-2, Dagstuhl.

Alexander Koller, Joachim Niehren, and Kristina Striegnitz.
Relaxing Underspecified Semantic Representations for Reinterpretation.
*Grammars 3*:2-3.

Alexander Koller and Joachim Niehren. On Underspecified Processing of Dynamic Semantics. Proceedings of COLING-2000, Saarbrücken.

Alexander Koller and Joachim Niehren. Constraint Programming in Computational Linguistics. To appear in Proceedings of LLC8, CSLI Press.

### 1999

Jan Jaspars and Alexander Koller. A Calculus for Direct Deduction with Dominance Constraints. Proceedings of the Twelfth Amsterdam Colloquium, Amsterdam.Alexander Koller and Joachim Niehren. Scope Underspecification and Processing. Lecture Notes, ESSLLI '99, Utrecht.

Alexander Koller, Joachim Niehren, and Kristina Striegnitz. Relaxing Underspecified Semantic Representations for Reinterpretation. Proceedings of the Sixth Meeting on Mathematics of Language (MOL6), Orlando, Florida.

Alexander Koller. Constraint Languages for Semantic Underspecification. Diplomarbeit, Universität des Saarlandes.

### 1998

Alexander Koller, Joachim Niehren, and Ralf Treinen. Dominance Constraints: Algorithms and Complexity. Proceedings of the Third Conference on Logical Aspects of Computational Linguistics (LACL '98), Grenoble, France. To appear in LNCS.Joachim Niehren and Alexander Koller. Dominance Constraints in Context Unification. Proceedings of the Third Conference on Logical Aspects of Computational Linguistics (LACL '98), Grenoble, France. To appear in LNCS.

Alexander Koller. Evaluating Context Unification for Semantic Underspecification. Proceedings of the Third ESSLLI Student Session, Saarbrücken, Germany.