Monotonicity conjecture for the computational capabilities of oblivious robot systems

Let GG be a network and let k1k\geq 1. Write F(G,k)\mathcal F(G,k) for the system of kk oblivious mobile robots on GG, and write \preceq for the computational-capability preorder. Monotonicity conjecture. For all networks GG and all k1k\geq 1, F(G,k)F(G,k+1)\mathcal F(G,k)\preceq \mathcal F(G,k+1).

This conjecture asserts that adding robots never decreases the set of computable functions, strengthening the preceding simulation results. The supplied text does not state whether it has been resolved.

Sources & referencesView supporting material

Primary source

Paola Flocchini, Nicola Santoro, Giovanni Viglietta and Masafumi Yamashita, “Universal Systems of Oblivious Mobile Robots”, arXiv:1602.04881 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.