En informática teórica y lógica matemática, un sistema de reescritura de cadenas ( SRS ), históricamente llamado sistema semi- Thue , es un sistema de reescritura sobre cadenas de un alfabeto (generalmente finito ) . Dada una relación binaria entre cadenas fijas sobre el alfabeto, llamadas reglas de reescritura , denotadas por, un SRS extiende la relación de reescritura a todas las cadenas en las que el lado izquierdo y derecho de las reglas aparecen como subcadenas , es decir, dónde , , , y son cadenas.
La noción de un sistema semi-Thue coincide esencialmente con la presentación de un monoide . Por lo tanto, constituyen un marco natural para resolver el problema verbal de monoides y grupos.
Un SRS se puede definir directamente como un sistema de reescritura abstracta . También puede verse como un tipo restringido de sistema de reescritura de términos . Como formalismo, los sistemas de reescritura de cadenas son Turing completos . [ cita requerida ] El nombre semi-Thue proviene del matemático noruego Axel Thue , quien introdujo el tratamiento sistemático de los sistemas de reescritura de cuerdas en un artículo de 1914. [1] Thue introdujo esta noción con la esperanza de resolver el problema verbal de semigrupos presentados de forma finita. Solo en 1947 se demostró que el problema era indecidible ; este resultado fue obtenido de forma independiente por Emil Post y AA Markov Jr. [2] [3]
Definición
Un sistema de reescritura de cadenas o un sistema semi-Thue es una tupla dónde
- Σ es un alfabeto, generalmente asumido como finito. [4] Los elementos del conjunto(* es la estrella de Kleene aquí) son cadenas finitas (posiblemente vacías) en Σ , a veces llamadas palabras en lenguajes formales ; simplemente las llamaremos cadenas aquí.
- R es una relación binaria en cadenas de Σ , es decir, Cada elemento se llama una regla (de reescritura) y generalmente se escribe.
Si la relación R es simétrica , entonces el sistema se llama sistema Thue .
Las reglas de reescritura en R se pueden extender naturalmente a otras cadenas enpermitiendo subcadenas que ser reescrito de acuerdo con R . Más formalmente, la relación de relación de reescritura de un pasoinducido por R en para cualquier cuerda :
- si y solo si existen tal que , , y .
Desde es una relación en , el par se ajusta a la definición de un sistema de reescritura abstracta . Obviamente, R es un subconjunto de. Algunos autores usan una notación diferente para la flecha en (p.ej ) para distinguirlo de la propia R (), Ya que más tarde quieren ser capaz de soltar el subíndice y aún evitar la confusión entre R y la reescritura de un solo paso inducida por R .
Claramente, en un sistema semi-Thue podemos formar una secuencia (finita o infinita) de cadenas producidas comenzando con una cadena inicial. y reescribiéndolo repetidamente haciendo un reemplazo de subcadena a la vez:
Una reescritura de cero o más pasos como esta es capturada por el cierre transitivo reflexivo de, denotado por (ver sistema de reescritura de resúmenes # Nociones básicas ). Esto se llama relación de reescritura o relación de reducción eninducida por R .
Thue congruencia
En general, el conjunto de cadenas en un alfabeto forma un monoide libre junto con la operación binaria de concatenación de cadenas (denotado comoy escrito multiplicativamente dejando caer el símbolo). En un SRS, la relación de reducción es compatible con la operación monoide, lo que significa que implica para todas las cuerdas . Desdees por definición un pedido anticipado ,forma un preorden monoidal .
Del mismo modo, el cierre simétrico transitivo reflexivo de, denotado (ver sistema de reescritura abstracta # Nociones básicas ), es una congruencia , lo que significa que es una relación de equivalencia (por definición) y también es compatible con la concatenación de cadenas. La relaciónse llama la congruencia Thue generada por R . En un sistema Thue, es decir, si R es simétrico, la relación de reescritura coincide con la congruencia de Thue .
Presentaciones de factor monoide y monoide
Desde es una congruencia, podemos definir el factor monoide del monoide libre por la congruencia de Thue de la manera habitual . Si un monoidees isomorfo con, luego el sistema semi-Thue se llama presentación monoide de.
Inmediatamente obtenemos algunas conexiones muy útiles con otras áreas del álgebra. Por ejemplo, el alfabeto { a , b } con las reglas { ab → ε, ba → ε}, donde ε es la cadena vacía , es una presentación del grupo libre en un generador. Si en cambio las reglas son solo { ab → ε}, entonces obtenemos una presentación del monoide bicíclico .
La importancia de los sistemas semi-Thue como presentación de monoides se ve reforzada por lo siguiente:
Teorema : cada monoide tiene una presentación de la forma, por lo tanto, siempre se puede presentar mediante un sistema semi-Thue, posiblemente sobre un alfabeto infinito. [5]
En este contexto, el conjunto se llama el conjunto de generadores de, y se llama el conjunto de relaciones definitorias . Podemos clasificar de inmediato los monoides en función de su presentación. se llama
- finamente generado si es finito.
- finitamente presentado si ambos y son finitos.
El problema verbal de los sistemas semi-Thue
El problema verbal para los sistemas semi-Thue se puede plantear de la siguiente manera: Dado un sistema semi-Thue y dos palabras (cadenas) , lata ser transformado en aplicando reglas de ? Este problema es indecidible , es decir, no existe un algoritmo general para resolver este problema. Esto incluso es válido si limitamos la entrada a sistemas finitos [ definición necesaria ] .
Martin Davis ofrece al lector lego una prueba de dos páginas en su artículo "¿Qué es una Computación?" págs. 258-259 con comentario pág. 257. Davis presenta la prueba de esta manera: "Invente [un problema verbal] cuya solución conduciría a una solución al problema que se detiene ".
Conexiones con otras nociones
Un sistema semi-Thue también es un sistema de reescritura de términos , uno que tiene palabras monádicas (funciones) que terminan en la misma variable que los términos del lado izquierdo y derecho, [6] por ejemplo, una regla de término es equivalente a la regla de la cadena .
Un sistema semi-Thue también es un tipo especial de sistema canónico Post , pero cada sistema canónico Post también se puede reducir a un SRS. Ambos formalismos son Turing completos y, por lo tanto, equivalen a las gramáticas irrestrictas de Noam Chomsky , que a veces se denominan gramáticas semi-Thue . [7] Una gramática formal solo se diferencia de un sistema semi-Thue por la separación del alfabeto en terminales y no terminales, y la fijación de un símbolo inicial entre los no terminales. Una minoría de autores realmente define un sistema semi-Thue como un triple, dónde se llama conjunto de axiomas . Bajo esta definición "generativa" de sistema semi-Thue, una gramática sin restricciones es simplemente un sistema semi-Thue con un solo axioma en el que se divide el alfabeto en terminales y no terminales, y hace que el axioma sea no terminal. [8] El simple artificio de dividir el alfabeto en terminales y no terminales es poderoso; permite la definición de la jerarquía de Chomsky basada en qué combinación de terminales y no terminales contienen las reglas. Este fue un avance crucial en la teoría de los lenguajes formales .
En computación cuántica, se puede desarrollar la noción de un sistema Thue cuántico. [9] Dado que la computación cuántica es intrínsecamente reversible, las reglas de reescritura sobre el alfabetodeben ser bidireccionales (es decir, el sistema subyacente es un sistema Thue, no un sistema semi-Thue). En un subconjunto de caracteres del alfabeto se puede adjuntar un espacio Hilbert , y una regla de reescritura que lleva una subcadena a otra puede realizar una operación unitaria sobre el producto tensorial del espacio de Hilbert unido a las cuerdas; esto implica que conservan el número de caracteres del conjunto. Al igual que en el caso clásico, se puede demostrar que un sistema Thue cuántico es un modelo computacional universal para el cálculo cuántico, en el sentido de que las operaciones cuánticas ejecutadas corresponden a clases de circuitos uniformes (como las de BQP cuando, por ejemplo, se garantiza la terminación de las reglas de reescritura de cadenas dentro de polinomialmente muchos pasos en el tamaño de entrada), o equivalentemente una máquina cuántica de Turing .
Historia e importancia
Los sistemas Semi-Thue se desarrollaron como parte de un programa para agregar constructos adicionales a la lógica , a fin de crear sistemas como la lógica proposicional , que permitirían expresar teoremas matemáticos generales en un lenguaje formal y luego probarlos y verificarlos en un lenguaje automático. , moda mecánica. La esperanza era que el acto de demostrar el teorema pudiera entonces reducirse a un conjunto de manipulaciones definidas en un conjunto de cadenas. Posteriormente se descubrió que los sistemas semi-Thue son isomórficos a las gramáticas no restringidas , que a su vez se sabe que son isomórficas a las máquinas de Turing . Este método de investigación tuvo éxito y ahora las computadoras pueden usarse para verificar las demostraciones de teoremas matemáticos y lógicos.
Por sugerencia de Alonzo Church , Emil Post en un artículo publicado en 1947, demostró por primera vez que "cierto Problema de Thue" era irresoluble, lo que Martin Davis afirma como "... la primera prueba irresoluble de un problema de las matemáticas clásicas - en este caso, el problema verbal para semigrupos ". [10]
Davis también afirma que AA Markov ofreció la prueba de forma independiente . [11]
Ver también
- Sistema L
- MU rompecabezas
Notas
- ^ Libro y Otto, p. 36
- ^ Abramsky y col. pag. 416
- ↑ Salomaa et al., P. 444
- ↑ En Book y Otto se define un sistema semi-Thue sobre un alfabeto finito a lo largo de la mayor parte del libro, excepto en el capítulo 7 cuando se introduce la presentación monoide, cuando esta suposición se abandona silenciosamente.
- ^ Libro y Otto, Teorema 7.1.7, p. 149
- ^ Nachum Dershowitz y Jean-Pierre Jouannaud . Rewrite Systems (1990) pág. 6
- ^ DIA Cohen , Introducción a la teoría de la computadora, 2da ed., Wiley-India, 2007, ISBN 81-265-1334-9 , p.572
- ^ Dan A. Simovici, Richard L. Tenney, Teoría de lenguajes formales con aplicaciones , World Scientific, 1999 ISBN 981-02-3729-4 , capítulo 4
- ^ J. Bausch, T. Cubitt, M. Ozols, La complejidad de las cadenas de giro traslacionalmente invariantes con una dimensión local baja , Ann. Henri Poincaré 18 (11), 2017 doi : 10.1007 / s00023-017-0609-7 págs. 3449-3513
- ^ Martin Davis (editor) (1965), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , after page 292, Raven Press , Nueva York
- ↑ AA Markov (1947) Doklady Akademii Nauk SSSR (NS) 55: 583–586
Referencias
Monografías
- Ronald V. Book y Friedrich Otto, String-rewriting Systems , Springer, 1993, ISBN 0-387-97965-4 .
- Matthias Jantzen, Reescritura de cadenas confluentes , Birkhäuser, 1988, ISBN 0-387-13715-7 .
Libros de texto
- Martin Davis , Ron Sigal, Elaine J. Weyuker, Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica , 2a ed., Academic Press, 1994, ISBN 0-12-206382-1 , capítulo 7
- Elaine Rich, Autómatas, computabilidad y complejidad: teoría y aplicaciones , Prentice Hall, 2007, ISBN 0-13-228806-0 , capítulo 23.5.
Encuestas
- Samson Abramsky, Dov M. Gabbay, Thomas SE Maibaum (ed.), Handbook of Logic in Computer Science: Semantic modelado , Oxford University Press, 1995, ISBN 0-19-853780-8 .
- Grzegorz Rozenberg, Arto Salomaa (ed.), Handbook of Formal Languages: Word, language, grammar , Springer, 1997, ISBN 3-540-60420-0 .
Papeles de referencia
- Emil Post (1947) La insolubilidad recursiva de un problema de Thue , The Journal of Symbolic Logic 12: 1-11 a través del Proyecto Euclides .