2010/06/15 by Matthew J. Patitz, Patitz, Matthew J., Scott M. Summers +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced biosensing and bioanalysis techniques #Biosensors and Analytical Detection #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1006.3046
arxiv created 2010/06/15 · openalex publication_date 2010/06/15 · arxiv updated 2010/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we introduce the following problem in the theory of algorithmic self-assembly: given an input shape as the seed of a tile-based self-assembly system, design a finite tile set that can, in some sense, uniquely identify whether or not the given input shape--drawn from a very general class of shapes--matches a particular target shape. We first study the complexity of correctly identifying squares. Then we investigate the complexity associated with the identification of a considerably more general class of non-square, hole-free shapes.