# Dynamic Ring Exploration with \((H,s)\) View +
## 2 Models and Terminologies  
We consider _a time variant ring_\(\mathcal{R}=(V,E,\rho)\) where \(G=(V,E)\) is a ring network, i.e., \(V=\{v_{0},v_{1},\ldots,v_{n-1}\}\) is a set of \(n\) nodes and \(E=\{e_{0},e_{1},\ldots,e_{n-1}\}\) is a set of \(n\) links such that \(e_{i}=(v_{i},v_{i+1\bmod n})\). The nodes of the network are anonymous. For simplicity, we omit mod \(n\) in the following. A function \(\rho:E\times\mathbb{N}\to\{0,1\}\) is called a _link presence function_ such that \(\rho(e,t)\) is \(1\) (resp., \(0\)) if link \(e\) is present (resp., missing) at time step (or _step_) \(t\in\mathbb{N}\). A network at each step \(t\) is denoted as \(R_{t}=(V,E_{t})\) where \(E_{t}=\{e_{i}\in E\mid\rho(e_{i},t)=1\}\). We assume that \(\mathcal{R}\) is \(1\)_-interval connected_, i.e., at each step \(t\), a network \(R_{t}\) is connected. In other words, at each step \(t\), there is at most one missing link \(e_{i}\in E\) such that \(e_{i}\
otin E_{t}\). We say the ascending (resp., descending) order of node indices is the right (resp., left) direction. Each port of \(e_{i}\) has a globally consistent label at \(v_{i}\) and \(v_{i+1}\) which gives an entity on the ring a global direction (the right direction at \(v_{i}\) and the left direction at \(v_{i+1}\)) of the ring. Given a connected component \(V^{\prime}\subseteq V\), the _right_ (resp., _left_) _extremity_ of \(V^{\prime}\) is the node \(v_{i}\in V^{\prime}\) such that \(v_{i+1}\
otin V^{\prime}\) (resp., \(v_{i-1}\
otin V^{\prime}\)). If \(|V^{\prime}|=1\), the unique node in \(V^{\prime}\) is both the right extremity and the left extremity of \(V^{\prime}\). In the network, a single agent \(A\) is operational. Agent \(A\) knows the network size \(n\), has computation capacity and its own memory, and can traverse at most one link in each step. In addition to them, \(A\) can get the _view_ which contains information of presence of nearby links in near future as defined later. In a step \(t\), \(A\) at a node, say \(v_{i}\), first decides which direction it moves and updates its memory depending on the current content of its memory and the view from \(v_{i}\). If the corresponding link is present at \(t\), \(A\) succeeds to move and reaches a neighbor of \(v_{i}\) by the end of \(t\). Otherwise, \(A\) fails to move and stays at \(v_{i}\). Informally speaking, the \((H,S)\)_view_ that agent \(A\) can get shows which link is missing within \(H\) hops from the current node and within \(S\) steps in the future including the current step. Formally speaking, for \(\lceil n/2\rceil\geq H\geq 1\) and \(S\geq 1\), \(A\) gets the \((H,S)\) view \(\beta_{H,S}(i,s)=\{(e_{j},t,\rho(e_{j},t))\mid i-H\leq j\leq i+H-1,s\leq t\leq s +S-1\}\) when \(A\) exists on \(v_{i}\) at step \(s\). For example, when \(H=2\), \(S=2\), and \(A\) exists on \(v_{0}\) at step \(5\), \(A\) can see \(\beta_{2,2}(0,5)=\{(e_{1},5,0),\ (e_{0},5,1),\ (e_{n-1},5,1),\ (e_{n-2},5,1),\ (e_{1},6,1),\)\((e_{0},6,0),\ (e_{n-1},6,1),\ (e_{n-2},6,1)\}\). When no confusion arises, we simply write _the view_ instead of writing the \"\((H,S)\) view\". It is assumed that a link scheduling (or \(\rho(e_{i},t)\) for every \(e_{i}\) and every step \(t>0\)) is decided by the adversary. The adversary knows the algorithm of \(A\), has infinite computation capacity, and tries to prevent \(A\) from exploring the ring. In this paper, we consider the exploration problem by a single agent \(A\): \(A\) is required to visit all the nodes in the ring. A node is said to be _explored_ by (resp., at) the \(t\)-th step when it is visited by \(A\) at the end of the \((t-1)\)-th step or earlier (resp., at the end of the \((t-1)\)-th step for the first time). In the similar manner, we say that \(A\) reaches a node at the \(t\)-th step when \(A\) visits the node at the end of the \((t-1)\)-th step and that \(A\)_explores_ a node \(v\) at the \(t\)-th step if \(v\) is unexplored at the start of the \((t-1)\)-th step and \(A\) reaches \(v\) at the \(t\)-th step.