# Local Rule Substitutions and Stepped Surfaces

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}.
Keywords :
Document type :
Journal articles
Domain :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00149362
Contributor : Thomas Fernique <>
Submitted on : Friday, May 25, 2007 - 1:32:27 PM
Last modification on : Tuesday, January 12, 2021 - 3:33:23 AM
Long-term archiving on: : Thursday, April 8, 2010 - 5:52:59 PM

### Identifiers

• HAL Id : lirmm-00149362, version 1

### Citation

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

Record views