On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks

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



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2012.289.pdf
  • Filesize: 228 kB
  • 12 pages

Document Identifiers

Author Details

Giorgio Delzanno
Arnaud Sangnier
Riccardo Traverso
Gianluigi Zavattaro

Cite AsGet BibTex

Giorgio Delzanno, Arnaud Sangnier, Riccardo Traverso, and Gianluigi Zavattaro. On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 289-300, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.FSTTCS.2012.289

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.
Keywords
  • Broadcast Communication
  • Parameterized Verification
  • Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail