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.
I synnerhet Cook et al. REF bevisar att problemet med tillfredsställande/detaljisering kan lösas på polynomtid.
Tractable reasoning in a fragment of separation logic
{'venue': 'In 22nd CONCUR, Springer LNCS 6901', 'journal': None, 'mag_field_of_study': ['Computer Science']}