Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Model checking mobile ambients

Charatonik, W., Dal Zilio, S., Gordon, A. D., Mukhopadhyay, S., & Talbot, J.-M. (2003). Model checking mobile ambients. Theoretical Computer Science, 308, 277-331.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Charatonik, Witold1, Autor           
Dal Zilio, Silvano, Autor
Gordon, Andrew Donald, Autor
Mukhopadhyay, Supratik1, Autor           
Talbot, Jean-Marc1, Autor           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We settle the complexity bounds of the model checking problem for the ambient calculus with public names against the ambient logic. We show that if either the calculus contains replication or the logic contains the guarantee operator, the problem is undecidable. In the case of the replication-free calculus and guarantee-free logic we prove 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2004-06-172003
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 202031
Anderer: Local-ID: C1256104005ECAFC-30C5005D9C1C805CC1256D200054C703-CharatonikDGMT2003
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Theoretical Computer Science
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 308 Artikelnummer: - Start- / Endseite: 277 - 331 Identifikator: ISSN: 0304-3975