Palabra morfológica

En matemáticas e informática, una palabra mórfica o palabra sustitutiva es una secuencia infinita de símbolos que se construye a partir de una clase particular de endomorfismo de un monoide libre .

Toda secuencia automática es morfológica. ^{[ 1 ]}

Sea f un endomorfismo del monoide libre A ^∗ sobre un alfabeto A con la propiedad de que existe una letra a tal que f ( a ) = como para una cadena no vacía s : decimos que f es prolongable en a . La palabra

${\displaystyle asf(s)f(f(s))\cdots f^{(n)}(s)\cdots \ }$

es una palabra puramente mórfica o puramente sustitutiva . Nótese que es el límite de la secuencia a , f ( a ), f ( f ( a )), f ( f ( f ( a ))), ... Es claramente un punto fijo del endomorfismo f : la única secuencia de este tipo que comienza con la letra a . ^{[ 2 ] [ 3 ]} En general, una palabra mórfica es la imagen de una palabra puramente mórfica bajo una codificación, es decir, un morfismo que mapea letra por letra. ^{[ 1 ]}

Si una palabra mórfica se construye como el punto fijo de un morfismo uniforme k - prolongable en A ^∗ , entonces la palabra es k - automática . El n -ésimo término de dicha secuencia puede ser producido por un autómata de estados finitos que lee los dígitos de n en base k . ^{[ 1 ]}

• La secuencia de Thue-Morse se genera sobre {0,1} mediante el endomorfismo 2-uniforme 0 → 01, 1 → 10. ^{[ 4 ] [ 5 ]}
• La palabra de Fibonacci se genera sobre { a , b } mediante el endomorfismo a → ab , b → a . ^{[ 1 ] [ 4 ]}
• La palabra de Tribonacci se genera sobre { a , b , c } mediante el endomorfismo a → ab , b → ac , c → a . ^{[ 5 ]}
• La secuencia de Rudin-Shapiro se obtiene a partir del punto fijo del morfismo 2-uniforme a → ab , b → ac , c → db , d → dc seguido de la codificación a , b → 0, c , d → 1. ^{[ 5 ]}
• La secuencia regular de plegado de papel se obtiene a partir del punto fijo del morfismo 2-uniforme a → ab , b → cb , c → ad , d → cd seguido de la codificación a , b → 0, c , d → 1. ^{[ 6 ]}

Un sistema D0L ( sistema de Lindenmayer determinista libre de contexto ) está dado por una palabra w del monoide libre A ^∗ sobre un alfabeto A junto con un morfismo σ prolongable en w . El sistema genera la palabra D0L infinita ω = lim _{n →∞} σ ⁿ ( w ). Las palabras puramente morfológicas son palabras D0L, pero no a la inversa. Sin embargo, si ω = u ν es una palabra D0L infinita con un segmento inicial u de longitud | u | ≥ | w |, entonces z ν es una palabra puramente morfológica, donde z es una letra que no está en A. ^{[ 7 ]}

• Secuencia de corte
• Lyndon palabra
• Palabra de Hall
• Palabra de Sturm

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations . Cambridge University Press . ISBN 978-0-521-82332-6. Zbl 1086.11015 . 
• Honkala, Juha (2010). «El problema de la igualdad para palabras puramente sustitutivas». En Berthé, Valérie ; Rigo, Michel (eds.). Combinatoria, autómatas y teoría de números . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  135. Cambridge: Cambridge University Press . pp. 505–529 . ISBN  978-0-521-51597-9. Zbl 1216.68209 . 
• Lotario, M. (2005). Combinatoria aplicada a las palabras . Enciclopedia de Matemáticas y sus aplicaciones. vol.  105. Una obra colectiva de Jean Berstel , Dominique Perrin, Maxime Crochemore , Eric Laporte, Mehryar Mohri , Nadia Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman , Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche y Valérie Berthé . Cambridge: Prensa de la Universidad de Cambridge . ISBN 0-521-84802-4. Zbl 1133.68067 . 
• Lothaire, M. (2011). Combinatoria algebraica en palabras . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  90. Con prólogo de Jean Berstel y Dominique Perrin (Reimpresión de la  edición en tapa dura de 2002). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183 . 

• Cassaigne, Julien; Karhumäki, Juhani (1997). "Palabras de Toeplitz, periodicidad generalizada y morfismos iterados periódicamente" . European Journal of Combinatorics . 18 (5): 497– 510. doi : 10.1006/eujc.1996.0110 . Zbl 0881.68065 .