Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2024) | last year (2023) | two years ago (2022) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Charatonik, Witold
Podelski, Andreas		dblp
dblp

BibTeX cite key*:

CPintersectionJ

Title

Title*:

Set Constraints with Intersection

Journal

Journal Title*:

Information and Computation
Journal's URL:

http://www.elsevier.com/inca/publications/store/6/2/2/8/4/4/

Download URL
for the article:

http://dx.doi.org/doi:10.1006/inco.2001.2952
Language:

English

Publisher

Publisher's
Name:

Academic Press
Publisher's URL:

http://www.elsevier.com

Publisher's
Address:

New York, USA
ISSN:

0890-5401

Vol, No, pp, Date

Volume*:

179
Number:

2

Publishing Date:

December 2002

Pages*:

213-229
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

Set constraints are inclusions between expressions denoting sets of
trees (over a given alphabet of constructor symbols). The
efficiency of their satisfiability test is a central issue in
set-based program analysis, their main application domain. We
introduce the class of {\em set constraints with intersection}\/
(the only operators forming the expressions are constructors and
intersection) and show that its satisfiability problem is
DEXPTIME-complete. This is the first class of set constraints (over
a general constructor alphabet) that falls into this complexity
class. The solved form in our algorithm represents the least
solution as a tree automaton and exhibits which variables denote the
empty set. We furthermore prove that set constraints with
intersection are equivalent to {\em definite set constraints}\/ (in
expressive power, and the satisfiability problems are linearly
inter-reducible). The class of definite set constraints was the
first one for which the decidability question was solved; we hereby
settle also the complexity question.

URL for the Abstract:


Categories,
Keywords:

set constraints, program analysis

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Programming Logics Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, CCL bibliography


BibTeX Entry:
@ARTICLE{CPintersectionJ,
AUTHOR = {Charatonik, Witold and Podelski, Andreas},
 TITLE = {Set Constraints with Intersection},
 JOURNAL = {Information and Computation},
 PUBLISHER = {Academic Press},
 YEAR = {2002},
 NUMBER = {2},
 VOLUME = {179},
 PAGES = {213--229},
 ADDRESS = {New York, USA},
 MONTH = {December},
 ISBN = {0890-5401},
}

Entry last modified by Anja Becker, 03/12/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Andreas Podelski		Created
01/18/1999 04:58:03 PM
Revisions
9.
8.
7.
6.
5.		Editor(s)
Anja Becker
Andreas Podelski
Witold Charatonik
Manfred Jaeger
Manfred Jaeger		Edit Dates
09.05.2003 10:42:43
04/15/2003 04:11:54 PM
11/01/2002 16:01:57
31/08/2001 11:30:24
31/08/2001 11:27:00