Seminár z teoretickej informatiky - Stefan Dobrev (22.3.2019)

v piatok 22.3.2019 o 11:00 hod. v miestnosti M/213

---

Prednášajúci:  Stefan Dobrev (Matematický ústav SAV)

Názov:  Exploration of High-Dimensional Grids by Finite State Machines

Termín:  22.3.2019, 11:00 hod., M/213

Abstrakt:
We consider the problem of finding a treasure at an unknown point of an n-dimensional infinite grid, n ≥ 3, by initially collocated finite state agents (scouts/robots). Recently, the problem has been well characterized for 2 dimensions for deterministic as well as randomized agents, both in synchronous and semi-synchronous models. It has been conjectured that n + 1 randomized agents are necessary to solve this problem in the n-dimensional grid. We disprove the conjecture in a strong sense: we show that three randomized synchronous agents suffice to explore an n-dimensional grid for any n. Our algorithm is optimal in terms of the number of the agents.

web: https://beda.dcs.fmph.uniba.sk/seminar

---