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 :
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2007, 380, pp.317-329

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00149362
Contributeur : Thomas Fernique <>
Soumis le : vendredi 25 mai 2007 - 13:32:27
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : jeudi 8 avril 2010 - 17:52:59

Identifiants

• 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〉

Métriques

Consultations de la notice

272

Téléchargements de fichiers