A Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2012

A Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings

Abstract

In this paper we investigate certain properties of semi-totalistic cellular automata (CA) on the well known quasi-periodic kite and dart two dimensional tiling of the plane presented by Roger Penrose. We show that, despite the irregularity of the underlying grid, it is possible to devise a semi-totalistic CA capable of simulating any boolean circuit on this aperiodic tiling.

Domains

Computational Complexity [cs.CC]
Fichier principal
Vignette du fichier
automata2012201207311919.pdf (1.19 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Victor Poupet  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00839161

Submitted on : Thursday, June 27, 2013-12:06:45 PM

Last modification on : Friday, March 24, 2023-2:52:57 PM

Long-term archiving on : Wednesday, April 5, 2017-4:18:02 AM

Download

Dates and versions

lirmm-00839161 , version 1 (27-06-2013)

Licence

CC0 - Public Domain Dedication

Identifiers

  • HAL Id : lirmm-00839161 , version 1

Cite

Katsunobu Imai, Takahiro Hatsuda, Victor Poupet, Sato Kota. A Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings. Automata & JAC, 2012, La Marana, Corsica, France. pp.267-278. ⟨lirmm-00839161⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ESCAPE LIRMM MIPS UNIV-MONTPELLIER
233 View
341 Download

Share

More