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
Talbot, Jean-Marc

dblp
dblp

Not MPG Author(s):

Talbot, Jean-Marc

Editor(s):

Tison, Sophie

dblp

Not MPII Editor(s):

Tison, Sophie

BibTeX cite key*:

CharatonikTalbot2002

Title, Booktitle

Title*:

Atomic Set Constraints with Projection

Booktitle*:

Rewriting Techniques and Applications. 13th International Conference, RTA 2002

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

Copenhagen, Denmark

Language:

English

Event Date*
(no longer used):

-- July 22-24, 2002

Organization:


Event Start Date:

22 July 2002

Event End Date:

24 July 2002

Publisher

Name*:

Springer

URL:


Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

2378

Number:


Month:


Pages:

311-325

Year*:

2002

VG Wort Pages:


ISBN/ISSN:

3-540-43916

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We investigate a class of set constraints defined as atomic set
constraints augmented with projection. This class subsumes some
already studied classes such as atomic set constraints with
left-hand side projection and INES constraints. All these classes
enjoy a nice property that satisfiability can be performed in cubic time. This has be contrasted with several other classes of set constraints, such as definite set constraints and positive set constraints, for which satisfiability ranges from DEXPTIME-complete to NEXPTIME-complete. However, these latter classes allow set operators such as intersection or union which is not the case for the class studied here. In the case of atomic set constraints with projection one might expect that satisfiability remains polynomial. Unfortunately, we show that that the satisfiability problem for this class is no longer polynomial, but CoNP-hard. Furthermore, we devise a PSPACE algorithm to solve this satisfiability problem.



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Programming Logics Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{CharatonikTalbot2002,
AUTHOR = {Charatonik, Witold and Talbot, Jean-Marc},
EDITOR = {Tison, Sophie},
TITLE = {Atomic Set Constraints with Projection},
BOOKTITLE = {Rewriting Techniques and Applications. 13th International Conference, RTA 2002},
PUBLISHER = {Springer},
YEAR = {2002},
VOLUME = {2378},
PAGES = {311--325},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Copenhagen, Denmark},
ISBN = {3-540-43916},
}


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
09/27/2002 08:55:29 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
01.09.2003 17:20:44
01.09.2003 14:45:12
04.08.2003 16:09:38
07.07.2003 15:38:33
07.07.2003 14:37:49
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section