2012/02/27 by Giorgio Delzanno, Arnaud Sangnier, Delzanno, Giorgio +5
Computer Science · #Cooperative Communication and Network Coding #Distributed systems and fault tolerance #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1202.5850
openalex publication_date 2012/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the impact of spontaneous movement in the complexity of verification problems for an automata-based protocol model of networks with selective broadcast communication. We first consider reachability of an error state and show that parameterized verification is decidable with polynomial complexity. We then move to richer queries and show how the complexity changes when considering properties with negation or cardinality constraints.