Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

this year (2024) | last year (2023) | two years ago (2022) | 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
Editor(s):

BibTeX Citekey*:

CDGMT2001-techrep

Language:

English

Title, Institution

Title*:

The Complexity of Model Checking Mobile Ambients

Institution*:

Microsoft Research, Microsoft Corporation

Publishers or Institutions Address*:

Redmond, USA

Type:

Technical Report

No, Year, pp.,

Number*:

MSR-TR-2001-03
Pages*:

50

Month:

May
VG Wort
Pages*:

50

Year*:

2001
ISBN/ISSN:






DOI:




Note, Abstract, ©

Note:


(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.

Categories / Keywords:


Copyright Message:


HyperLinks / References / URLs:


Personal Comments:


File Upload:


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, university publications list, working group publication list, Fachbeirat, CCL bibliography, VG Wort


BibTeX Entry:
@TECHREPORT{CDGMT2001-techrep,
AUTHOR = {Charatonik, Witold and Dal Zilio, Silvano and Gordon, Andrew Donald and Mukhopadhyay, Supratik and Talbot, Jean-Marc},
 TITLE = {The Complexity of Model Checking Mobile Ambients},
 YEAR = {2001},
 TYPE = {Technical Report},
 INSTITUTION = {Microsoft Research, Microsoft Corporation},
 NUMBER = {MSR-TR-2001-03},
 PAGES = {50},
 ADDRESS = {Redmond, USA},
 MONTH = {May},
}

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
08/14/2001 04:22:17 PM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Christine Kiesel
Uwe Brahm
Uwe Brahm
Manfred Jaeger
Manfred Jaeger		Edit Dates
14.05.2003 16:59:05
01/18/2002 03:30:49 PM
01/18/2002 03:30:07 PM
31/08/2001 17:55:52
14/08/2001 16:22:18