Abstrakt. Vi presenterar en allmän ram för att verifiera program med komplexa dynamiska länkade datastrukturer vars korrekthet beror på att beställa relationer mellan lagrade datavärden. Den underliggande formalismen i vårt ramverk är skogsautomata (FA), som tidigare har utvecklats för verifiering av högmanipulerande program. Vi utökar FA genom begränsningar mellan dataelement i samband med noder av högar som representeras av FA, och vi presenterar utökade versioner av alla operationer som behövs för att använda den utvidgade FA i en helt automatiserad verifieringsmetod, baserad på abstrakt tolkning. Vi har implementerat vårt tillvägagångssätt som en förlängning av Forester-verktyget och framgångsrikt tillämpat det på ett antal program som behandlar datastrukturer såsom olika former av ensam- och dubbellänkade listor, binära sökträd, samt hoppa listor.
REF förlänger skogsautomatiken genom begränsningar mellan dataelement i samband med knutpunkterna i högarna.
Verification of Heap Manipulating Programs with Ordered Data by Extended Forest Automata
{'venue': 'ATVA', 'journal': None, 'mag_field_of_study': ['Computer Science']}