RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






Симпозиум по логике и вычислимости «Logic and Computation Day»
7 июня 2013 г. 15:30, г. Москва, МИАН
 


Fixed-point tile sets and their applications

A. Romashchenko

A. A. Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow

Количество просмотров:
Эта страница:29

Аннотация: An aperiodic tile set was first constructed by R. Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (Entscheidungsproblem) to physics (quasicrystals). We present a construction of an aperiodic tile set that is based on Kleene's fixed-point construction instead of traditional geometric arguments. This construction it very flexible, and it can be used in embed many supplementary features in a tiling: it is suitable to give a new proof for the undecidability of the domino problem, to enforce high Kolmogorov complexity of a tiling, to characterize effectively closed 1D subshift it terms of 2D shifts of finite type, to construct a robust aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow sparse tiling errors, etc. Joint work with Bruno Durand and Alexander Shen.

Язык доклада: английский

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017