(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