Computing (or not) Quasi-Periodicity Functions of Tilings

Details Computing (or not) Quasi-Periodicity Functions of Tilings Computing (or not) Quasi-Periodicity Functions of Tilings

2010-12-03

arxiv.org/abs/1012.1222v1

Nonlinear Sciences

Cellular Automata and Lattice Gases

Journ\'ees Automates Cellulaires 2010, Turku : Finland (2010)

Scientific paper

We know that tilesets that can tile the plane always admit a quasi-periodic tiling [4, 8], yet they hold many uncomputable properties [3, 11, 21, 25]. The quasi-periodicity function is one way to measure the regularity of a quasi-periodic tiling. We prove that the tilings by a tileset that admits only quasi-periodic tilings have a recursively (and uniformly) bounded quasi-periodicity function. This corrects an error from [6, theorem 9] which stated the contrary. Instead we construct a tileset for which any quasi-periodic tiling has a quasi-periodicity function that cannot be recursively bounded. We provide such a construction for 1-dimensional effective subshifts and obtain as a corollary the result for tilings of the plane via recent links between these objects [1, 10].

Affiliated with

Also associated with

No associations

Rating

Computing (or not) Quasi-Periodicity Functions of Tilings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing (or not) Quasi-Periodicity Functions of Tilings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing (or not) Quasi-Periodicity Functions of Tilings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-515728