ﻻ يوجد ملخص باللغة العربية
We consider a search problem on a $2$-dimensional infinite grid with a single mobile agent. The goal of the agent is to find her way home, which is located in a grid cell chosen by an adversary. Initially, the agent is provided with an infinite sequence of instructions, that dictate the movements performed by the agent. Each instruction corresponds to a movement to an adjacent grid cell and the set of instructions can be a function of the initial locations of the agent and home. The challenge of our problem stems from faults in the movements made by the agent. In every step, with some constant probability $0 leq p leq 1$, the agent performs a random movement instead of following the current instruction. This paper provides two results on this problem. First, we show that for some values of $p$, there does not exist any set of instructions that guide the agent home in finite expected time. Second, we complement this impossibility result with an algorithm that, for sufficiently small values of $p$, yields a finite expected hitting time for home. In particular, we show that for any $p < 1$, our approach gives a hitting rate that decays polynomially as a function of time. In that sense, our approach is far superior to a standard random walk in terms of hitting time. The main contribution and take-home message of this paper is to show that, for some value of $0.01139dots < p < 0.6554ldots$, there exists a phase transition on the solvability of the problem.
This contribution is devoted to the study of positional numeration systems with negative base introduced by Ito and Sadahiro in 2009, called (-beta)-expansions. We give an admissibility criterion for more general case of (-beta)-expansions and discus
We propose a new ternary infinite (even full-infinite) square-free sequence. The sequence is defined both by an iterative method and by a direct definition. Both definitions are analogous to those of the Thue-Morse sequence. The direct definition is
Wings of flying animals can not only generate lift and control torques but also can sense their surroundings. Such dual functions of sensing and actuation coupled in one element are particularly useful for small sized bio-inspired robotic flyers, who
We study navigation with limited information in networks and demonstrate that many real-world networks have a structure which can be described as favoring communication at short distance at the cost of constraining communication at long distance. Thi
We consider the problem of computing a binary linear transformation using unreliable components when all circuit components are unreliable. Two noise models of unreliable components are considered: probabilistic errors and permanent errors. We introd