Circle formation of weak robots and Lyndon words
From MaRDI portal
Publication:845920
DOI10.1016/J.IPL.2006.09.008zbMATH Open1185.68730arXivcs/0605096OpenAlexW2951728928MaRDI QIDQ845920FDOQ845920
Authors: Yoann Dieudonné, Franck Petit 
Publication date: 29 January 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: A Lyndon word is a non-empty word strictly smaller in the lexicographic order than any of its suffixes, except itself and the empty word. In this paper, we show how Lyndon words can be used in the distributed control of a set of n weak mobile robots. By weak, we mean that the robots are anonymous, memoryless, without any common sense of direction, and unable to communicate in an other way than observation. An efficient and simple deterministic protocol to form a regular n-gon is presented and proven for n prime.
Full work available at URL: https://arxiv.org/abs/cs/0605096
Cites Work
- Self-stabilization
- Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
- Title not available (Why is that?)
- Title not available (Why is that?)
- Periodic musical sequences and Lyndon words
- Title not available (Why is that?)
- Structural Information and Communication Complexity
- A public key cryptosystem based on Lyndon words
Cited In (5)
- Deterministic geoleader election in disoriented anonymous systems
- Computing by mobile robotic sensors
- Optimal exclusive perpetual grid exploration by luminous myopic opaque robots with common chirality
- Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
- The ``runs theorem
Uses Software
This page was built for publication: Circle formation of weak robots and Lyndon words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845920)
