Negative Set Constraints With Equality (1994)  (Make Corrections)  (42 citations)
Witold Charatonik, Leszek Pacholski
Logic in Computer Science

  Home/Search   Context   Related

 
View or download:
mpisb.mpg.de/~witold/pap...lics94.ps.Z
Cached:  PS.gz  PS  PDF  Image  Update  Help

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

Rate this article: (best)
  Comment on this article  
(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