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




@InProceedings{Backofen_Treinen:1994,
      AUTHOR = {Backofen, Rolf and Treinen, Ralf},
      TITLE = {How to Win a Game with Features},
      YEAR = {1994},
      BOOKTITLE = {1st International Conference on Constraints in Computational Logics (CCL'94), September 7-9},
      VOLUME = {845},
      PAGES = {320-335},
      EDITOR = {Jouannaud, J.-P.},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {München, Germany},
      PUBLISHER = {Springer},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/FeatureGamesCCL94.dvi.Z ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/FeatureGamesCCL94.entry ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/FeatureGamesCCL94.ps.Z},
      ANNOTE = {COLIURL : Backofen:1994:HWG.pdf Backofen:1994:HWG.ps Backofen:1994:HWG.dvi}
}

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

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

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