English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We propose a new theoretical model for passively mobile Wireless SensorNetworks, called PM, standing for Passively mobile Machines. The mainmodification w.r.t. the Population Protocol model is that agents now, insteadof being automata, are Turing Machines. We provide general definitions forunbounded memories, but we are mainly interested in computations upper-boundedby plausible space limitations. However, we prove that our results hold formore general cases. We focus on complete communication graphs and define thecomplexity classes PMSPACE(f(n)) parametrically, consisting of all predicatesthat are stably computable by some PM protocol that uses O(f(n)) memory on eachagent. We provide a protocol that generates unique ids from scratch only byusing O(log n) memory, and use it to provide an exact characterization for theclasses PMSPACE(f(n)) when f(n)={\Omega}(log n): they are precisely the classesof all symmetric predicates in NSPACE(nf(n)). In this way, we provide a spacehierarchy for the PM model when the memory bounds are {\Omega}(log n). Finally,we explore the computability of the PM model when the protocols use o(loglog n)space per machine and prove that SEMILINEAR=PMSPACE(f(n)) when f(n)=o(loglogn), where SEMILINEAR denotes the class of the semilinear predicates. In fact,we prove that this bound acts as a threshold, so that SEMILINEAR is a propersubset of PMSPACE(f(n)) when f(n)=O(loglog n).

Passively Mobile Communicating Machines that Use Restricted Space