En matemáticas , los subdesplazamientos de tipo finito se utilizan para modelar sistemas dinámicos y, en particular, son objeto de estudio en dinámica simbólica y teoría ergódica . También describen el conjunto de todas las secuencias posibles ejecutadas por una máquina de estados finitos . Los espacios de turnos más estudiados son los subdesplazamientos de tipo finito.
Definición
Dejar ser un conjunto finito de símbolos (alfabeto). Sea X el conjuntode todas las secuencias bi-infinito de elementos de V junto con el operador de desplazamiento T . Dotamos a V con la topología discreta ya X con la topología del producto . Un flujo simbólico o subshift es un cerrado T subconjunto -invariant Y de X [1] y el idioma asociado L Y es el conjunto de subsecuencias finitos de Y . [2]
Ahora deja frijol matriz de adyacencia con entradas en {0,1}. Usando estos elementos construimos un gráfico dirigido G = ( V , E ) con V el conjunto de vértices y E el conjunto de aristas que contienen la arista dirigidaen E si y solo si. Sea Y el conjunto de todas las sucesiones de aristas admisibles infinitas , donde por admisible se entiende que la sucesión es un recorrido por el gráfico, y la sucesión puede ser infinita unilateral o bilateral. Sea T el operador de desplazamiento a la izquierda en tales secuencias; desempeña el papel de operador de evolución temporal del sistema dinámico. Un subdesplazamiento de tipo finito se define entonces como un par ( Y , T ) obtenido de esta manera. Si la secuencia se extiende hasta el infinito en una sola dirección, se denomina subdesplazamiento unilateral de tipo finito, y si es bilateral , se denomina subdesplazamiento bilateral de tipo finito.
Formalmente, se pueden definir las secuencias de aristas como
Este es el espacio de todas las secuencias de símbolos de modo que el símbolo p puede ir seguido del símbolo q solo si la entrada (p, q) ésima de la matriz A es 1. El espacio de todas las secuencias bi-infinitas se define de forma análoga:
El operador de cambio T mapea una secuencia en el cambio de uno o dos lados a otro desplazando todos los símbolos a la izquierda, es decir
Claramente, este mapa solo es invertible en el caso del cambio de dos lados.
Un subdesplazamiento de tipo finito se llama transitivo si G está fuertemente conectado : hay una secuencia de aristas desde cualquier vértice a cualquier otro vértice. Son precisamente los subdesplazamientos transitivos de tipo finito los que corresponden a sistemas dinámicos con órbitas densas.
Un caso especial importante es el n- shift completo : tiene un gráfico con una arista que conecta cada vértice con todos los demás vértices; es decir, todas las entradas de la matriz de adyacencia son 1. El desplazamiento n completo corresponde al esquema de Bernoulli sin la medida .
Terminología
Por convención, se entiende que el término cambio se refiere al cambio n completo. Un subdesplazamiento es entonces cualquier subespacio del turno completo que es invariante al cambio (es decir, un subespacio que es invariante bajo la acción del operador de turno), no vacío y cerrado para la topología del producto definida a continuación. Algunos subdesplazamientos se pueden caracterizar por una matriz de transición, como se indicó anteriormente; estos subdesplazamientos se denominan subdesplazamientos de tipo finito. A menudo, los subdesplazamientos de tipo finito se denominan simplemente desplazamientos de tipo finito . Los subdesplazamientos de tipo finito también se denominan a veces cambios de Markov topológicos .
Ejemplos de
Muchos sistemas dinámicos caóticos son isomorfos a subdesplazamientos de tipo finito; los ejemplos incluyen sistemas con conexiones homoclínicas transversales , difeomorfismos de variedades cerradas con una entropía métrica positiva , el sistema Prouhet-Thue-Morse , el sistema Chacon (este es el primer sistema que se muestra que se mezcla débilmente pero no fuertemente ), los sistemas Sturmian y Toeplitz sistemas . [3]
Generalizaciones
Un sistema sofic es una imagen de un subdesplazamiento de tipo finito donde diferentes bordes del gráfico de transición pueden asignarse al mismo símbolo. [ cuando se define como? ] Puede considerarse como el conjunto de etiquetas de caminos a través de un autómata : un subdesplazamiento de tipo finito corresponde entonces a un autómata que es determinista . [4] Estos sistemas corresponden a idiomas regulares .
Los sistemas libres de contexto se definen de forma análoga y se generan mediante gramáticas de estructura de frases .
Un sistema de renovación se define como el conjunto de todas las concatenaciones infinitas de alguna colección finita fija de palabras finitas.
Los subdesplazamientos de tipo finito son idénticos a los modelos de Potts unidimensionales libres (que no interactúan) ( generalizaciones de n letras de los modelos de Ising ), con ciertas configuraciones de vecino más cercano excluidas. Los modelos Ising interactivos se definen como subdesplazamientos junto con una función continua del espacio de configuración [ cuando se define como? ] (continua con respecto a la topología del producto, definida a continuación); la función de partición y el hamiltoniano se pueden expresar explícitamente en términos de esta función. [ aclaración necesaria ]
Los subdesplazamientos pueden cuantificarse de cierta manera, lo que lleva a la idea de los autómatas finitos cuánticos .
Topología
Un subdesplazamiento tiene una topología natural, derivada de la topología del producto en, dónde
ya V se le da la topología discreta . Una base para la topología de, que induce la topología del subdesplazamiento, es la familia de juegos de cilindros
Los juegos de cilindros son juegos abiertos en. Cada set abierto enes una unión contable de conjuntos de cilindros. Cada conjunto abierto en el subdesplazamiento es la intersección de un conjunto abierto decon el subdesplazamiento. Con respecto a esta topología, el desplazamiento T es un homeomorfismo ; es decir, con respecto a esta topología, es continua con inversa continua.
Métrico
Se puede definir una variedad de métricas diferentes en un espacio de turno. Se puede definir una métrica en un espacio de turno considerando dos puntos como "cercanos" si tienen muchos símbolos iniciales en común; esta es la métrica p -ádica . De hecho, los espacios de cambio de uno y dos lados son espacios métricos compactos .
La medida
Un subdesplazamiento de tipo finito puede estar dotado de cualquiera de varias medidas diferentes , lo que conduce a un sistema dinámico que conserva la medida . Un objeto común de estudio es la medida de Markov , que es una extensión de una cadena de Markov a la topología del cambio.
Una cadena de Markov es un par ( P , π) que consta de la matriz de transición , una matriz por lo cual todos y
por todo i . El vector de probabilidad estacionario tiene todo y tiene
- .
Se dice que una cadena de Markov, como se definió anteriormente, es compatible con el desplazamiento de tipo finito si cuando sea . La medida de Markov de un juego de cilindros se puede definir entonces por
La entropía de Kolmogorov-Sinai con relación a la medida de Markov es
Función Zeta
La función zeta de Artin-Mazur se define como la serie de potencias formales
donde Fix ( T n ) es el conjunto de puntos fijos del desplazamiento de n veces. [5] Tiene una fórmula de producto
donde γ corre sobre las órbitas cerradas. [5] Para subdesplazamientos de tipo finito, la función zeta es una función racional de z : [6]
Ver también
- Operador de transferencia
- Gráfico de Bruijn
- Autómatas finitos cuánticos
- Axioma A
Notas
- ↑ Xie (1996) p.21
- ↑ Xie (1996) p.22
- ^ Matthew Nicol y Karl Petersen, (2009) " Teoría ergódica: construcciones y ejemplos básicos ", Enciclopedia de la complejidad y la ciencia de sistemas , Springer https://doi.org/10.1007/978-0-387-30440-3_177
- ↑ Pytheas Fogg (2002) p.205
- ↑ a b Brin y Stuck (2002) p.60
- ^ Brin y Stuck (2002) p.61
Referencias
- Brin, Michael; Atascado, Garrett (2002). Introducción a los sistemas dinámicos (2ª ed.). Prensa de la Universidad de Cambridge . ISBN 0-521-80841-3.
- David Damanik, Subshifts estrictamente ergódicos y operadores asociados , (2005)
- Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de clase en matemáticas. 1794 . Berlín: Springer-Verlag . ISBN 3-540-44141-7. Zbl 1014.11015 .
- Natasha Jonoska , Subshifts of Finite Type, Sofic Systems and Graphs , (2000).
- Michael S. Keane, Teoría ergódica y subdesplazamientos de tipo finito , (1991), que aparece como Capítulo 2 en Teoría ergódica, Dinámica simbólica y espacios hiperbólicos , Tim Bedford, Michael Keane y Caroline Series, Eds. Prensa de la Universidad de Oxford, Oxford (1991). ISBN 0-19-853390-X (Proporciona una breve introducción expositiva, con ejercicios y referencias extensas).
- Lind, Douglas; Marcus, Brian (1995). Introducción a la codificación y la dinámica simbólica . Prensa de la Universidad de Cambridge . ISBN 0-521-55124-2. Zbl 1106.37301 .
- Teschl, Gerald (2012). Ecuaciones diferenciales ordinarias y sistemas dinámicos . Providencia : Sociedad Matemática Estadounidense . ISBN 978-0-8218-8328-0.
- Xie, Huimin (1996). Complejidad gramatical y sistemas dinámicos unidimensionales . Direcciones en el caos. 6 . World Scientific. ISBN 9810223986.
Otras lecturas
- Williams, Susan G., ed. (2004). Dinámica simbólica y sus aplicaciones: American Mathematical Society, curso corto, 4-5 de enero de 2002, San Diego, California . Actas de simposios en matemáticas aplicadas: notas de clase del curso corto de AMS. 60 . Sociedad Matemática Estadounidense . ISBN 0-8218-3157-7. Zbl 1052.37003 .