Publication
A Novel Basis for Logic Rewriting
Concepts associés (37)
Unification
vignette|Unifier deux termes, c'est les rendre identiques en remplaçant les variables. En informatique et en logique, l'unification est un processus algorithmique qui, étant donnés deux termes, trouve une substitution qui appliquée aux deux termes les rend identiques. Par exemple, et peuvent être rendus identiques par la substitution et , qui donne quand on l'applique à chacun de ces termes le terme .
Algorithme probabiliste
En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].
Fonction parité
La fonction parité est une fonction booléenne. La sortie vaut 1, si et seulement si, le nombre de 1 dans l'entrée est impaire. Un cas particulier est la fonction parité avec deux entrées, qui est connue sous le nom de XOR. Cette fonction est centrale dans l'étude des circuits booléens. Le résultat est parfois appelé bit de parité. La fonction parité un exemple de fonction qui n'est pas dans la classe de complexité nommée AC0. Ceci a été démontré par Furst, Saxe et Sipser, et indépendamment à Miklós Ajtai. C
Terme (logique)
Un terme est une expression de base du calcul des prédicats, de l'algèbre, notamment de l'algèbre universelle, et du calcul formel, des systèmes de réécriture et de l'unification. C'est l'objet produit par une analyse syntaxique. Sa principale caractéristique est d'être homogène (il n'y a que des opérations de base et pas d'opérations logiques) et de décrire l'agencement des opérations de base. Un terme est parfois appelé une formule du premier ordre.
Affine logic
Affine logic is a substructural logic whose proof theory rejects the structural rule of contraction. It can also be characterized as linear logic with weakening. The name "affine logic" is associated with linear logic, to which it differs by allowing the weakening rule. Jean-Yves Girard introduced the name as part of the geometry of interaction semantics of linear logic, which characterizes linear logic in terms of linear algebra; here he alludes to affine transformations on vector spaces. Affine logic predated linear logic.
Logiques sous-structurelles
Les logiques sous-structurelles sont des logiques mathématiques où certaines règles d'inférence ne sont pas utilisées ou ont une utilisation restreinte. En particulier, par rapport à la logique classique ou à la logique intuitionniste, il leur manque la règle de contraction qui dit peu ou prou que si on peut faire un raisonnement avec une même hypothèse invoquée deux fois, on peut faire le même raisonnement sans dupliquer cette hypothèse et la règle d'affaiblissement qui permet d'éliminer de l'ensemble des hypothèses une hypothèse inutilisée dans le raisonnement.
Système de Thue
En informatique théorique et en logique mathématique, un système de semi-Thue ou sa version symétrique, un système de Thue, est un système de réécriture de chaînes de caractères ou mots, appelé ainsi d'après son inventeur, le mathématicien norvégien Axel Thue. Contrairement aux grammaires formelles, un tel système ne distingue pas entre symboles terminaux et non terminaux, et ne possède pas d'axiome. Un système de semi-Thue est donné par une relation binaire finie fixe entre mots sur un alphabet donné, dont les éléments sont appelés les règles de réécriture, et notées .