Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | 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