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.2012.289
URN: urn:nbn:de:0030-drops-38671
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3867/
Go to the corresponding LIPIcs Volume Portal

Delzanno, Giorgio ; Sangnier, Arnaud ; Traverso, Riccardo ; Zavattaro, Gianluigi

On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks

pdf-format:
28.pdf (0.2 MB)

Abstract

We investigate the impact of dynamic topology reconfiguration on the complexity of verification problems for models of protocols with broadcast communication. We first consider reachability of a configuration with a given set of control states and show that parameterized verification is decidable with polynomial time complexity. We then move to richer queries and show how the complexity changes when considering properties with negation or cardinality constraints.

BibTeX - Entry

@InProceedings{delzanno_et_al:LIPIcs:2012:3867,
  author =	{Giorgio Delzanno and Arnaud Sangnier and Riccardo  Traverso and Gianluigi Zavattaro},
  title =	{{On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{289--300},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3867},
  URN =		{urn:nbn:de:0030-drops-38671},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.289},
  annote =	{Keywords: Broadcast Communication, Parameterized Verification, Complexity}
}

Keywords: Broadcast Communication, Parameterized Verification, Complexity
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

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