Est-il possible de dériver une chaîne dans ce système de réécriture?

Système de réécriture est un ensemble de règles sous la forme de . Si nous appliquons cette règle à une chaîne nous remplaçons toute sous-chaîne dans par une sous-chaîne et vice versa. $A \leftrightarrow B$ $w$ $A$ $w$ $B$

Étant donné une chaîne de départ nous pouvons dériver dans le système avec les règles suivantes: $AAABB$ $BAAB$

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

Existe-t-il un algorithme général pour cela?

computability term-rewriting Daniil
la source

J'apprécierais si vous pouviez ajouter plus de balises à cette question, ou changer le jeu de règles pour le rendre plus cool.

Daniil

@JD Je pense qu'en général, ce problème de réécriture ne peut pas être résolu, car vous pouvez modéliser la machine Turing avec un tel système de réécriture et un problème de dérivation == problème d'arrêt dans TM

Daniil

@JD ah, c'est logique, je devrais en lire plus, merci!

Daniil

@Daniil et futurs lecteurs: Le problème indécidable utilisé est le problème de la correspondance .

2012

Il s'agit essentiellement de l'idée d'algorithme de Markov.

vonbrand

Réponses:

$A$ $A$

$A \to BA$

Aryabhata
la source

Oui, IIRC, c'est indécidable parce que vous pouvez modéliser une MT avec un ensemble spécifique de règles de réécriture.

Daniil