Decidability of Systems of Set Constraints with Negative Constraints (1994)  (Make Corrections)  (52 citations)
A. Aiken, D. Kozen, Ed Wimmers
Information and Computation

  Home/Search   Context   Related

 
View or download:
brics.dk/RS/94/Ref...ICSRS9432.ps.gz
Cached:  PS.gz  PS  PDF  Image  Update  Help

From:  brics.dk/RS/94/Ref/BRICSRS94... (more)
(Enter author homepages)

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

Abstract: Set constraints are relations between sets of terms. They have been used extensively in various applications in program analysis and type inference. Recently, several algorithms for solving general systems of positive set constraints have appeared. In this paper we consider systems of mixed positive and negative constraints, which are considerably more expressive than positive constraints alone. We show that it is decidable whether a given such system has a solution. The proof involves a ... (Update)

Context of citations to this paper:   More

...and flow analysis. Set constraints are related to the subtyping constraints and form the basis of several program analyses [2, 1, 7, 8, 5, 17]. The applications of type systems with subtyping have motivated the study of the complexity and the decidability of the subtyping...

.... to basic set constraints have also been de ned: in particular, we consider those adding projections and negative constraints e 1 6 e 2 [4, 24]. In this paper we will refer to this kind of set based constraints as Set Inclusion constraints (abbreviated as SI constraints)...

Cited by:   More
The complete list of RTA open problems - Date April Summary   (Correct)
Structural Subtyping of Non-Recursive Types is Decidable - Viktor Kuncak And (2003)   (Correct)
Atomic Set Constraints with Projection - Witold Charatonik And (2002)   (Correct)

Similar documents (at the sentence level):
74.8%:   Decidability of Systems of Set Constraints with Negative.. - Aiken, Kozen, Wimmers (1995)   (Correct)

Active bibliography (related documents):   More   All
0.4:   The Complexity of Set Constraints - Aiken, Kozen, Vardi, Wimmers (1993)   (Correct)
0.2:   Logical Aspects of Set Constraints - Kozen (1993)   (Correct)
0.2:   Some Notes on Rational Spaces - Cheng, Kozen (1996)   (Correct)

Similar documents based on text:   More   All
0.8:   On the Comparison Complexity of the String.. - Breslauer, Colussi.. (1995)   (Correct)
0.8:   The Girard Translation Extended with Recursion - Braüner (1995)   (Correct)
0.8:   Dynamic Algorithms for the Dyck Languages - Frandsen, Husfeldt, Miltersen.. (1995)   (Correct)

Related documents from co-citation:   More   All
40:   Solving systems of set constraints with negated subset relationships (context) - Gilleron, Tison et al. - 1993
39:   A decision procedure for a class of set constraints - Heintze, Jaffar - 1990
37:   Set constraints are the monadic class - Bachmair, Ganzinger et al. - 1993

BibTeX entry:   (Update)

A. Aiken, D. Kozen, and E. L. Wimmers. Decidability of systems of set constraints with negative constraints. Information and Computation, 122(1):30--44, Oct. 1995. http://citeseer.ist.psu.edu/aiken94decidability.html   More

@article{ aiken95decidability,
    author = "Alexander Aiken and Dexter Kozen and Edward L. Wimmers",
    title = "Decidability of Systems of Set Constraints with Negative Constraints",
    journal = "Information and Computation",
    volume = "122",
    number = "1",
    pages = "30-44",
    year = "1995",
    url = "citeseer.ist.psu.edu/aiken94decidability.html" }
Citations (may not include all citations):
195   Flow analysis and optimization of LISPlike structures (context) - Jones, Muchnick - 1979
109   Solving systems of set constraints (context) - Aiken, Wimmers - 1992
87   Towards a theory of types in PROLOG (context) - Mishra - 1984
81   A decision procedure for a class of set constraints - Heintze, Jaffar - 1990
75   Set constraints are the monadic class - Bachmair, Ganzinger et al. - 1993
66   Declaration-free type checking (context) - Mishra, Reddy - 1985
63   Automatic computation of data set definitions (context) - Reynolds - 1969
58   Springer-Verlag (context) - Cox, Little et al. - 1992
57   The complexity of set constraints - Aiken, Kozen et al.
52   Decidability of systems of set constraints with negative con.. - Aiken, Kozen et al. - 1993
46   Implementing regular tree expressions - Aiken, Murphy
34   Solving systems of set constraints using tree automata (context) - Gilleron, Tison et al. - 1993
23   Experience with a type evaluator (context) - Young, O'Keefe
10   On equations for regular languages (context) - Brzozowski, Leiss - 1980
7   Systems of negative Boolean constraints (context) - Marriott, Odersky - 1992



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


Documents on the same site (http://www.brics.dk/RS/94/Ref/BRICS-RS-94-Ref/):   More
A Fractal which violates the Axiom of Determinacy - Riis (1994)   (Correct)
Complexity of Nondeterministic Functions - Andreev (1994)   (Correct)
A Constraint Oriented Proof Methodology based on Modal.. - Larson, al. (1994)   (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