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




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

@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{Podelski_et_al:1997,
      AUTHOR = {Podelski, Andreas and Charatonik, Witold and Müller, Martin},
      TITLE = {Set-Based Error Diagnosis of Concurrent Constraint Programs},
      YEAR = {1997},
      MONTH = {December},
      ADDRESS = {Saarbrücken},
      TYPE = {Technical Report},
      INSTITUTION = {Universität des Saarlandes},
      URL = {http://www.ps.uni-sb.de/Paper/abstracts/Diagnosis-97.html ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/Diagnosis-97.ps.gz},
      ABSTRACT = {We present an automated method for the static prediction of the run-time error 'deadlock or failure' in concurrent constraint programs. The method is based on a new set-based analysis of reactive logic programs which computes an approximation of the greatest-model semantics. Semantically, the method is based on the connection between the inevitability of 'deadlock or failure' in concurrent constraint programs, finite failure in logic programming and the greatest-model semantics over infinite trees.},
      ANNOTE = {COLIURL : Podelski:1997:SBE.pdf Podelski:1997:SBE.ps}
}

@InProceedings{Podelski_et_al:1999,
      AUTHOR = {Podelski, Andreas and Charatonik, Witold and Müller, Martin},
      TITLE = {Set-Based Failure Analysis for Logic Programs and Concurrent Constraint Programs},
      YEAR = {1999},
      BOOKTITLE = {8th European Symposium of Programming (ESOP '99). Programming Languages and Systems, March 22-28},
      NUMBER = {1576},
      PAGES = {177-192},
      EDITOR = {Swierstra, S. Doaitse},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {Amsterdam, The Netherlands},
      PUBLISHER = {Springer},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/esop99.ps.gz},
      ABSTRACT = {This paper presents the first approximation method of the finite-failure set of a logic program by set-based analysis. In a dual view, the method yields a type analysis for programs with ongoing behaviors (perpetual processes). Our technical contributions are (1) the semantical characterization of finite failure of logic programs over infinite trees and (2) the design and soundness proof of the first set-based analysis of logic programs with the greatest-model semantics. Finally, we exhibit the connection between finite failure and the inevitability of the 'inconsistent-store' error in fair executions of concurrent constraint programs where no process suspends forever. This indicates a potential application to error diagnosis for concurrent constraint programs.},
      ANNOTE = {COLIURL : Podelski:1999:SBF.pdf Podelski:1999:SBF.ps}
}

@InProceedings{Podelski_Smolka:1995,
      AUTHOR = {Podelski, Andreas and Smolka, Gert},
      TITLE = {Situated Simplification},
      YEAR = {1995},
      BOOKTITLE = {1st Conference on Principles and Practice of Constraint Programming, September},
      NUMBER = {976},
      PAGES = {328-344},
      EDITOR = {Montanari, U.},
      SERIES = {Lecture Notes in Computer Science},
      ADDRESS = {Cassis, France},
      PUBLISHER = {Springer},
      URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/SituSimpliTCS.ps.gz},
      ABSTRACT = {Testing satisfaction of guards is the essential operation of concurrent constraint programming (CCP) systems. We present and prove correct, for the first time, an incremental algorithm for the simultaneous tests of entailment and disentailment of rational tree constraints to be used in CCP systems with deep guards (e.g., AKL or Oz). The algorithm is presented as the simplification of the constraints which form the (possibly deep) guards and which are situated at different nodes (or, local computation spaces) in a tree (of arbitrary depth). In this algorithm, each variable may have multiple bindings (representing multiple constraints on the same variable in different nodes). These may be realized by re- and de-installation upon each newly resumed check of the guard in the corresponding node (as done, e.g., in AKL or Oz), or by using look-up tables (with entries indexed by the nodes). We give a simple fixed-point algorithm and use it for proving that the tests implemented by another, practical algorithm are correct and complete for entailment and disentailment. We formulate the results in this paper for rational tree constraints; they can be adapted to finite and feature trees.},
      ANNOTE = {COLIURL : Podelski:1995:SS.pdf Podelski:1995:SS.ps}
}

@Article{Podelski_Smolka:1997,
      AUTHOR = {Podelski, Andreas and Smolka, Gert},
      TITLE = {Situated Simplification},
      YEAR = {1997},
      JOURNAL = {Theoretical Computer Science},
      VOLUME = {173},
      PAGES = {209-233}
}