License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2309
URN: urn:nbn:de:0030-drops-23092
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2309/
Go to the corresponding LIPIcs Volume Portal

Bozzelli, Laura ; Legay, Axel ; Pinchinat, Sophie

On Timed Alternating Simulation for Concurrent Timed Games

pdf-format:
09005.BozzelliLaura.2309.pdf (0.2 MB)

Abstract

We address the problem of alternating simulation refinement for concurrent timed games (\TG). We show that checking timed alternating simulation between\TG is \EXPTIME-complete, and provide a logical characterization of thispreorder in terms of a meaningful fragment of a new logic, \TAMTLSTAR.\TAMTLSTAR is an action-based timed extension of standard alternating-timetemporal logic \ATLSTAR, which allows to quantify on strategies where thedesignated player is not responsible for blocking time. While for full
\TAMTLSTAR, model-checking \TG is undecidable, we show that for its fragment
\TAMTL, corresponding to the timed version of \ATL, in \EXPTIME.

BibTeX - Entry

@InProceedings{bozzelli_et_al:LIPIcs:2009:2309,
  author =	{Laura Bozzelli and Axel Legay and Sophie Pinchinat},
  title =	{{On Timed Alternating Simulation for Concurrent Timed Games}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{85--96},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Ravi Kannan and K. Narayan Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2309},
  URN =		{urn:nbn:de:0030-drops-23092},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2309},
  annote =	{Keywords: Concurrent Timed Games, Timed Alternating Simulation, Timed Alternating Temporal Logics}
}

Keywords: Concurrent Timed Games, Timed Alternating Simulation, Timed Alternating Temporal Logics
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2009
Date of publication: 14.12.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI