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




@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{Bodirsky_et_al:2001,
      AUTHOR = {Bodirsky, Manuel and Erk, Katrin and Koller, Alexander and Niehren, Joachim},
      TITLE = {Beta Reduction Constraints},
      YEAR = {2001},
      BOOKTITLE = {12th International Conference on Rewriting Techniques and Applications (RTA'01), May 22-24},
      PAGES = {31-46},
      EDITOR = {Middeldorp, Aart},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {Utrecht, The Netherlands},
      PUBLISHER = {Springer-Verlag},
      URL = {https://www.coli.uni-saarland.de/~koller/papers/beta.ps.gz},
      ABSTRACT = {The constraint language for lambda structures (CLLS) can model lambda terms that are known only partially. In this paper, we introduce beta reduction constraints to describe beta reduction steps between partially known lambda terms. We show that beta reduction constraints can be expressed in an extension of CLLS by group parallelism. We then extend a known semi-decision procedure for CLLS to also deal with group parallelism and thus with beta-reduction constraints.},
      ANNOTE = {COLIURL : Bodirski:2001:BRC.pdf Bodirsky:2001:BRC.ps}
}

@InProceedings{Bodirsky_et_al:2001_1,
      AUTHOR = {Bodirsky, Manuel and Erk, Katrin and Koller, Alexander and Niehren, Joachim},
      TITLE = {Underspecified Beta Reduction},
      YEAR = {2001},
      BOOKTITLE = {Proceedings of the 39th Annual Meeting of the Association of Computational Linguistics (ACL'01), July 6-11},
      PAGES = {74-81},
      ADDRESS = {Toulouse, France},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/usp-beta.ps.gz https://www.coli.uni-saarland.de/~koller/papers/usp-beta.ps.gz},
      ABSTRACT = {For ambiguous sentences, traditional semantics construction produces large numbers of higher-order formulas, which must then be beta-reduced individually. Underspecified versions can produce compact descriptions of all readings, but it is not known how to perform beta reduction on these descriptions. We show how to do this using beta reduction constraints in the constraint language for $lambda$-structures (CLLS).},
      ANNOTE = {COLIURL : Bodirski:2001:UBR.pdf Bodirsky:2001:UBR.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}
}

@Article{Egg_et_al:2001,
      AUTHOR = {Egg, Markus and Koller, Alexander and Niehren, Joachim},
      TITLE = {The Constraint Language for Lambda Structures},
      YEAR = {2001},
      JOURNAL = {Journal of Logic, Language, and Information},
      VOLUME = {10},
      NUMBER = {4},
      PAGES = {457-485},
      URL = {https://www.coli.uni-saarland.de/~koller/papers/clls.ps.gz},
      ANNOTE = {COLIURL : Egg:2001:CLL.pdf Egg:2001:CLL.ps}
}

@TechReport{Egg_et_al:1998_1,
      AUTHOR = {Egg, Markus and Koller, Alexander and Niehren, Joachim and Ruhrberg, Peter},
      TITLE = {Constraints over Lambda Structures, Antecedent Contained Deletion, and Quantifier Identities},
      YEAR = {1998},
      ADDRESS = {Saarbrücken},
      TYPE = {Technical Report},
      INSTITUTION = {Computational Linguistics and Programming Systems Lab, University of the Saarland},
      ABSTRACT = {The constraint language for lambda-structures (CLLS) allows for a simple, integrated, and underspecified treatment of scope, ellipses, anaphora, and their interaction. CLLS features constraints for dominance, lambda binding, parallelism, and anaphoric links. In the case of antecedent contained deletion (ACD), the definition of parallelism in the original version of CLLS is slightly too restrictive due to an overly weak notion of quantifier identity. We show how to extend CLLS with an appropriate notion of quantifier identity such that ACD can be naturally analysed. This sheds some light on conflicting requirements on quantifier representations as needed for ACD and Hirschbühler sentences.}
}

@InProceedings{Egg_et_al:1998_2,
      AUTHOR = {Egg, Markus and Niehren, Joachim and Ruhrberg, Peter and Xu, Feiyu},
      TITLE = {Constraints over Lambda-Structures in Semantic Underspecification},
      YEAR = {1998},
      BOOKTITLE = {17th International Conference on Computational Linguistics and 36th Annual Meeting of the Association for Computational Linguistics (COLING-ACL'98), August 10-14},
      VOLUME = {1},
      PAGES = {353-359},
      EDITOR = {ACL},
      ADDRESS = {Montréal, Québec, Canada},
      PUBLISHER = {Morgan Kaufmann Publishers},
      URL = {http://www.dfki.de/~feiyu/CLLS-98.pdf ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/COLING-feiyu-98.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/COLING-feiyu-98.entry},
      ABSTRACT = {We introduce a first-order language for semantic underspecification that we call Constraint Language for Lambda-Structures (CLLS). A lambda-structure can be considered as a lambda-term up to consistent renaming of bound variables (alpha-equality); a constraint of CLLS is an underspecified description of a $lambda$-structure. CLLS solves a capturing problem omnipresent in underspecified scope representations. CLLS features constraints for dominance, lambda binding, parallelism, and anaphoric links. Based on CLLS we present a simple, integrated, and underspecified treatment of scope, parallelism, and anaphora.},
      ANNOTE = {COLIURL : Egg:1998:CLSb.pdf Egg:1998:CLSb.ps}
}

@Article{Erk_et_al:2003,
      AUTHOR = {Erk, Katrin and Koller, Alexander and Niehren, Joachim},
      TITLE = {Processing Underspecified Semantic Descriptions in the Constraint Language for Lambda Structures},
      YEAR = {2003},
      JOURNAL = {Research on Language and Computation},
      VOLUME = {1},
      PAGES = {127--169},
      URL = {https://www.coli.uni-saarland.de/~koller/papers/cllsproc.ps.gz},
      ABSTRACT = {The constraint language for lambda structures (CLLS) is an expressive language of tree descriptions which combines dominance constraints with powerful parallelism and binding constraints. CLLS was introduced as a uniform framework for defining underspecified semantics representations of natural language sentences, covering scope, ellipsis, and anaphora. This article presents saturation-based algorithms for processing the complete language of CLLS and gives an overview of previous results on questions of processing and complexity.},
      ANNOTE = {COLIURL : Erk:2002:PUS.pdfErk:2002:PUS.ps}
}

@InProceedings{Erk_Niehren:2000,
      AUTHOR = {Erk, Katrin and Niehren, Joachim},
      TITLE = {Parallelism Constraints},
      YEAR = {2000},
      BOOKTITLE = {11th International Conference on Rewriting Techniques and Applications (RTA '00), July 10-12},
      EDITOR = {Bachmair, L.},
      SERIES = {LNCS},
      ADDRESS = {University of East Anglia, Norwich, UK},
      PUBLISHER = {Springer},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/parallelism.ps.gz},
      ABSTRACT = {Parallelism constraints are logical desciptions of trees. They are as expressive as context unification, i.e. second-order linear unification. We present a semi-decision procedure enumerating all most general unifiers of a parallelism constraint and prove it sound and complete. In contrast to all known procedures for context unification, the presented procedure terminates for the important fragment of dominance constraints and performs reasonably well in a recent application to underspecified natural language semantics.},
      ANNOTE = {COLIURL : Erk:2000:PC.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}
}

@TechReport{Koller_Niehren:1999,
      AUTHOR = {Koller, Alexander and Niehren, Joachim},
      TITLE = {Scope Underspecification and Processing},
      YEAR = {1999},
      TYPE = {Reader for the ESSLLI summer school},
      URL = {http://www.ps.uni-sb.de/~niehren/ESSLLI99/ ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/ESSLLI:99.ps.gz},
      ABSTRACT = {This reader contains material for the ESSLLI '99 course, Scope Underspecification and Processing''. The reader and course are aimed at a pretty broad audience; we have tried to only presuppose a very general idea of natural language processing and of first-order logic. Underspecification is a general approach to dealing with ambiguity. In the course, we'll be particularly concerned with scope underspecification, which deals with scope ambiguity, a structural ambiguity of the semantics of a sentence. As scope underspecification is at least partially motivated by computational issues, we will pay particular attention to processing aspects. We're going to show how dominance constraints can be used for scope underspecification and how they can be processed efficiently by using concurrent constraint programming technology.},
      ANNOTE = {COLIURL : Koller:1999:SUP.pdf Koller:1999:SUP.ps}
}

@InProceedings{Koller_Niehren:2000,
      AUTHOR = {Koller, Alexander and Niehren, Joachim},
      TITLE = {Constraint Programming in Computational Linguistics},
      YEAR = {2000},
      BOOKTITLE = {8th CSLI Workshop on Logic Language and Computation, May 30},
      EDITOR = {Barker-Plummer, Dave and Beaver, D. and van Benthem, Johan and Scotto di Luzio, P.},
      ADDRESS = {Stanford},
      PUBLISHER = {CSLI},
      URL = {http://www.ps.uni-sb.de/Papers/abstracts/CP-NL.html ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/CP-NL.ps.gz},
      ABSTRACT = {Constraint programming is a programming paradigm that was originally invented in computer science to deal with hard combinatorial problems. Recently, constraint programming has evolved into a technology which permits to solve hard industrial scheduling and optimization problems. We argue that existing constraint programming technology can be useful for applications in natural language processing. Some problems whose treatment with traditional methods requires great care to avoid combinatorial explosion of (potential) readings seem to be solvable in an efficient and elegant manner using constraint programming. We illustrate our claim by two recent examples, one from the area of underspecified semantics and one from parsing.},
      ANNOTE = {COLIURL : Koller:2000:CPC.pdf Koller:2000:CPC.ps}
}

@InProceedings{Koller_Niehren:2000_1,
      AUTHOR = {Koller, Alexander and Niehren, Joachim},
      TITLE = {On Underspecified Processing of Dynamic Semantics},
      YEAR = {2000},
      BOOKTITLE = {18th International Conference on Computational Linguistics (COLING '00), July 31 - August 4},
      PAGES = {460-466},
      ADDRESS = {Saarbrücken, Germany},
      PUBLISHER = {Morgan Kaufmann},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/dynamic.ps.gz},
      ABSTRACT = {We propose a new inference system which operates on underspecified semantic representations of scope and anaphora. This inference system exploits anaphoric accessibility conditions known from dynamic semantics to decide scope ambiguities if possible. The main feature of the system is that it deals with underspecified descriptions directly, i.e. without enumerating readings.},
      ANNOTE = {COLIURL : Koller:2000:UPD.pdf Koller:2000:UPD.ps}
}

@InCollection{Koller_Niehren:2002,
      AUTHOR = {Koller, Alexander and Niehren, Joachim},
      TITLE = {Constraint Programming in Computational Linguistics},
      YEAR = {2002},
      BOOKTITLE = {Words, Proofs, and Diagrams},
      EDITOR = {Barker-Plummer, Dave and Beaver, David I. and van Benthem, Johan and di Luzio, Patrick Scotto},
      ADDRESS = {Stanford},
      PUBLISHER = {CSLI Press},
      URL = {http://www.ps.uni-sb.de/Papers/abstracts/CP-NL.html ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/CP-NL.ps.gz},
      ABSTRACT = {Constraint programming is a programming paradigm that was originally invented in computer science to deal with hard combinatorial problems. Recently, constraint programming has evolved into a technology which permits to solve hard industrial scheduling and optimization problems. We argue that existing constraint programming technology can be useful for applications in natural language processing. Some problems whose treatment with traditional methods requires great care to avoid combinatorial explosion of (potential) readings seem to be solvable in an efficient and elegant manner using constraint programming. We illustrate our claim by two recent examples, one from the area of underspecified semantics and one from parsing.},
      NOTE = {Extended version of a paper at the 8th Stanford Workshop on Logic, Language, and Computation (1999)},
      ANNOTE = {COLIURL : Koller:2002:CPC.pdf Koller:2002:CPC.ps}
}

@InProceedings{Koller_et_al:1999,
      AUTHOR = {Koller, Alexander and Niehren, Joachim and Striegnitz, Kristina},
      TITLE = {Relaxing Underspecified Semantic Representations for Reinterpretation},
      YEAR = {1999},
      BOOKTITLE = {6th Meeting on Mathematics of Language (MOL6), July 23-25},
      PAGES = {74-87},
      ADDRESS = {Orlando, Florida, USA},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/Relax99.ps.gz},
      ABSTRACT = {Type and sort conflicts in semantics are usually resolved by a process of reinterpretation. Recently, Egg (1999) has proposed an alternative account in which conflicts are avoided by underspecification. The main idea is to derive sufficiently relaxed underspecified semantic representations; addition of reinterpretation operators then simply is further specialization. But in principle, relaxing underspecified representations bears the danger of overgeneration. In this paper, we investigate this problem in the framework of CLLS, where underspecified representations are expressed by tree descriptions subsuming dominance constraints. We introduce some novel properties of dominance constraints and present a safety criterion that ensures that an underspecified description can be relaxed without adding unwanted readings. We then apply this criterion systematically to Egg's analysis and show why its relaxation operation does not lead to overgeneration.},
      ANNOTE = {COLIURL : Koller:1999:RUS.pdf Koller:1999:RUS.ps}
}

@Article{Koller_et_al:2000_1,
      AUTHOR = {Koller, Alexander and Niehren, Joachim and Striegnitz, Kristina},
      TITLE = {Relaxing Underspecified Semantic Representations for Reinterpretation},
      YEAR = {2000},
      JOURNAL = {Grammars},
      VOLUME = {3},
      NUMBER = {2-3},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/relax2000.ps.gz},
      ABSTRACT = {Type and sort conflicts in semantics are usually resolved by a process of reinterpretation, which introduces an operator into the semantic representation. We elaborate on the foundations of a recent approach to reinterpretation within a framework for semantic underspecification. In this approach, relaxed underspecified semantic representations are inferred from the syntactic structure, leaving space for subsequent addition of reinterpretation operators. Unfortunately, a structural danger of overgeneration is inherent to the relaxation of underspecified semantic representations. We identify the problem and distinguish structural properties that avoid it. We furthermore develop techniques for proving these properties and apply them to prove the safety of relaxation in a prototypical syntax/semantics interface. In doing so, we present some novel properties of tree descriptions in the constraint language over lambda structures (CLLS).},
      ANNOTE = {COLIURL : Koller:2000:RUS.pdf Koller:2000:RUS.ps}
}

@InProceedings{Koller_et_al:1998,
      AUTHOR = {Koller, Alexander and Niehren, Joachim and Treinen, Ralf},
      TITLE = {Dominance Constraints: Algorithms and Complexity},
      YEAR = {1998},
      BOOKTITLE = {3rd International Conference on Logical Aspects of Computational Linguistics (LACL '98), December 14-16},
      ADDRESS = {Grenoble, France},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/DominanceNP98.ps.gz},
      ABSTRACT = {Dominance constraints for finite tree structures are widely used in several areas of computational linguistics including syntax, semantics, and discourse. In this paper, we investigate algorithmic and complexity questions for dominance constraints and their first-order theory. We present two NP algorithms for solving dominance constraints, which have been implemented in the concurrent constraint programming language Oz. The main result of this paper is that the satisfiability problem of dominance constraints is NP-complete. Despite this intractability result, the more sophisticated of our algorithms performs well in an application to scope underspecification. We also show that the existential fragment of the first-order theory of dominance constraints is NP-complete and that the full first-order theory has non-elementary complexity.},
      ANNOTE = {COLIURL : Koller:1998:DCA.pdf Koller:1998:DCA.ps}
}

@TechReport{Müller_Niehren:1997,
      AUTHOR = {Müller, Martin and Niehren, Joachim},
      TITLE = {Entailment of Set Constraints is not Feasible},
      YEAR = {1997},
      ADDRESS = {Saarbrücken},
      TYPE = {Technical Report},
      INSTITUTION = {Universität des Saarlandes, Programming Systems Lab},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/inesInfeas.ps.gz},
      ABSTRACT = {Set constraints are inclusions between expressions denoting sets of trees. They have been used extensively for type inference and program analysis. At the lower end of the expressiveness scale there are atomic set constraints and Ines constraints (inclusions over non-empty sets) for both of which a cubic time satisfiability test is known. Recently, there has been increasing interest in entailment tests for set constraints. We prove that the entailment problem of atomic set constraints is coNP-hard. We also show that the entailment problem of Ines constraints is coNP-hard. This corrects a claim of polynomial complexity presented at CP'96. Our results suggest that a complete entailment test is not feasible even for simple classes of set constraints.},
      ANNOTE = {COLIURL : Muller:1997:ESC.pdf Muller:1997:ESC.ps}
}

@InProceedings{Müller_Niehren:1998,
      AUTHOR = {Müller, Martin and Niehren, Joachim},
      TITLE = {Ordering Constraints over Feature Trees Expressed in Second-Order Monadic Logic},
      YEAR = {1998},
      BOOKTITLE = {9th International Conference on Rewriting Techniques and Applications (RTA '98), March 30 - April 1},
      NUMBER = {1379},
      PAGES = {196-210},
      EDITOR = {Nipkow, T.},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {Tsukuba, Japan},
      PUBLISHER = {Springer-Verlag},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/SWS97.ps.gz},
      ABSTRACT = {The system FT$_lt$ of ordering constraints over feature trees has been introduced as an extension of the system FT of equality constraints over feature trees. We investigate decidability and complexity questions for fragments of the first-order theory of FT$_lt$. It is well-known that the first-order theory of FT$_lt$ is decidable and that several of its fragments can be decided in quasi-linear time, including the satisfiability problem of FT$_lt$ and its entailment problem with existential quantification $$phimodels E x1 ... E xn ( phi' )$$ Much less is known on the first-order theory of FT$_lt$. The satisfiability problem of FT$_lt$ can be decided in cubic time, as well as its entailment problem without existential quantification. Our main result is that the entailment problem of FT$_lt$ with existential quantifiers is decidable but PSPACE-hard. Our decidability proof is based on a new technique where feature constraints are expressed in second-order monadic logic with countably many successors SwS. We thereby reduce the entailment problem of FT$_lt$ with existential quantification to Rabin's famous theorem on tree automata.},
      ANNOTE = {COLIURL : Muller:1998:OCF.pdf Muller:1998:OCF.ps}
}

@Article{Müller_Niehren:2000,
      AUTHOR = {Müller, Martin and Niehren, Joachim},
      TITLE = {Ordering Constraints over Feature Trees Expressed in Second-Order Monadic Logic},
      YEAR = {2000},
      JOURNAL = {Information and Computation},
      VOLUME = {159},
      NUMBER = {1-2},
      PAGES = {22-58},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/SWSJournal99.ps.gz},
      ABSTRACT = {The system FT$_leq$ of ordering constraints over feature trees has been introduced as an extension of the system FT of equality constraints over feature trees. While the first-order theory of FT is well understood, only few complexity and decidability results are known for fragments of the first-order theory of FT$_leq$. We introduce a new handle for such decidability questions by showing how to express ordering constraints over feature trees in second-order monadic logic (S2S or WS2S). Our relationship implies a new decidability result for feature logics, namely that the entailment problem of FT$_leq$ with existential quantifiers $phi_1models exists x_1ldotsexists x_n phi_2$ is decidable. We also show that this problem is PSPACE-hard even though the quantifier-free case can be solved in cubic time. To our knowledge, this is the first time that a non-trivial decidability result of feature logic is reduced to Rabins famous tree theorem.},
      ANNOTE = {COLIURL : Muller:2000:OCFa.pdf Muller:2000:OCFa.ps}
}

@InProceedings{Müller_et_al:1997,
      AUTHOR = {Müller, Martin and Niehren, Joachim and Podelski, Andreas},
      TITLE = {Ordering Constraints over Feature Trees},
      YEAR = {1997},
      BOOKTITLE = {3rd International Conference on Principles and Practice of Constraint Programming (CP '97), October 29 - November 1},
      NUMBER = {1330},
      PAGES = {297-311},
      EDITOR = {Smolka, Gert},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {Schloss Hagenberg, Austria},
      PUBLISHER = {Springer},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/FTSub97.ps.gz},
      ABSTRACT = {Feature trees have been used to accommodate records in constraint programming and record like structures in computational linguistics. Feature trees model records, and feature constraints yield extensible and modular record descriptions. We introduce the constraint system FT$<$ of ordering constraints interpreted over feature trees. Under the view that feature trees represent symbolic information, the relation $<$ corresponds to the information ordering (carries less information than). We present a polynomial algorithm that decides the satisfiability of conjunctions of positive and negative information ordering constraints over feature trees. Our results include algorithms for the satisfiability problem and the entailment problem of FT$<$ in time $O(n^3)$. We also show that FT$<$ has the independence property and are thus able to handle negative conjuncts via entailment. Furthermore, we reduce the satisfiability problem of Dörre's weak-subsumption constraints to the satisfiability problem of FT$<$. This improves the complexity bound for solving weak subsumption constraints from $O(n^5)$ to $O(n^3)$.},
      ANNOTE = {COLIURL : Muller:1997:OCF.pdf Muller:1997:OCF.ps}
}

@Article{Müller_et_al:2000,
      AUTHOR = {Müller, Martin and Niehren, Joachim and Podelski, Andreas},
      TITLE = {Ordering Constraints over Feature Trees},
      YEAR = {2000},
      JOURNAL = {Constraints, an International Journal},
      VOLUME = {5},
      NUMBER = {1-2},
      PAGES = {7-42},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/ftsub-constraints-99.ps.gz},
      ABSTRACT = {Feature trees are the formal basis for algorithms manipulating record like structures in constraint programming, computational linguistics and in concrete applications like software configuration management. Feature trees model records, and constraints over feature trees yield extensible and modular record descriptions. We introduce the constraint system FT$_leq$ of ordering constraints interpreted over feature trees. Under the view that feature trees represent symbolic information, the relation $leq$ corresponds to the information ordering (carries less information than''). We present two algorithms in cubic time, one for the satisfiability problem and one for the entailment problem of FT$_leq$. We show that FT$_leq$ has the independence property. We are thus able to handle negative conjuncts via entailment and obtain a cubic algorithm that decides the satisfiability of conjunctions of positive and negated ordering constraints over feature trees. Furthermore, we reduce the satisfiability problem of Dörre's weak subsumption constraints to the satisfiability problem of FT$_leq$ and improve the complexity bound for solving weak subsumption constraints from $O(n^5)$ to $O(n^3)$.},
      ANNOTE = {COLIURL : Muller:2000:OCFb.pdf Muller:2000:OCFb.ps}
}

@TechReport{Müller_et_al:1997_1,
      AUTHOR = {Müller, Martin and Niehren, Joachim and Smolka, Gert},
      TITLE = {Typed Concurrent Programming with Logic Variables},
      YEAR = {1997},
      MONTH = {September},
      ADDRESS = {Saarbrücken},
      TYPE = {Technical Report},
      INSTITUTION = {Universität des Saarlandes, Programming Systems Lab},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/plain-report-97.ps.gz},
      ABSTRACT = {We present a concurrent higher-order programming language called Plain and a concomitant static type system. Plain is based on logic variables and computes with possibly partial data structures. The data structures of Plain are procedures, cells, and records. Plain's type system features record-based subtyping, bounded existential polymorphism, and access modalities distinguishing between reading and writing.},
      ANNOTE = {COLIURL : Muller:1997:TCP.pdf Muller:1997:TCP.ps}
}

@InProceedings{Müller_et_al:1998,
      AUTHOR = {Müller, Martin and Niehren, Joachim and Treinen, Ralf},
      TITLE = {The First-Order Theory of Ordering Constraints over Feature Trees},
      YEAR = {1998},
      BOOKTITLE = {13th Annual IEEE Symposium on Logic in Computer Sience (LICS '98), June 21 - 24},
      PAGES = {432-443},
      ADDRESS = {Indianapolis, Indiana, USA},
      PUBLISHER = {IEEE Press},
      URL = {http://www.ps.uni-sb.de/Papers/abstracts/FTSubTheory-Long:99.html ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/FTSubTheory-Long:99.ps.gz},
      ABSTRACT = {The system FT$_leq$ of ordering constraints over feature trees has been introduced as an extension of the system FT of equality constraints over feature trees. We investigate the first-order theory of FT$_leq$ and its fragments in detail, both over finite trees and over possibly infinite trees. We prove that the first-order theory of FT$_leq$ is undecidable, in contrast to the first-order theory of FT which is well-known to be decidable. We show that the entailment problem of FT$_leq$ with existential quantification is PSPACE-complete. So far, this problem has been shown decidable, coNP-hard in case of finite trees, PSPACE-hard in case of arbitrary trees, and cubic time when restricted to quantifier-free entailment judgments. To show PSPACE-completeness, we show that the entailment problem of FT$_leq$ with existential quantification is equivalent to the inclusion problem of non-deterministic finite automata.},
      ANNOTE = {COLIURL : Muller:1998:FOT.pdf Muller:1998:FOT.ps}
}

@Article{Müller_et_al:2001,
      AUTHOR = {Müller, Martin and Niehren, Joachim and Treinen, Ralf},
      TITLE = {The First-Order Theory of Ordering Constraints over Feature Trees},
      YEAR = {2001},
      JOURNAL = {Discrete Mathematics and Theoretical Computer Science},
      VOLUME = {4},
      NUMBER = {2},
      PAGES = {193-234},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/FTSubTheory-98.ps.gz},
      ABSTRACT = {The system FT$_leq$ of ordering constraints over feature trees has been introduced as an extension of the system FT of equality constraints over feature trees. We investigate the first-order theory of FT$_leq$ and its fragments in detail, both over finite trees and over possibly infinite trees. We prove that the first-order theory of FT$_leq$ is undecidable, in contrast to the first-order theory of FT which is well-known to be decidable. We show that the entailment problem of FT$_leq$ with existential quantification is PSPACE-complete. So far, this problem has been shown decidable, coNP-hard in case of finite trees, PSPACE-hard in case of arbitrary trees, and cubic time when restricted to quantifier-free entailment judgments. To show PSPACE-completeness, we show that the entailment problem of FT$_leq$ with existential quantification is equivalent to the inclusion problem of non-deterministic finite automata.},
      ANNOTE = {COLIURL : Muller:2001:FOT.pdf}
}

@TechReport{Niehren:1995,
      AUTHOR = {Niehren, Joachim},
      TITLE = {Functional Computation as Concurrent Computation},
      YEAR = {1995},
      NUMBER = {RR-95-14},
      ADDRESS = {Saarbrücken},
      TYPE = {Research Report},
      INSTITUTION = {DFKI}
}

@InProceedings{Niehren:1996,
      AUTHOR = {Niehren, Joachim},
      TITLE = {Functional Computation as Concurrent Computation},
      YEAR = {1996},
      BOOKTITLE = {23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '96), January 21-24},
      PAGES = {333-343},
      ADDRESS = {St. Petersburg Beach, Florida, USA},
      PUBLISHER = {ACM Press},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/POPL96.ps.gz},
      ABSTRACT = {We investigate functional computation as a special form of concurrent computation. As formal basis, we use a uniformly confluent core of the pi-calculus, which is also contained in models of higher-order concurrent constraint programming. We embed the call-by-need and the call-by-value lambda-calculus into the pi-calculus. We prove that call-by-need complexity is dominated by call-by-value complexity. In contrast to the recently proposed call-by-need lambda-calculus, our concurrent call-by-need model incorporates mutual recursion and can be extended to cyclic data structures by means of constraints.},
      NOTE = {longer version appeared as DFKI Research Report RR-95-14},
      ANNOTE = {COLIURL : Niehren:1996:FCC.pdf Niehren:1996:FCC.ps}
}

@TechReport{Niehren:1999,
      AUTHOR = {Niehren, Joachim},
      TITLE = {Uniform Confluence in Concurrent Computation},
      YEAR = {1999},
      ADDRESS = {Saarbrücken},
      TYPE = {Technical Report},
      INSTITUTION = {Universität des Saarlandes, Programming Systems Lab},
      URL = {http://www.ps.uni-sb.de/Papers/abstracts/Uniform:2000.html ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/Uniform-97.ps.gz},
      ABSTRACT = {Indeterminism is typical for concurrent computation. If several concurrent actors compete for the same resource then at most one of them may succeed, whereby the choice of the successful actor is indeterministic. As a consequence, the execution of a concurrent program may be nonconfluent. Even worse, most observables (termination, computational result, and time complexity) typically depend on the scheduling of actors created during program execution. This property contrast concurrent programs from purely functional programs. A functional program is uniformly confluent in the sense that all its possible executions coincide modulo reordering of execution steps. In this paper, we investigate concurrent programs that are uniformly confluent and their relation to eager and lazy functional programs. We study uniform confluence in concurrent computation within the applicative core of the $pi$-calculus which is widely used in different models of concurrent programming (with interleaving semantics). In particular, the applicative core of the $pi$-calculus serves as a kernel in foundations of concurrent constraint programming with first-class procedures (as provided by the programming language Oz). We model eager functional programming in the $lambda$-calculus with weak call-by-value reduction and lazy functional programming in the call-by-need amming in the $lambda$-calculus with standard reduction. As a measure of time complexity, we count application steps. We encode the $lambda$-calculus with both above reduction strategies into the applicative core of the $pi$-calculus and show that time complexity is preserved. Our correctness proofs employs a new technique based on uniform confluence and simulations. The strength of our technique is illustrated by proving a folk theorem, namely that the call-by-need complexity of a functional program is smaller than its call-by-value complexity.},
      ANNOTE = {COLIURL : Niehren:1999:UCC.pdf Niehren:1999:UCC.ps}
}

@Article{Niehren:2000,
      AUTHOR = {Niehren, Joachim},
      TITLE = {Uniform Confluence in Concurrent Computation},
      YEAR = {2000},
      JOURNAL = {Journal of Functional Programming},
      VOLUME = {10},
      NUMBER = {3},
      PAGES = {1-47},
      URL = {www.ps.uni-sb.de/Papers/abstracts/Uniform:99.html ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/Uniform:2000.ps.gz},
      ABSTRACT = {Indeterminism is typical for concurrent computation. If several concurrent actors compete for the same resource then at most one of them may succeed, whereby the choice of the successful actor is indeterministic. As a consequence, the execution of a concurrent program may be nonconfluent. Even worse, most observables (termination, computational result, and time complexity) typically depend on the scheduling of actors created during program execution. This property contrast concurrent programs from purely functional programs. A functional program is uniformly confluent in the sense that all its possible executions coincide modulo reordering of execution steps. In this paper, we investigate concurrent programs that are uniformly confluent and their relation to eager and lazy functional programs. We study uniform confluence in concurrent computation within the applicative core of the $pi$-calculus which is widely used in different models of concurrent programming (with interleaving semantics). In particular, the applicative core of the $pi$-calculus serves as a kernel in foundations of concurrent constraint programming with first-class procedures (as provided by the programming language Oz). We model eager functional programming in the $lambda$-calculus with weak call-by-value reduction and lazy functional programming in the call-by-need $lambda$-calculus with standard reduction. As a measure of time complexity, we count application steps. We encode the $lambda$-calculus with both above reduction strategies into the applicative core of the $pi$-calculus and show that time complexity is preserved. Our correctness proofs employs a new technique based on uniform confluence and simulations. The strength of our technique is illustrated by proving a folk theorem, namely that the call-by-need complexity of a functional program is smaller than its call-by-value complexity. A shortened version of this report will appear in the Journal of Functional Programming. Due to lack of space, this journal version does not contain the encoding of the $delta$-calculus (introduced in the paper) into the applicative core of the $pi$-calculus (given here), which is of its own interest.},
      ANNOTE = {COLIURL : Niehren:2000:UCC.pdf Niehren:2000:UCC.ps}
}

@InProceedings{Niehren_Koller:1998,
      AUTHOR = {Niehren, Joachim and Koller, Alexander},
      TITLE = {Dominance Constraints in Context Unification},
      YEAR = {1998},
      BOOKTITLE = {3rd International Conference on Logical Aspects of Computational Linguistics (LACL '98), December 14-16},
      NUMBER = {2014},
      PAGES = {199-218},
      EDITOR = {Moortgat, M.},
      SERIES = {Lecture Notes in Artificial Intelligence},
      ADDRESS = {Grenoble, France},
      PUBLISHER = {Springer},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/Dominance-98.ps.gz},
      ABSTRACT = {Tree descriptions based on dominance constraints are popular in several areas of computational linguistics including syntax, semantics, and discourse. Tree descriptions in the language of context unification have attracted some interest in unification and rewriting theory. Recently, dominance constraints and context unification have both been used in different underspecified approaches to the semantics of scope, parallelism, and their interaction. This raises the question whether both description languages are related. In this paper, we show for a first time that dominance constraints can be expressed in context unification. We also prove that dominance constraints extended with parallelism constraints are equal in expressive power to context unification.},
      ANNOTE = {COLIURL : Niehren:1998:DCC.pdf Niehren:1998:DCC.ps}
}

@InProceedings{Niehren_et_al:1997,
      AUTHOR = {Niehren, Joachim and Müller, Martin and Podelski, Andreas},
      TITLE = {Inclusion Constraints over Non-Empty Sets of Trees},
      YEAR = {1997},
      BOOKTITLE = {7th International Joint Conference CAAP/ FASE. Theory and Practice of Software Development (TAPSOFT '97), April 14-18},
      NUMBER = {1214},
      PAGES = {217-231},
      EDITOR = {Bidoit, M. and Dauchet, M.},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {Lille, France},
      PUBLISHER = {Springer},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/ines97.ps.gz},
      ABSTRACT = {We present a new constraint system called Ines. Its constraints are conjunctions of inclusions $t_1subseteq t_2$ between first-order terms (without set operators) which are interpreted over non-empty sets of trees. The existing systems of set constraints can express Ines constraints only if they include negation. Their satisfiability problem is NEXPTIME-complete. We present an incremental algorithm that solves the satisfiability problem of Ines constraints in cubic time. We intend to apply Ines constraints for type analysis for a concurrent constraint programming language.},
      ANNOTE = {COLIURL : Niehren:1997:ICN.pdf Niehren:1997:ICN.ps}
}

@TechReport{Niehren_et_al:1998,
      AUTHOR = {Niehren, Joachim and Müller, Martin and Talbot, Jean-Marc},
      TITLE = {Entailment of Atomic Set Constraints is PSPACE-Complete},
      YEAR = {1998},
      ADDRESS = {Saarbrücken},
      TYPE = {Technical Report},
      INSTITUTION = {Universität des Saarlandes, Programming Systems Lab},
      URL = {www.ps.uni-sb.de/Papers/abstracts/atomic-lics-99.html ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/atomic:98.ps.gz},
      ABSTRACT = {The complexity of set constraints has been extensively studied over the last years and was often found quite high. At the lower end of expressiveness, there are atomic set constraints which are conjunctions of inclusions $t_1subseteq t_2$ between first-order terms without set operators. It is well-known that satisfiability of atomic set constraints can be tested in cubic time. Also, entailment of atomic set constraints has been claimed decidable in polynomial time. We refute this claim. We show that entailment between atomic set constraints can express quantified boolean formulas and is thus PSPACE hard. For infinite signatures, we also present a PSPACE-algorithm for solving atomic set constraints with negation. This proves that entailment of atomic set constraints is PSPACE-complete for infinite signatures. In case of finite signatures, the problem is even DEXPTIME-hard.},
      ANNOTE = {COLIURL : Niehren:1998:EAS.pdf Niehren:1998:EAS.ps}
}

@InProceedings{Niehren_et_al:1999,
      AUTHOR = {Niehren, Joachim and Müller, Martin and Talbot, Jean-Marc},
      TITLE = {Entailment of Atomic Set Constraints is PSPACE-Complete},
      YEAR = {1999},
      BOOKTITLE = {14th Annual IEEE Symposium on Logic in Computer Science (LICS '99), July 2-5},
      PAGES = {285-294},
      ADDRESS = {Trento, Italy},
      PUBLISHER = {IEEE Press},
      URL = {www.ps.uni-sb.de/Papers/abstracts/atomic:98.html ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/atomic-lics-99.ps.gz},
      ABSTRACT = {The complexity of set constraints has been extensively studied over the last years and was often found quite high. At the lower end of expressiveness, there are atomic set constraints which are conjunctions of inclusions t1 $subseteq$ t2 between first-order terms without set operators. It is well-known that satisfiability of atomic set constraints can be tested in cubic time. Also, entailment of atomic set constraints has been claimed decidable in polynomial time. We refute this claim. We show that entailment between atomic set constraints can express validity of quantified boolean formulas and is thus PSPACE hard. For infinite signatures, we also present a PSPACE-algorithm for solving atomic set constraints with negation. This proves that entailment of atomic set constraints is PSPACE-complete for infinite signatures. In case of finite signatures, this problem is even DEXPTIME-hard.},
      ANNOTE = {COLIURL : Niehren:1999:EAS.pdf Niehren:1999:EAS.ps}
}

@InProceedings{Niehren_et_al:1997_1,
      AUTHOR = {Niehren, Joachim and Pinkal, Manfred and Ruhrberg, Peter},
      TITLE = {On Equality up-to Constraints over Finite Trees, Context Unification and One-Step Rewriting},
      YEAR = {1997},
      BOOKTITLE = {14th International Conference on Automated Deduction (CADE 14), July 13-17},
      NUMBER = {1249},
      PAGES = {34-48},
      EDITOR = {McCune, W.},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {Townsville, Australia},
      PUBLISHER = {Springer},
      URL = {Full version available from http://www.ps.uni-sb.de/Papers/abstracts/fullContext.html},
      ABSTRACT = {We introduce equality up-to constraints over finite trees and investigate their expressiveness. Equality up-to constraints subsume equality constraints, subtree constraints, and one-step rewriting constraints. We establish a close correspondence between equality up-to constraints over finite trees and context unification. Context unification subsumes string unification and is subsumed by linear second-order unification. We obtain the following three new results. The satisfiability problem of equality up-to constraints is equivalent to context unification, which is an open problem. The positive existential fragment of the theory of one-step rewriting is decidable. The $exists^*forall^*exists^*$ fragment of the theory of context unification is undecidable.},
      ANNOTE = {COLIURL : Niehren:1997:ECF.pdf Niehren:1997:ECF.ps}
}

@InProceedings{Niehren_et_al:1997_2,
      AUTHOR = {Niehren, Joachim and Pinkal, Manfred and Ruhrberg, Peter},
      TITLE = {A Uniform Approach to Underspecification and Parallelism},
      YEAR = {1997},
      BOOKTITLE = {35th Annual Meeting of the Association of Computational Linguistics (ACL), July 7-12},
      PAGES = {410-417},
      EDITOR = {Cohen, P. R. and Wahlster, Wolfgang},
      ADDRESS = {Madrid, Spain},
      PUBLISHER = {ACL},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/Ellipses.ps.gz},
      ABSTRACT = {We propose a unified framework in which to treat semantic underspecification and parallelism phenomena in discourse. The framework employs a constraint language that can express equality and subtree relations between finite trees. In addition, our constraint language can express the equality up-to relation over trees which captures parallelism between them. The constraints are solved by context unification. We demonstrate the use of our framework at the examples of quantifier scope, ellipses, and their interaction.},
      ANNOTE = {COLIURL : Niehren:1997:UAU.pdf Niehren:1997:UAU.ps}
}

@TechReport{Niehren_Priesnitz:1999,
      AUTHOR = {Niehren, Joachim and Priesnitz, Tim},
      TITLE = {Characterizing Subtype Entailment in Automata Theory},
      YEAR = {1999},
      ADDRESS = {Saarbrücken},
      TYPE = {Technical Report},
      INSTITUTION = {Universität des Saarlandes},
      URL = {http://www.ps.uni-sb.de/Papers/abstracts/pauto.html ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/pauto.ps.gz},
      ABSTRACT = {Subtype entailment is the entailment problem of subtype constraints for some type language. Understanding the algorithmic properties of subtype entailment is relevant to several subtype inference systems. For simple types, subtype entailment is coNP complete; when extended with recursive types it becomes PSPACE complete. Adding the least and greatest type renders subtyping non-structural. Whether non-structural subtype entailment is decidable is a prominent open problem. We characterize subtype entailment in automata theory. This yields a uniform proof method by which all known complexity results on subtype entailment in the literature can be derived. The main contribution of the paper is an equivalent characterization of non-structural subtype entailment in automata theory (by so called P-automata). On the one hand side, our characterization implies that several variants of non-structural subtype entailment are polynomial time equivalent (with or without contravariant function types or recursive types). This robustness result is new and nontrivial. On the other hand side, we believe that our characterization contributes an important and necessary step towards answering the open question on decidability of non-structural subtype entailment.},
      ANNOTE = {COLIURL : Niehren:1999:CSE.pdf Niehren:1999:CSE.ps}
}

@InProceedings{Niehren_Priesnitz:1999_1,
      AUTHOR = {Niehren, Joachim and Priesnitz, Tim},
      TITLE = {Entailment of Non-Structural Subtype Constraints},
      YEAR = {1999},
      BOOKTITLE = {Asian Computing Science Conference, December 10-12},
      NUMBER = {1742},
      PAGES = {251-265},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {Phuket, Thailand},
      PUBLISHER = {Springer},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/SubTypeEntailment:99.ps.gz},
      ABSTRACT = {Entailment of subtype constraints was introduced for constraint simplification in subtype inference systems. Designing an efficient algorithm for subtype entailment turned out to be surprisingly difficult. The situation was clarified by Rehof and Henglein who proved entailment of structural subtype constraints to be coNP-complete for simple types and PSPACE-complete for recursive types. For entailment of non-structural subtype constraints of both simple and recursive types they proved PSPACE-hardness and conjectured PSPACE-completeness but failed in finding a complete algorithm. In this paper, we investigate the source of complications and isolate a natural subproblem of non-structural subtype entailment that we prove PSPACE-complete. We conjecture (but this is left open) that the presented approach can be extended to the general case.},
      ANNOTE = {COLIURL : Niehren:1999:ENS.pdf Niehren:1999:ENS.ps}
}

@Article{Niehren_et_al:2000,
      AUTHOR = {Niehren, Joachim and Treinen, Ralf and Tison, Sophie},
      TITLE = {On Rewrite Constraints and Context Unification},
      YEAR = {2000},
      JOURNAL = {Information Processing Letters},
      VOLUME = {74},
      NUMBER = {1-2},
      PAGES = {35-40},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/rewrite-context.ps.gz},
      ABSTRACT = {We show that stratified context unification, which is one of the most expressive fragments of context unification known to be decidable, is equivalent to the satisfiability problem of slightly generalized rewriting constraints.},
      ANNOTE = {COLIURL : Niehren:2000:RCC.pdf Niehren:2000:RCC.ps}
}

@InProceedings{Erk_Niehren:2003,
      AUTHOR = {Erk, Katrin and Niehren, Joachim},
      TITLE = {Well-Nested Parallelism Constraints for Ellipsis Resolution},
      YEAR = {2003},
      BOOKTITLE = {Proceedings of EACL'03},
      ADDRESS = {Budapest},
      URL = {http://www.ps.uni-sb.de/Papers/abstracts/wellnested.html}
}

@InProceedings{Fuchss_et_al:2004,
      AUTHOR = {Fuchss, Ruth and Koller, Alexander and Niehren, Joachim and Thater, Stefan},
      TITLE = {Minimal Recursion Semantics as Dominance Constraints: Translation, Evaluation, and Analysis},
      YEAR = {2004},
      BOOKTITLE = {Proceedings of the 42nd ACL},
      ADDRESS = {Barcelona}
}

@InProceedings{Koller_et_al:2003,
      AUTHOR = {Koller, Alexander and Niehren, Joachim and Thater, Stefan},
      TITLE = {Bridging the Gap between Underspecification Formalisms: Hole Semantics as Dominance Constraints},
      YEAR = {2003},
      BOOKTITLE = {Proceedings of the 10th Conference of The European Chapter of the Association for Computational Linguistics},
      PAGES = {195--202},
      ADDRESS = {Budapest, Hungary},
      URL = {Koller:2003:BGB}
}

@InProceedings{Niehren_Thater:2003,
      AUTHOR = {Niehren, Joachim and Thater, Stefan},
      TITLE = {Bridging the Gap between Underspecification Formalisms: Minimal Recursion Semantics as Dominance Constraints},
      YEAR = {2003},
      BOOKTITLE = {Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics},
      PAGES = {367--374},
      ADDRESS = {Sapporo, Japan}
}

@InProceedings{Fuchss_et_al:2003,
      AUTHOR = {Fuchss, Ruth and Niehren, Joachim and Thater, Stefan},
      TITLE = {Minimal Recursion Semantics as Dominance Constraints: A Preliminary Evaluation},
      YEAR = {2003},
      BOOKTITLE = {Prospects and Advances in the Syntax/Semantics Interface},
      PAGES = {51--55},
      ADDRESS = {Nancy, France}
}