Teoría de la concatenación - Enciclopedia

La teoría de la concatenación, también conocida como teoría de las cadenas, teoría del carácter-cadena o sintaxis teórica, estudia las cadenas de caracteres sobre alfabetos finitos de caracteres, signos, símbolos o marcas. La teoría de las cadenas 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. Una gramática generativa puede considerarse como una definición recursiva en la teoría de las cadenas.

La operación más básica sobre las cadenas es la concatenación; conectar dos cadenas para formar una cadena más larga cuyas 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 que recuerdan a la adición de enteros; en la matemática moderna, este sistema se llama monoides libres.

En 1956, Alonzo Church escribió: "Como cualquier rama de las matemáticas, la sintaxis teórica puede y, en última instancia, debe estudiarse mediante el método axiomatizado". Church obviamente no estaba al tanto de que la teoría de las cadenas ya tenía dos axiomatizaciones desde los años 1930: una de Hans Hermes y otra de Alfred Tarski. Coincidencialmente, la primera presentación en inglés de las bases axiomáticas de la teoría de las cadenas de Tarski de 1933 apareció en 1956 – el mismo año en que Church llamó a tales axiomatizaciones. Como Tarski mismo señaló utilizando otra terminología, surgen dificultades serias si las cadenas se interpretan como tokens en lugar de como tipos en el sentido de la distinción tipo-token de Peirce.


Referencias