MPI-INF Logo
Publications

Server    halma.mpi-inf.mpg.de

Proceedings Article, Paper


@InProceedings
Beitrag in Tagungsband, Workshop
Author, Editor
Author(s):
Charatonik, Witold
Podelski, Andreas
Talbot, Jean-Marc		dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
CharatonikPodelskiTalbot-POPL00
Title, Booktitle
Title*:
Paths vs. Trees in Set-based Program Analysis
Booktitle*:
Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL-00)
Event, URLs
Conference URL::
http://www.research.ibm.com/people/w/wegman/POPL.html
Downloading URL:
Event Address*:
Boston, Massachusetts, USA
Language:
English
Event Date*
(no longer used):
19-21 January 2000
Organization:
Event Start Date:
16 May 2024
Event End Date:
16 May 2024
Publisher
Name*:
ACM
URL:
http://www.acm.org/pubs/
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
330-337
Year*:
2000
VG Wort Pages:
8
ISBN/ISSN:
1-58113-125-9
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 Set-based analysis of logic programs provides an accurate method for
descriptive type-checking of logic programs. The key idea of this
method is to upper approximate the least model of the program by a
regular set of trees. In 1991, Fr\"uhwirth, Shapiro, Vardi and
Yardeni raised the question whether it can be more efficient to use
the domain of sets of paths instead, {\em i.e.}, to approximate the
least model by a regular set of words. We answer the question
negatively by showing that type-checking for path-based analysis is
as hard as the set-based one, that is DEXPTIME-complete. This
result has consequences also in the areas of set constraints,
automata theory and model checking.
Keywords:
Set-based Analysis, Logic Programming, Set Constraints
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:
@INPROCEEDINGS{CharatonikPodelskiTalbot-POPL00,
AUTHOR = {Charatonik, Witold and Podelski, Andreas and Talbot, Jean-Marc},
 TITLE = {Paths vs. Trees in Set-based Program Analysis},
 BOOKTITLE = {Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL-00)},
 PUBLISHER = {ACM},
 YEAR = {2000},
 PAGES = {330--337},
 ADDRESS = {Boston, Massachusetts, USA},
 MONTH = {January},
 ISBN = {1-58113-125-9},
}

Entry last modified by Christine Kiesel, 03/12/2010
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)
Witold Charatonik		Created
01/04/2000 03:37:19 PM
Revisions
11.
10.
9.
8.
7.		Editor(s)
Christine Kiesel
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel		Edit Dates
28.08.2001 15:09:45
05/01/2001 02:54:57 PM
04/04/2001 04:19:55 PM
16.03.2001 12:19:22 PM
16.03.2001 12:19:05 PM