Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.research.ibm.com/people/w/wegman/POPL.html

URL for downloading the paper:


Event Address*:

Boston, Massachusetts, USA

Language:

English

Event Date*
(no longer used):

19-21 January 2000

Organization:


Event Start Date:

20 September 2019

Event End Date:

20 September 2019

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
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)
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