Théorie de la concaténation - Concatenation theory
La théorie de Concaténation , aussi appelée la théorie des cordes , la théorie chaîne de caractères , ou théorique syntaxe , les études des chaînes de caractères sur un alphabet fini de caractères, des signes, des symboles ou des marques. La théorie des cordes est fondamentale pour la linguistique formelle , l'informatique, la logique et la métamathématique, en particulier la théorie de la preuve. Une grammaire générative peut être vue comme une définition récursive en théorie des cordes.
L'opération la plus basique sur les chaînes est la concaténation ; connectez deux chaînes pour former une chaîne plus longue dont la longueur est la somme des longueurs de ces deux chaînes. ABCDE est la concaténation de AB avec CDE, en symboles ABCDE = AB ^ CDE. Les chaînes et la concaténation de chaînes peuvent être traitées comme un système algébrique avec certaines propriétés ressemblant à celles de l'addition d'entiers; en mathématiques modernes, ce système est appelé un monoïde libre .
En 1956, Alonzo Church écrivait: "Comme toute branche des mathématiques, la syntaxe théorique peut, et doit finalement, être étudiée par la méthode axiomatique". Church ignorait manifestement que la théorie des cordes avait déjà deux axiomatisations des années 1930: l'une de Hans Hermes et l'autre d' Alfred Tarski . Par coïncidence, la première présentation anglaise des fondements axiomatiques de Tarski en 1933 sur la théorie des cordes est apparue en 1956 - la même année où Church a appelé à de telles axiomatisations. Comme Tarski l'a lui-même noté en utilisant une autre terminologie, de sérieuses difficultés surviennent si les chaînes sont interprétées comme des jetons plutôt que comme des types au sens de la distinction type-jeton de Pierce , à ne pas confondre avec des distinctions similaires sous - jacentes à d'autres distinctions de type-jeton .