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 investigate the computational power of the deterministic single-agentmodel where the agent and each node are equipped with a limited amount ofpersistent memory. Tasks are formalized as decision problems on properties ofinput graphs, i.e., the task is defined as a subset $\mathcal{T}$ of allpossible input graphs, and the agent must decide if the network belongs to$\mathcal{T}$ or not. We focus on the class of the decision problems which aresolvable in a polynomial number of movements, and polynomial-time localcomputation. The contribution of this paper is the computational power of thevery weak system with one-bit agent memory and $O(1)$-bit storage (i.e. nodememory) is equivalent to the one with $O(n)$-bit agent memory and $O(1)$-bitstorage. We also show that the one-bit agent memory is crucial to lead thisequivalence: There exists a decision task which can be solved by the one-bitmemory agent but cannot be solved by the zero-bit memory (i.e., oblivious)agent. Our result is deduced by the algorithm of simulating the $O(n)$-bitmemory agent by the one-bit memory agent with polynomial-time overhead, whichis developed by two novel technical tools. The first one is a dynamic $s$-$t$path maintenance mechanism which uses only $O(1)$-bit storage per node. Thesecond one is a new lexicographically-ordered DFS algorithm for the mobileagent system with $O(1)$-bit memory and $O(1)$-bit storage per node. Thesetools are of independent interest.

Deciding a Graph Property by a Single Mobile Agent: One-Bit Memory Suffices