Strutture Applicative Parziali e Algebre Combinatorie Parziali: proprietà insiemistiche e categoriali

Una struttura applicativa parziale, o “sap”, è una semplice struttura matematica formata da un insieme e da un'operazione binaria parziale su di esso. Usualmente ogni elemento appartenente a una sap viene interpretato come un algoritmo, e l'operazione corrisponde all'esecuzione di un algoritmo sull'input costituito da un altro algoritmo. Le algebre combinatorie parziali, o “acp”, sono particolari sap che godono di una proprietà chiamata completezza combinatoria, secondo cui, per ogni possibile modo di combinare diversi algoritmi fra loro, esiste un algoritmo che organizza secondo tale schema gli algoritmi che gli vengono forniti come input. Questa tesi studia le proprietà fondamentali delle sap e delle acp, concentrandosi in particolare su due aspetti: la struttura interna delle acp e i limiti, colimiti ed esponenziali nelle categorie Sap e Acp.