2010/09/27 by Thomas Fernique, Fernique, Thomas, Nicolas Ollinger +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #05B45 #37B50 #52C23 #Cellular Automata and Applications #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #H.1.1 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1009.5167
openalex publication_date 2010/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A combinatorial substitution is a map over tilings which allows to define sets of tilings with a strong hierarchical structure. In this paper, we show that such sets of tilings are sofic, that is, can be enforced by finitely many local constraints. This extends some similar previous results (Mozes'90, Goodman-Strauss'98) in a much shorter presentation.