Семинар лаборатории теоретической информатики: "Eroders". Докладчик: Питер Гач
19 июня на семинаре лаборатории теоретической информатики состоится доклад Питера Гача "Eroders"
This talk is about cellular automata on a finite-dimensional lattice---a certain kind that has special interest for error correction. A state 0 is distinguished, and a cellular automaton is called an ''eroder'' if it eliminates any finite island of non-0s. We restrict attention to cellular automata whose state set is ordered with 0 being minimal, and whose transition rule is monotonic. (For example majority vote over some neighbors.) A classical result of Toom characterizes all 2-state eroders (in any dimension). It also shows that such eroders erode in linear time, and resist (low random) noise. (The latter was key to building the simplest known construction of a reliable computation model.)
Here I will report on work (some of it old by Galperin and Toom, some of it new, joint with Ilkka Törmä and Mathieu Hilaire) trying to extend these results to more than 2 states. In one dimension, all eroders erode in linear time, but not all resist noise. In 2 dimensions and 3 states, some eroders need more than linear time, and we don't even know whether the eroder property is decidable.
Characterizing eroders that resist noise (in any dimension) seems easier than to characterize just eroders (they all erode in linear time).
Семинар пройдет с 18:10 до 19:30 в аудитории 503 ФКН.
Заказ пропуска: email@example.com