La teoría de la concatenación , también llamada teoría de cuerdas , teoría de cadenas de caracteres o sintaxis teórica , estudia las cadenas de caracteres sobre alfabetos finitos de caracteres, signos, símbolos o marcas. La teoría de cuerdas es fundamental para la lingüística formal , la informática, la lógica y la metamatemática, especialmente la teoría de la demostración. [1] Una gramática generativa puede verse como una definición recursiva en la teoría de cuerdas.
La operación más básica con cadenas es la concatenación : conectar dos cadenas para formar una cadena más larga cuya longitud sea la suma de las longitudes de esas dos cadenas. ABCDE es la concatenación de AB con CDE, en símbolos ABCDE = AB ^ CDE. Las cadenas y la concatenación de cadenas pueden tratarse como un sistema algebraico con algunas propiedades similares a las de la suma de números enteros; en matemáticas modernas, este sistema se denomina monoide libre .
En 1956, Alonzo Church escribió: "Como cualquier rama de las matemáticas, la sintaxis teórica puede, y en última instancia debe, ser estudiada por el método axiomático". [2] Church evidentemente no sabía que la teoría de cuerdas ya tenía dos axiomatizaciones de la década de 1930: una de Hans Hermes y otra de Alfred Tarski . [3] Casualmente, la primera presentación en inglés de los fundamentos axiomáticos de la teoría de cuerdas de Tarski de 1933 apareció en 1956, el mismo año en que Church pidió tales axiomatizaciones. [4] Como el propio Tarski señaló utilizando otra terminología, surgen serias dificultades si las cadenas se interpretan como tokens en lugar de tipos en el sentido de la distinción tipo-token de Peirce .