Set Constraints: a Pearl in Research on Constraints (1997)  (Make Corrections)  (17 citations)
Leszek Pacholski, Andreas Podelski
Principles and Practice of Constraint Programming

  Home/Search   Context   Related

Links:   DBLP

 
View or download:
mpisb.mpg.de/~podelski/p...tutorial.ps
ag2.mpisb.mpg.de/~podels...tutorial.ps
Cached:  PS.gz  PS  PDF  Image  Update  Help

From:  mpisb.mpg.de/~podelski/papers (more)
(Enter author homepages)

Rate this article: (best)
  Comment on this article  
(Enter summary)

Abstract: . The topic of set constraints is a pearl among the research topics on constraints. It combines theoretical investigations (ranging from logical expressiveness, decidability, algorithms and complexity analysis to program semantics and domain theory) with practical experiments in building systems for program analysis, addressing questions like implementation issues and scalability. The research has its direct applications in type inference, optimization and verification of imperative,... (Update)

Context of citations to this paper:   More

...Their main application is set based analysis and type inference for functional, imperative and logic programming languages. See [22] for a recent survey this is a very active field, and it would be too long to list all relevant papers. Even the number of variants of set...

.... that queries over this logic (see Section 6) cannot express the classes of tree set constraints used most frequently in program analysis [3, 27]. VC dimension We now show that the behavior of definable families in T p and T formula is not as tame as in a term algebra. A standard...

Cited by:   More
Atomic Set Constraints with Projection - Witold Charatonik And (2002)   (Correct)
Finite Set Constraints in Oz - Müller, Müller   (Correct)
Set-Based Failure Analysis for Logic Programs and.. - Podelski, Charatonik, .. (1999)   (Correct)

Active bibliography (related documents):   More   All
1.4:   Set Constraints with Intersection - Charatonik, Podelski   (Correct)
0.9:   Set Constraints and Set-Based Analysis - Heintze, Jaffar (1994)   (Correct)
0.8:   Ezy Mnogo'sciowe W Pewnych Teoriach R'owno'sciowych - Witold Charatonik   (Correct)

Similar documents based on text:   More   All
1.0:   Entailment of Atomic Set Constraints is PSPACE-Complete - Niehren, Müller, Talbot (1998)   (Correct)
0.8:   Entailment of Set Constraints is not Feasible - Müller, Niehren (1997)   (Correct)
0.4:   Inclusion Constraints over Non-empty Sets of Trees - Müller, Niehren, Podelski (1997)   (Correct)

Related documents from co-citation:   More   All
10:   Set constraints and set-based analysis - Heintze, Jaffar - 1994
9:   applications and future directions (context) - Aiken, Results - 1994
9:   Solving classes of set constraints with tree automata - Devienne, Talbot et al. - 1997

BibTeX entry:   (Update)

L. Pacholski and A. Podelski. Set Constraints: A Pearl in Research on Constraints (Tutorial Abstract). In G. Smolka, editor, Proceedings of the Third International Conference on Principles and Practive of Constraint Programming, volume 1330 of Lecture Notes in Computer Science. Springer-Verlag, 1997. http://citeseer.ist.psu.edu/pacholski97set.html   More

@inproceedings{ pacholski97set,
    author = "Leszek Pacholski and Andreas Podelski",
    title = "Set Constraints: A Pearl in Research on Constraints",
    booktitle = "Principles and Practice of Constraint Programming",
    pages = "549-562",
    year = "1997",
    url = "citeseer.ist.psu.edu/pacholski97set.html" }
Citations (may not include all citations):
266   The Oz programming model - Smolka - 1995  ACM   DBLP
195   Flow analysis and optimization of lisp-like structures (context) - Jones, Muchnick - 1979  ACM   DBLP
176   Type inclusion constraints and type inference - Aiken, Wimmers - 1993  ACM   DBLP
160   Set based analysis of ML programs (context) - Heintze - 1993
160   Set based analysis of ML programs (context) - Heintze - 1994
159   Theoretical Computer Science (context) - Kozen, set - 1996  ACM
148   Automata-theoretic techniques for modal logics of programs (context) - Vardi, Wolper - 1986  ACM   DBLP
140   Soft typing with conditional types - Aiken, Wimmers et al. - 1994  ACM   DBLP
128   Set based program analysis (context) - Heintze - 1992  ACM
119   An automata-theoretic approach to linear-temporal logic - Vardi - 1996
113   Akademiai Kiado (context) - G'ecseg, Steinby - 1984
109   Solving systems of set constraints (context) - Aiken, Wimmers - 1992
92   A finite presentation theorem for approximating logic progra.. - Heintze, Jaffar - 1990  ACM   DBLP
92   A finite presentation theorem for approximating logic progra.. - Heintze, Jaffar - 1990  ACM   DBLP
87   Towards a theory of types in Prolog (context) - Mishra - 1984  DBLP
86   A type system equivalent to flow analysis - Palsberg - 1995  ACM   DBLP
81   A decision procedure for a class of set constraints - Heintze, Jaffar - 1990
80   Handbook of Theoretical Computer Science (context) - Thomas - 1990  ACM
75   Set constraints are the monadic class - Bachmair, Ganzinger et al. - 1993  DBLP
72   semantics and abstract interpretation (context) - Cousot, Cousot - 1992
66   Declaration-free type checking (context) - Mishra, Reddy - 1985  ACM   DBLP
63   Automatic computation of data set definitions (context) - Reynolds - 1969  DBLP
57   The complexity of set constraints - Aiken, Kozen et al. - 1993  ACM   DBLP
56   Solvable Cases of the Decision Problem (context) - Ackermann - 1954
53   Static type inference in a dynamically typed language - Aiken, Murphy - 1991  ACM   DBLP
53   Safety analysis versus type inference - Palsberg, Schwartzbach - 1995  ACM   DBLP
52   Decidability of systems of set constraints with negative con.. - Aiken, Kozen et al. - 1995  ACM   DBLP
52   Logic programming with sets - Kuper - 1990  ACM   DBLP
50   Solving systems of set constraints with negated subset relat.. (context) - Gilleron, Tison et al. - 1993  DBLP
50   Solving systems of set constraints with negated subset relat.. (context) - Gilleron, Tison et al. - 1993  DBLP
49   grammar and set-constraint-based program analysis by abstrac.. (context) - Cousot, Cousot - 1995
49   Logic programs as types for logic programs - Fruhwirth, Shapiro et al. - 1991  DBLP
48   A type system for logic programs (context) - Yardeni, Shapiro - 1987  ACM   DBLP
48   A type system for logic programs (context) - Yardeni, Shapiro - 1991  ACM   DBLP
47   Resolution strategies as decision procedures (context) - Joyner - 1979  ACM   DBLP
46   Implementing regular tree expressions - Aiken, Murphy - 1991  ACM   DBLP
45   Haskell overloading is DEXPTIME-complete (context) - Seidl - 1994  ACM   DBLP
44   Set constraints with projections are in NEXPTIME - Charatonik, Pacholski - 1994  DBLP
42   Negative set constraints with equality - Charatonik, Pacholski - 1994  DBLP
41   Interval Propagation to Reason about Sets: Definition and Im.. (context) - Gervet - 1997  DBLP
39   Set constructors in a logic database language (context) - Beeri, Nagvi et al. - 1991  ACM   DBLP
39   Type inference with partial types (context) - Thatte - 1988  ACM   DBLP
38   Set constraints with intersection - Charatonik, Podelski - 1997  ACM   DBLP
34   Embedding Extensional Finite Sets in CLP - Dovier, Rossi - 1993  ACM   DBLP
34   Solving systems of set constraints using tree automata (context) - Gilleron, Tison et al. - 1993  ACM   DBLP
34   Logical aspects of set constraints - Kozen - 1993  ACM   DBLP
33   A regular type language for logic programs (context) - Dart, Zobel - 1992  DBLP
33   Linear-time subtransitive control-flow analysis - Heintze, McAllester - 1997
32   An engine for logic program analysis - Heintze, Jaffar - 1992  DBLP
32   Conjunto: Constraint logic programming with finite set domai.. - Gervet - 1994  DBLP
30   Polymorphically typed logic programs - Yardeni, Fruhwirth et al. - 1992  DBLP
29   Solving classes of set constraints with tree automata - Devienne, Talbot et al. - 1997  DBLP
27   Making set-constraint based program analyses scale (context) - Fahndrich, Aiken - 1996
26   Systems of set constraints with negative constraints are NEX.. (context) - Stefansson - 1994  ACM   DBLP
23   Experience with a type evaluator (context) - Young, O'Keefe - 1988
21   Set-based analysis of reactive infinitestate systems - Podelski, Charatonik et al. - 1997
20   Constraint Logic Programming with Regular Sets (context) - Walinsky, Sigma - 1989
19   Short Overview of the CLPS System (context) - Legeard, Legros - 1991  DBLP
19   Membership-constraints and complexity in logic programming w.. - Stolzenburg - 1996  DBLP
19   the cubic bottleneck in subtyping and flow analysis - Heintze, McAllester - 1997
19   Semantic Types for Logic Programs (context) - Heintze, Jaffar - 1992  DBLP
18   Set constraints and logic programming - Kozen - 1994  ACM   DBLP
17   applications and future directions (context) - Aiken, Results - 1994
17   Tarskian set constraints - McAllester, Givan et al. - 1996  ACM   DBLP
17   Practical model-based static analysis for definite logic pro.. - Gallagher, Boulanger et al. - 1995  ACM   DBLP
16   Inclusion constraints over non-empty sets of trees - Muller, Niehren et al. - 1997  ACM   DBLP
16   Compiling intensional sets in CLP - Bruscoli, Dovier et al. - 1994  ACM   DBLP
16   Theoretical Computer Science (context) - Slutzki, automata - 1985  ACM
14   Regular approximation of computation paths in logic and func.. - Gallagher, Lafave - 1996  ACM   DBLP
14   Rational spaces and set constraints - Kozen - 1995  ACM   DBLP
13   Systematic realisation of control flow analyses for CML - Gasser, Nielson et al. - 1997  ACM   DBLP
13   A complete Gentzen-style axiomatization for set constraints - Cheng, Kozen - 1996  ACM   DBLP
12   The independence property of a class of set constraints - Charatonik, Podelski - 1996  DBLP
11   intersection types and recursive types (context) - Damm, union - 1994
11   Some new decidability results on positive and negative set c.. (context) - Gilleron, Tison et al. - 1994  ACM   DBLP
11   Sorted unification using set constraints - Uribe - 1992  ACM   DBLP
11   Computable Set Theory and Logic Programming (context) - Dovier - 1996
9   Set based analysis of arithmetic (context) - Heintze - 1993  ACM
9   Tree Automata and Languages - Nivat, Podelski - 1992  ACM   DBLP
8   Type Analysis for a Higher-Order Concurrent Constraint Langu.. (context) - Muller - 1997
8   A demand-driven set-based analysis - Biswas - 1997  ACM   DBLP
8   the complexity of set-based analysis - McAllester, Heintze
7   Set constraints in some equational theories (context) - Charatonik - 1995  ACM   DBLP
7   Uber Moglichkeiten im Relativkalkul (context) - Lowenheim - 1915
7   Set constraints in some equational theories (context) - Charatonik  ACM   DBLP
6   Set Intervals in Constraint-Logic Programming: Definition an.. (context) - Gervet - 1995
6   Max-Planck-Institut fur Informatik (context) - Charatonik, Podelski et al. - 1997
6   Laboratoire d'Informatique Fondamentale de Lille (context) - Bogaert, Tison et al. - 1991
6   Laboratoire d'Informatique Fondamentale de Lille (context) - Gilleron, Tison et al. - 1996
4   Ordering constraints over feature trees - Muller, Niehren et al. - 1997  ACM   DBLP
4   Finite set constraints in Oz (context) - Muller, Muller - 1997
4   Grid structures and undecidable constraint theories (context) - Seynhave, Tommasi et al. - 1997  ACM   DBLP
4   Delayed logic and finite state machines (context) - Arden - 1961
3   Finite Set Intervals (context) - Puget - 1996
3   Weizmann Institute of Science (context) - Yardeni, system et al. - 1987
2   Negative set constraints: an easy proof of decidability (context) - Charatonik, Pacholski - 1993
1   Presented at the Workshop on Set Constraints (context) - Foster, SC et al. - 1996
1   Theorical Computer Science (context) - Brzozowski, Leiss et al. - 1980



The graph only includes citing articles where the year of publication is known.


Documents on the same site (http://www.mpi-sb.mpg.de/~podelski/papers.html):   More
Directional Type Inference for Logic Programs - Charatonik, Podelski (1998)   (Correct)
Inclusion Constraints over Non-empty Sets of Trees - Müller, Niehren, Podelski (1997)   (Correct)
Ordering Constraints over Feature Trees - Müller, Niehren, Podelski (1997)   (Correct)

Online articles have much greater impact   More about CiteSeer.IST   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST - Copyright Penn State and NEC