(Enter summary)
Abstract: Systems of set constraints describe relations between
sets of ground terms. They have been successfully
used in program analysis and type inference. So far
two proofs of decidability of mixed set constraints have
been given: by R. Gilleron, S. Tison and M. Tommasi
[12] and A. Aiken, D. Kozen, and E.L. Wimmers [3].
However, both these proofs are long, involved and do
not seem to extend to more general set constraints.
Our approach is based on a reduction of set constraints
to the monadic class... (Update)
Context of citations to this paper: More
.... by positive set constraints only [16] The expressiveness of INES constraints is subsumed by that of set constraints with negation [9, 16]. In the case of finite trees, the satisfiability problem of set constraints with negation is known to be decidable [1, 13] it is complete...
.... [25] The complexity of the satisfiability problem for various classes of set constraints has been widely studied [17, 20, 10, 3, 6, 18, 4, 11, 12, 3, 35, 29] and was often found to be very high (e.g. NEXPTIME complete [35, 3] and DEXPTIMEcomplete [14] At the lower end of...
Cited by: More
The complete list of RTA open problems - Date April Summary
(Correct)
Disunification in ACI1 Theories - Dovier, Piazza, Pontelli (1999)
(Correct)
Atomic Set Constraints with Projection - Witold Charatonik And (2002)
(Correct)
Similar documents (at the sentence level):
16.0%: Ezy Mnogo'sciowe W Pewnych Teoriach R'owno'sciowych - Witold Charatonik
(Correct)
5.5%: Set constraints with projections are in NEXPTIME - Charatonik, Pacholski (1994)
(Correct)
Active bibliography (related documents): More All
0.6: Set Constraints: a Pearl in Research on Constraints - Pacholski, Podelski (1997)
(Correct)
0.3: The Complexity of Set Constraints - Aiken, Kozen, Vardi, Wimmers (1993)
(Correct)
0.3: Some Notes on Rational Spaces - Cheng, Kozen (1996)
(Correct)
Similar documents based on text: More All
0.8: VII Seminarium " Warszawsko - Wroclawskie" z Teorii Informatyki - Sokolowski, al. (1993)
(Correct)
0.6: Tarskian Set Constraints are in NEXPTIME - Mielniczuk, Pacholski (1998)
(Correct)
0.4: Set Constraints and Automata - Gilleron, Tison, Tommasi (1996)
(Correct)
Related documents from co-citation: More All
34: Set constraints are the monadic class
- Bachmair, Ganzinger et al. - 1993
33: A decision procedure for a class of set constraints
- Heintze, Jaffar - 1990
32: The complexity of set constraints
- Aiken, Kozen et al. - 1993
BibTeX entry: (Update)
W. Charatonik and L. Pacholski. Negative set constraints with equality. In Ninth Annual IEEE Symposium on Logic in Computer Science, pages 128--136, 1994. http://citeseer.ist.psu.edu/charatonik94negative.html More
@inproceedings{ charatonik94negative,
author = "Witold Charatonik and Leszek Pacholski",
title = "Negative Set Constraints with Equality",
booktitle = "Logic in Computer Science",
pages = "128-136",
year = "1994",
url = "citeseer.ist.psu.edu/charatonik94negative.html" }
Citations (may not include all citations):
195
Flow analysis and optimization of lisp-like structures (context) - Jones, Muchnick - 1979
109
Solving systems of set constraints (context) - Aiken, Wimmers - 1992
92
A finite presentation theorem for approximating logic progra..
- Heintze, Jaffar - 1990
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
56
Solvable Cases of the Decision Problem (context) - Ackermann - 1954
53
Static type inference in a dynamically typed language
- Aiken, Murphy - 1991
52
Decidability of systems of set constraints with negative con..
- Aiken, Kozen et al. - 1993
50
Solving systems of set constraints with negated subset relat.. (context) - Gilleron, Tison et al. - 1993
46
Implementing regular tree expressions
- Aiken, Murphy - 1991
34
Solving systems of set constraints using tree automata (context) - Gilleron, Tison et al. - 1993
33
Complexity results for classes of quantificational formulas (context) - Lewis - 1980
26
Systems of set constraints with negative constraints are NEX.. (context) - Stefansson - 1993
23
Experience with a type evaluator (context) - Young, O'Keefe - 1988
12
Computer Science Department (context) - Aiken, Kozen et al. - 1993
12
Solvable Classes of Quantificational Formulas (context) - Dreben, Goldfarb et al. - 1979
6
Laboratoire d'Informatique Fondamentale de Lille (context) - Bogaert, Tison et al. - 1991
1
An application of games to the completeness problems for fro.. (context) - Ehrenfeucht - 1961
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.mpi-sb.mpg.de/~witold/): More
Solving Set Constraints for Greatest Models - Charatonik, Podelski (1997)
(Correct)
Set-based Error Diagnosis of Concurrent Constraint Programs - Podelski, Charatonik, Müller (1997)
(Correct)
The Independence Property of a Class of Set Constraints - Charatonik, Podelski (1996)
(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