Local Rule Substitutions and Stepped Surfaces - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Theoretical Computer Science Year : 2007

Local Rule Substitutions and Stepped Surfaces

Thomas Fernique
  • Function : Author
  • PersonId : 938430


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}.
Fichier principal
Vignette du fichier
local.pdf (290.79 Ko) Télécharger le fichier

Dates and versions

lirmm-00149362 , version 1 (25-05-2007)



Thomas Fernique. Local Rule Substitutions and Stepped Surfaces. Theoretical Computer Science, 2007, 380, pp.317-329. ⟨10.1016/j.tcs.2007.03.021⟩. ⟨lirmm-00149362⟩
268 View
175 Download



Gmail Facebook X LinkedIn More