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
Dal Zilio, Silvano
Gordon, Andrew Donald
Mukhopadhyay, Supratik
Talbot, Jean-Marc

dblp
dblp
dblp
dblp
dblp

Not MPG Author(s):

Dal Zilio, Silvano
Gordon, Andrew Donald

Editor(s):

Honsell, Furio
Miculan, Marino

dblp
dblp

Not MPII Editor(s):

Honsell, Furio
Miculan, Marino

BibTeX cite key*:

CDGMT01

Title, Booktitle

Title*:

The Complexity of Model Checking Mobile Ambients

Booktitle*:

Foundations of Software Science and Computation Structures. Proceedings of the 4th International Conference (FOSSACS-01). Held as Part of the Joint European Conferences on Theory and Practice of Software (ETAPS-01)

Event, URLs

URL of the conference:

http://fossacs.dimi.uniud.it/

URL for downloading the paper:


Event Address*:

Genova, Italy

Language:

English

Event Date*
(no longer used):

April,2 -- April,8

Organization:


Event Start Date:

14 May 2003

Event End Date:

18 May 2003

Publisher

Name*:

Springer

URL:

http://www.springer.de/

Address*:

Berlin, Germany

Type:

Extended Abstract

Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

2030

Number:


Month:

April

Pages:

152-167

Year*:

2001

VG Wort Pages:

16

ISBN/ISSN:

3-540-41864-4

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We settle the complexity bounds of the model checking problem for
the replication-free ambient calculus with public names against the
ambient logic without parallel adjunct. We show that the problem is
PSPACE-complete. For the complexity upper-bound, we devise a new
representation of processes that remains of polynomial size during
process execution; this allows us to keep the model checking
procedure in polynomial space. Moreover, we prove PSPACE-hardness
of the problem for several quite simple fragments of the calculus
and the logic; this suggests that there are no interesting fragments
with polynomial-time model checking algorithms.



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, CCL bibliography, VG Wort



BibTeX Entry:

@INPROCEEDINGS{CDGMT01,
AUTHOR = {Charatonik, Witold and Dal Zilio, Silvano and Gordon, Andrew Donald and Mukhopadhyay, Supratik and Talbot, Jean-Marc},
EDITOR = {Honsell, Furio and Miculan, Marino},
TITLE = {The Complexity of Model Checking Mobile Ambients},
BOOKTITLE = {Foundations of Software Science and Computation Structures. Proceedings of the 4th International Conference (FOSSACS-01). Held as Part of the Joint European Conferences on Theory and Practice of Software (ETAPS-01)},
PUBLISHER = {Springer},
YEAR = {2001},
TYPE = {Extended Abstract},
VOLUME = {2030},
PAGES = {152--167},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Genova, Italy},
MONTH = {April},
ISBN = {3-540-41864-4},
}


Entry last modified by Anja Becker, 06/07/2011
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)
Supratik Mukhopadhyay
Created
03/15/2001 04:32:22 PM
Revisions
13.
12.
11.
10.
9.
Editor(s)
Anja Becker
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Edit Dates
07.06.2011 13:51:17
2007-03-26 18:44:52
2007-03-26 18:44:14
14.05.2003 16:58:53
31.03.2002 18:35:20
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section