Sistema Semi-Thue

---

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 , donde ,, ${\ Displaystyle R}$${\ displaystyle s \ rightarrow t}$${\ displaystyle usv \ rightarrow utv}$${\ Displaystyle s}$${\ Displaystyle t}$${\ Displaystyle u}$y son cadenas.${\ Displaystyle v}$

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]}

Un sistema de reescritura de cadenas o un sistema semi-Thue es una tupla donde ${\ Displaystyle (\ Sigma, R)}$

Las reglas de reescritura en R se pueden extender naturalmente a otras cadenas al permitir que las subcadenas se reescriban de acuerdo con R. Más formalmente, la relación de reescritura de un paso inducida por R para cualquier cadena :${\ Displaystyle \ Sigma ^ {*}}$${\ displaystyle {\ xrightarrow [{R}] {}}}$${\ Displaystyle \ Sigma ^ {*}}$${\ Displaystyle s, t \ in \ Sigma ^ {*}}$

---