Monotonicity conjecture for the computational capabilities of oblivious robot systems

About 10 years old · traced to

Let GG be a network and let k≥1k\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 k≥1k\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.

References

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.