Término matemático
En matemáticas y ciencias de la computación, 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 mórfica. [1]
Definición
Sea f un endomorfismo del monoide libre A ∗ en 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
es una palabra mórfica pura o pura 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 que comienza con la letra a . [2] [3] En general, una palabra mórfica es la imagen de una palabra mórfica pura bajo una codificación, es decir, un morfismo que asigna letra a letra. [1]
Si una palabra mórfica se construye como el punto fijo de un morfismo k - uniforme prolongable en A ∗ entonces la palabra es k - automática . El término n -ésimo en tal secuencia puede ser producido por un autómata de estados finitos que lea los dígitos de n en base k . [1]
Ejemplos
- La secuencia de Thue-Morse se genera sobre {0,1} por el endomorfismo 2-uniforme 0 → 01, 1 → 10. [4] [5]
- La palabra de Fibonacci se genera sobre { a , b } por el endomorfismo a → ab , b → a . [1] [4]
- La palabra tribonacci se genera sobre { a , b , c } por 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]
Sistema D0L
Un sistema D0L ( sistema Lindenmayer determinista y libre de contexto ) está dado por una palabra w del monoide libre A ∗ en un alfabeto A junto con un morfismo σ prolongable en w . El sistema genera la palabra D0L infinita ω = lim n →∞ σ n ( w ). Las palabras puramente mórficas 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 mórfica, donde z es una letra que no está en A . [7]
Véase también
Referencias
- ^ abcd Lotario (2005) pág. 524
- ^ Lothaire (2011) pág. 10
- ^ Honkala (2010) pág. 505
- ^ de Lothaire (2011) pág. 11
- ^ abc Lothaire (2005) pág. 525
- ^ Lothaire (2005) pág. 526
- ^ Honkala (2010) pág. 506
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . 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 . págs. 505–529. ISBN 978-0-521-51597-9.Zbl1216.68209 .
- Lothaire, M. (2005). Combinatoria aplicada a las palabras . Enciclopedia de matemáticas y sus aplicaciones. Vol. 105. Un trabajo colectivo 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: Cambridge University Press . ISBN. 0-521-84802-4.Zbl 1133.68067 .
- Lothaire, M. (2011). Combinatoria algebraica sobre 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 de tapa dura de 2002). Cambridge University Press. ISBN 978-0-521-18071-9.Zbl 1221.68183 .
Lectura adicional
- Cassaigne, Julien; Karhumäki, Juhani (1997). "Palabras de Toeplitz, periodicidad generalizada y morfismos iterados periódicamente". Revista Europea de Combinatoria . 18 (5): 497–510. doi : 10.1006/eujc.1996.0110 . Zbl 0881.68065.
