Vi tar itu med problemet med att bevisa den totala korrektheten i omvandlingar av bestämda logiska program. Vi anser att en allmän omvandlingsregel, kallad klausulersättning, som består i att omvandla ett program P till ett nytt program Q genom att ersätta en uppsättning 1 av klausuler som förekommer i P med en ny uppsättning 2 av klausuler, förutsatt att 1 och 2 är likvärdiga i minst Herbrand modell M(P ) av programmet P. Vi föreslår en allmän metod för att bevisa att transformationer baserade på klausulersättning är helt korrekta, det vill säga M(P ) = M(Q ). Vår metod består i att visa att omvandlingen av P till Q kan utföras genom: (i) lägga till extra argument till predikat, vilket härrör från det givna programmet P en kommenterad program P, (ii) tillämpa en variant av klausulersättningsregeln och omvandla den kommenterade programmet P till en avslutande kommenterade program Q, och (iii) radering av kommentarer från Q, därigenom få Q. Vår metod kräver inte att varken P eller Q slutar och den är parametrisk med avseende på annoteringarna. Genom att tillhandahålla olika annoteringar kan vi enkelt bevisa den totala korrektheten i programomvandlingar baserade på olika versioner av den populära veckling, vikning och målersättningsregler, som alla kan ses som särskilda fall av vår klausulersättning regel.
Bevisen för de resultat som presenteras i denna rapport är baserade på teorin om välgrundade kommentarer, vilket är en allmän teori för att bevisa riktigheten av programomvandlingar REF.
Totally correct logic program transformations via well-founded annotations
{'venue': None, 'journal': 'Higher-Order and Symbolic Computation', 'mag_field_of_study': ['Computer Science']}