Abstrakt. Karaktäriseringen av terminering med välgrundade monotona algebror har varit en milstolpe på vägen mot automatiserade termineringstekniker, av vilka vi har sett en omfattande utveckling under de senaste åren. Både den semantiska karakteriseringen och de mest kända termineringsmetoderna handlar om global uppsägning, likformigt av alla villkor i ett terminsomskrivningssystem (TRS). I detta dokument överväger vi lokal uppsägning, av specifika uppsättningar av villkor inom en given TRS. Huvudsyftet med detta dokument är att generalisera den semantiska karakteriseringen av den globala uppsägningen till lokal uppsägning. Detta möjliggörs genom att man erkänner att de välgrundade monotona algebrorna är partiella. Vi utvidgar också vår inställning till lokal relativ uppsägning. Intresset för lokal uppsägning uppstår naturligtvis i programverifiering, där man förmodligen bara är intresserad av förnuftiga ingångar, eller bara vill karakterisera den uppsättning ingångar för vilka ett program avslutas. Lokal uppsägning kommer också att vara av intresse när man hanterar en viss kategori av termer inom en TRS som är känd för att vara icke-avslutande, såsom kombinatorisk logik (CL) eller en TRS-kodning rekursiva programsystem eller Turing maskiner. Vi visar hur vissa av de välkända metoderna för att bevisa global uppsägning, såsom stegvis avskaffande av omskrivningsregler och semantisk märkning, kan anpassas till det lokala fallet. Vi beskriver också omvandlingar som minskar lokala till globala uppsägningsproblem. Den resulterande tekniken för att bevisa lokal uppsägning har i vissa fall redan automatiserats. En av våra ansökningar gäller karakteriseringen av termineringen av S-terminer i CL som reguljärt språk. Tidigare hade detta språk redan hittats genom en tråkig analys av S-termers reduktionsbeteende. Dessa resultat har nu bekräftats av ett fullständigt automatiserat och verifierat bevis.
Lokal uppsägning på vanliga språk, har undersökts i REF.
Local Termination: theory and practice
{'venue': 'LMCS 6 (3:20) 2010', 'journal': None, 'mag_field_of_study': ['Computer Science']}