Abstrakt. 2004 introducerade Berdine, Calcagno och O'Hearn ett fragment av separationslogik som möjliggör resonemang om program med pekare och länkade listor. De visade att införandet i detta fragment är i coNP, men den exakta komplexiteten i detta problem har varit öppen sedan dess. I detta dokument visar vi att problemet faktiskt kan lösas i polynom tid. I detta syfte representerar vi separationslogiska formler som grafer och visar att varje tillfredsställande formel är likvärdig med en vars graf är i en viss normal form. Detaljering mellan två sådana formler minskar sedan till en graf homomorfism problem. Vi diskuterar också naturliga syntaktiska förlängningar som gör det ointressant.
Nyligen har implementationsproblemet för SLRD över listor reducerats till graf homomorfism i REF, och kan lösas i PTIME.
Tractable reasoning in a fragment of separation logic
{'venue': 'In 22nd CONCUR, Springer LNCS 6901', 'journal': None, 'mag_field_of_study': ['Computer Science']}