Supposons que nous ayons un langage simple composé des termes: truetrue\mathtt{true} falsefalse\mathtt{false} si sont des termes, alorst1,t2,t3t1,t2,t3t_1,t_2,t_3ift1thent2elset3ift1thent2elset3\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 Supposons maintenant les règles...
J'ai fait un peu de recherche sur Google et je suis venu un peu court. Je me demande quelles sont les principales raisons pour lesquelles les informaticiens, les programmeurs, étudient la réécriture de termes et / ou la réécriture de graphes de termes. Pour autant que je sache, cela aide simplement...
Système de réécriture est un ensemble de règles sous la forme de . Si nous appliquons cette règle à une chaîne w, nous remplaçons toute sous-chaîne A dans w par une sous-chaîne B et vice versa.A↔BA↔BA \leftrightarrow BwwwAAAwwwBBB Étant donné une chaîne de départ nous pouvons dériver B A A B dans...
Soit être -reduction dans le -calculus. Définissez -expansion par .→β→β\to_\betaββ\betaλλ\lambdaββ\beta←β←β\leftarrow_\betat′←βt⟺t→βt′t′←βt⟺t→βt′t'\leftarrow_\beta t \iff t\to_\beta t' Est confluentes? En d'autres termes, avons-nous cela pour tout , si , alors il existe tel que...