¿Es posible derivar una cadena en este sistema de reescritura?

Sistema de reescritura es un conjunto de reglas en forma de . Si aplicamos esa regla a una cadena , reemplazamos cualquier subcadena en con una subcadena y viceversa. $A \leftrightarrow B$ $w$ $A$ $w$ $B$

Dada una cadena de inicio podemos derivar en el sistema con las siguientes reglas: $AAABB$ $BAAB$

$A \leftrightarrow BA$
$BABA \leftrightarrow AABB$
$AAA \leftrightarrow AB$
$BA \leftrightarrow AB$

¿Hay un algoritmo general para eso?

computability term-rewriting Daniil
fuente

Le agradecería si pudiera agregar más etiquetas a esta pregunta, o cambiar el conjunto de reglas para que se vea mejor.

Daniil

@JD Creo que, en general, este problema de reescritura no se puede resolver, porque puede modelar la máquina Turing con un sistema de reescritura y un problema de derivación == problema de detención en TM

Daniil

@JD ah, eso tiene sentido, debería leer más, gracias!

Daniil

@Daniil y futuros lectores: El problema indecidible utilizado es el problema de correspondencia posterior .

jmad

Esta es esencialmente la idea de algoritmo de Markov.

vonbrand

Respuestas:

Observe que la paridad del número de s no cambia. Como una cadena contiene un número impar y la otra par, no son accesibles. $A$ $A$

Creo en general (para un conjunto arbitrario de reglas, no su ejemplo específico), es probable que este sea un problema indecidible. Si las transformaciones son unidireccionales (es decir, reglas de la forma ), es así, por ejemplo, consulte: Sistema de etiquetas . $A \to BA$

Aryabhata
fuente

Sí, IIRC, es indecidible porque puedes modelar una TM con un conjunto específico de reglas de reescritura.

Daniil