文章基本信息

标题：On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks
本地全文：下载
作者：Giorgio Delzanno ; Arnaud Sangnier ; Riccardo Traverso 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：18
页码：289-300
DOI：10.4230/LIPIcs.FSTTCS.2012.289
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Broadcast Communication; Parameterized Verification; Complexity