Complex tilings

DOI10.1145/380752.380880zbMath1323.68326OpenAlexW2295394628MaRDI QIDQ5176032

Leonid A. Levin, Alexander Shen, Bruno Durand

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380880

zbMATH Keywords

tilingsrecursion theoryKolmogrov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Related Items

Simulation of effective subshifts by two-dimensional subshifts of finite type ⋮ A Topological Study of Tilings ⋮ Two notes on subshifts ⋮ Constructing New Aperiodic Self-simulating Tile Sets ⋮ Tilings: simulation and universality ⋮ Construction of sequences of zeros and ones with complex finite sequences ⋮ From logic to tiling

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)