MPI-INF Logo
Publications

Server    halma.mpi-inf.mpg.de

Proceedings Article, Paper


@InProceedings
Beitrag in Tagungsband, Workshop
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
Conference URL::
http://fossacs.dimi.uniud.it/
Downloading URL:
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
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