teoria concatenação - Concatenation theory
Teoria concatenação , também chamada teoria das cordas , teoria do caráter cordas , ou teórica sintaxe , estuda cadeias de caracteres mais de alfabetos finitos de caracteres, sinais, símbolos ou marcas. A teoria das cordas é fundamental para a lingüística formais, ciência da computação, lógica e metamathematics teoria especialmente prova. A gramática gerativa pode ser visto como uma definição recursiva na teoria das cordas.
A operação mais básica em cordas é concatenação ; conectar duas cordas para formar uma cadeia mais longa, cujo comprimento é a soma dos comprimentos dessas duas cordas. ABCDE é a concatenação de AB com CDE, em símbolos ABCDE = AB ^ CDE. Cordas, e concatenação de cordas pode ser tratada como um sistema algébrico com algumas propriedades que se assemelham às da adição de números inteiros; na matemática moderna, este sistema é chamado de monoid livre .
Em 1956 Alonzo Church escreveu: "Como qualquer ramo da matemática, sintaxe teórica pode, e, finalmente, deve, ser estudada pelo método axiomático". Igreja era, evidentemente, sem saber que a teoria das cordas já tinha dois axiomatizações da década de 1930: um por Hans Hermes e um por Alfred Tarski . Coincidentemente, a primeira apresentação Inglês de 1933 bases axiomáticas de Tarski da teoria das cordas apareceu em 1956 - o mesmo ano em que Igreja chamada para tais axiomatizações. Como o próprio Tarski observou usando outra terminologia graves dificuldades surgir se as cordas são interpretadas como fichas em vez de tipos no sentido da distinção tipo token de Pierce , não deve ser confundido com distinções semelhantes subjacentes outras distinções do tipo token .