Effective Closed Subshifts in 1D Can Be Implemented in 2D

Bruno Durand; Andrei Romashchenko; Alexander Shen

Retour

Effective Closed Subshifts in 1D Can Be Implemented in 2D

Acte de colloque

Avec comité de lecture

Effective Closed Subshifts in 1D Can Be Implemented in 2D

Bruno Durand, Andrei Romashchenko et Alexander Shen

FIELDS OF LOGIC AND COMPUTATION: ESSAYS DEDICATED TO YURI GUREVICH ON THE OCCASION OF HIS 70TH BIRTHDAY, Vol.6300, p.208

Lecture Notes in Computer Science

01/01/2010

Résumé

Computer Science

Computer Science, Software Engineering

Computer Science, Theory & Methods

Mathematics

Mathematics, Applied

Physical Sciences

Science & Technology

Technology

In this paper we use fixed point tilings to answer a question posed by Michael Hochman and show that every one-dimensional effectively closed subshift can be implemented by a local rule in two dimensions. The proof uses the fixed-point construction of an aperiodic tile set and its extensions.

Indicateurs

1 Consultations de la notice

Détails

Titre: Effective Closed Subshifts in 1D Can Be Implemented in 2D
Créateurs - sans rôle: Bruno Durand - Univ Aix Marseille, LIF Marseille, F-13331 Marseille 3, France
Andrei Romashchenko - Univ Aix Marseille, LIF Marseille, F-13331 Marseille 3, France
Alexander Shen - Univ Aix Marseille, LIF Marseille, F-13331 Marseille 3, France
Contributeurs - sans rôle: A Blass
N Dershowitz
W Reisig
Détails de publication: FIELDS OF LOGIC AND COMPUTATION: ESSAYS DEDICATED TO YURI GUREVICH ON THE OCCASION OF HIS 70TH BIRTHDAY, Vol.6300, p.208
Publications en série: Lecture Notes in Computer Science
Éditeur: Springer Nature
Nombre de pages: 3
Note de subvention: ANR-09-EMER-008-01 / NAFIT 09-01-00709a / RFBR; Russian Foundation for Basic Research (RFBR)
Identifiants: 99139365209311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Langue: English
Type de ressource: Conference proceeding