Abstrakt. Vi definierar en ny decibel logik för att uttrycka och kontrollera invarianter av program som manipulerar dynamiskt fördelade objekt via pekare och destruktiva pekaruppdateringar. Huvuddragen i denna logik är förmågan att begränsa grannskapet av en nod som kan nås via ett reguljärt uttryck från en utsedd nod. Logiken är stängd under booleska operationer (närmare bestämt, negation) och har en ändlig modellegendom. Det viktigaste tekniska resultatet är beviset på beslutbarhet. Vi visar hur man uttrycker förutsättningar, postvillkor och loopinvarianter för några intressanta program. Det är också möjligt att uttrycka egenskaper som uppdelning av datastrukturer och mutationer på låg nivå. Dessutom kan vår logik uttrycka egenskaper hos godtyckliga datastrukturer och ett godtyckligt antal pekarfält. Det senare ger ett sätt att naturligt ange postvillkor som relaterar fälten vid inträde till ett förfarande till fälten vid utträde. Därför är det möjligt att använda logiken för att automatiskt bevisa partiell korrekthet av program som utför högmutationer på låg nivå.
LRP REF är fullt decidable över flera länkade datastrukturer och har en ändlig modell egenskap.
A Logic of Reachable Patterns in Linked Data-Structures
{'venue': 'Foundations of Software Science and Computation Structures (29/03/2006) p. 94-110', 'journal': None, 'mag_field_of_study': ['Computer Science']}