2026-07-23T13:09:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3867 2024-03-06T10:34:33Z ddc:004 open_access

On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks Delzanno, Giorgio Sangnier, Arnaud Traverso, Riccardo Zavattaro, Gianluigi Broadcast Communication Parameterized Verification Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giorgio Delzanno and Arnaud Sangnier and Riccardo Traverso and Gianluigi Zavattaro 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.289 urn:nbn:de:0030-drops-38671 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.289 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode