Skip to Main content Skip to Navigation
Journal articles

Local Rule Substitutions and Stepped Surfaces

Thomas Fernique 1 
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Substitutions on words, \emph{i.e.}, non-erasing morphisms of the free monoid, are simple combinatorial objects which produce infinite words by replacing iteratively letters by words. This paper introduces a notion of substitution acting on multi-dimensional words, namely the \emph{local rule substitutions}. Roughly speaking, \emph{local rules} play for multi-dimensional words the role played by the concatenation product for substitutions on words. We then particularly focus on the local rule substitutions which act on the $2$-dimensional words coding \emph{stepped surfaces}, and we show that a wide class of them can be derived from \emph{generalized substitutions}.
Document type :
Journal articles
Complete list of metadata
Contributor : Thomas Fernique Connect in order to contact the contributor
Submitted on : Friday, May 25, 2007 - 1:32:27 PM
Last modification on : Friday, August 5, 2022 - 10:45:45 AM
Long-term archiving on: : Thursday, April 8, 2010 - 5:52:59 PM


  • HAL Id : lirmm-00149362, version 1



Thomas Fernique. Local Rule Substitutions and Stepped Surfaces. Theoretical Computer Science, Elsevier, 2007, 380, pp.317-329. ⟨lirmm-00149362⟩



Record views


Files downloads