2010/02/19 by Lila Kari, Benoît Masson, Kari, Lila +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Advanced Materials and Mechanics #Cellular Automata and Applications #Combinatorics #Computational Complexity (cs.CC) #Computer science #DNA and Biological Computing #Enhanced Data Rates for GSM Evolution #FOS: Computer and information sciences #Geometry #Mathematics #Path (computing) #Plane (geometry) #Polyomino #Position (finance) #Regular polygon #Relation (database) #Sequence (biology) #Set (abstract data type) #Simple (philosophy) #Substitution tiling #Tile #cs.CC
paper · pdf · doi:10.48550/arxiv.1002.3769
published in arXiv (Cornell University) (Cornell University) · Submitted to Theoretical Computer Science
openalex publication_date 2010/02/19 · arxiv created 2011/04/11 · arxiv updated 2011/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
This paper provides a bridge between the classical tiling theory and the complex neighborhood self-assembling situations that exist in practice. The neighborhood of a position in the plane is the set of coordinates which are considered adjacent to it. This includes classical neighborhoods of size four, as well as arbitrarily complex neighborhoods. A generalized tile system consists of a set of tiles, a neighborhood, and a relation which dictates which are the "admissible" neighboring tiles of a given tile. Thus, in correctly formed assemblies, tiles are assigned positions of the plane in accordance to this relation. We prove that any validly tiled path defined in a given but arbitrary neighborhood (a zipper) can be simulated by a simple "ribbon" of microtiles. A ribbon is a special kind of polyomino, consisting of a non-self-crossing sequence of tiles on the plane, in which successive tiles stick along their adjacent edge. Finally, we extend this construction to the case of traditional tilings, proving that we can simulate arbitrary-neighborhood tilings by simple-neighborhood tilings, while preserving some of their essential properties.