Término de matemáticas
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 .
Cada 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 hay una letra a tal que f ( a ) = como para una cadena s no vacía : decimos que f es prolongable en a . La palabra
Es una palabra puramente mórfica 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 : el secuencia única 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 n -ésimo término en tal secuencia puede ser producido por un autómata de estados finitos que lee los dígitos de n en base k . [1]
Ejemplos
- La secuencia 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 } 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 uniforme 2 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 uniforme 2 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 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 | tu | ≥ | w |, entonces z ν es una palabra puramente mórfica, donde z es una letra que no está en A. [7]
Ver también
Referencias
- ^ abcd Lothaire (2005) p.524
- ^ Lotario (2011) pág. 10
- ^ Honkala (2010) p.505
- ^ ab Lothaire (2011) pág. 11
- ^ abc Lothaire (2005) p.525
- ^ Lotario (2005) p.526
- ^ Honkala (2010) p.506
- Allouche, Jean-Paul; Shalit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Prensa de la Universidad de Cambridge . ISBN 978-0-521-82332-6. Zbl 1086.11015.
- Honkala, Juha (2010). "El problema de la igualdad de 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: Prensa de la Universidad de Cambridge . págs. 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.
- Lotario, M. (2011). Combinatoria algebraica sobre palabras . Enciclopedia de Matemáticas y sus aplicaciones. vol. 90. Con prefacio de Jean Berstel y Dominique Perrin (Reimpresión de la edición de tapa dura de 2002). Prensa de la Universidad de Cambridge. ISBN 978-0-521-18071-9. Zbl 1221.68183.
Otras lecturas
- Cassaigne, Julien; Karhumäki, Juhani (1997). "Palabras de Toeplitz, periodicidad generalizada y morfismos periódicamente iterados". Revista europea de combinatoria . 18 (5): 497–510. doi : 10.1006/eujc.1996.0110 . Zbl 0881.68065.
