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 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 pura mórfica o pura sustitutiva . Tenga en cuenta 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 mapea letra a letra. [1]
Si una palabra mórfica se construye como el punto fijo de un k prolongable - morfismo uniforme 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 estado finito leyendo los dígitos de n en base k . [1]
Ejemplos de
- La secuencia Thue-Morse se genera sobre {0,1} por el endomorfismo uniforme 2 0 → 01, 1 → 10. [4] [5]
- La palabra 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 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 de plegado regular 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 ) viene 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 carta no en una . [7]
Ver también
Referencias
- Allouche, Jean-Paul; Shallit, 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. 135 . Cambridge: Cambridge University Press . págs. 505–529. ISBN 978-0-521-51597-9. Zbl 1216.68209 .
- Lothaire, M. (2005). Combinatoria aplicada sobre palabras . Enciclopedia de las matemáticas y sus aplicaciones. 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: Cambridge University Press . ISBN 0-521-84802-4. Zbl 1133.68067 .
- Lothaire, M. (2011). Combinatoria algebraica sobre palabras . Enciclopedia de las matemáticas y sus aplicaciones. 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 iterados periódicamente" . Revista europea de combinatoria . 18 : 497–510. doi : 10.1006 / eujc.1996.0110 . Zbl 0881.68065 .