Meta-analysis of type theories with an application to the design of formal proofs - Petković Komel, Anja (visokošolska dela, 2021)
V doktorski disertaciji predstavimo meta-analizo širokega razreda splošnih teorij tipov. Osredotočimo se na tri vidike: transformacije teorij tipov, dopolnitev teorij tipov in splošen algoritem za preverjanje enakosti. Teorije tipov zagotavljajo matematično osnovo za mnoge dokazovalne pomočnike. Da bi lažje razumeli interakcije med teorijami, študiramo njihove meta-teoretične lastnosti in jih preverjamo z implementacijo fleksibilnega dokazovalnega pomočnika Andromeda 2, ki omogoča, da uporabnik sam poda teorijo tipov. Naša meta-analiza je zgrajena na definiciji končnih teorij tipov. Definiramo sintaktične transformacije teorij tipov in dokažemo, da tvorijo relativno monado za sintakso. Da bi vključili strukturo izpeljivosti nadgradimo definicijo v transformacije teorij tipov, ki pokrije nekatere znane primere, kot sta Curry-Howardova korespondenca in razširitev z definicijo. Nato dokažemo nekaj meta-izrekov o transformacijah. Uporabnost transformacij teorij tipov se pokaže v definiciji dopolnitve. Dokažemo izrek o dopolnitvi, ki pravi, da ima vsaka končna teorija tipov dopolnitev. Na strani implementacije oblikujemo splošen algoritem za preverjanje enakosti, ki ga lahko uporabimo na končnih teorijah tipov. Algoritem je sestavljen iz faze ekstenzionalnosti, kjer uporabljamo pravila ekstenzionalnosti, in faze normalizacije, ki temelji na pravilih za izračun. Obe vrsti pravil sta definirani s pomočjo pogoja objektne obrnljivosti. Podamo tudi zadosten sintaktični kriterij za prepoznavanje teh pravil in algoritem s preprostimi vzorci, ki pravila uporablja. Tretja komponenta algoritma je primeren pojem glavnih argumentov, ki določa normalno obliko. S spreminjanjem glavnih argumentov dobimo znane pojme, kot sta šibka in močna normalna oblika. Dokažemo, da algoritem zadošča izreku skladnosti. Algoritem je implementiran v dokazovalnem pomočniku Andromeda 2.
Keywords: algebraic theory; algebrajska teorija; dependent type theory; Disertacije; dokazovalni pomočnik; dopolnitev teorij tipov; logic; logika; Matematična logika; matematika; mathematics; odvisna teorija tipov; preverjanje enakosti; proof assistant; type-theoretic elaboration equality checking