Abstrakt. Separation Logic är en allmänt använd formalism för att beskriva dynamiskt fördelade länkade datastrukturer, såsom listor, träd, etc. Decidability status för olika fragment av logiken utgör ett långvarigt öppet problem. Aktuell resultatrapport om tekniker för att bestämma tillfredsställande och validitet för indicier för separation Logik(er) över listor (eventuellt med data). I detta dokument fastställer vi ett mer allmänt beslutsunderlag. Vi bevisar att varje separation Logic formel som använder ganska allmänt rekursivt definierade predikat är decidable för tillfredställelse, och dessutom innebär mellan sådana formler är decidedable för giltighet. Dessa predikat är allmänna nog att definiera (dubbelt) länkade listor, träd och strukturer mer allmänna än träd, såsom träd vars blad är kedjade i en lista. Decredability proofs är genom reduktion till decidability av Monadic Second Order Logic på grafer med avgränsad trädbredd.
REF minskar dock implicit problem till MSO på grafer med en avgränsad trädbredd, vilket resulterar i en multiplikator-exponentiell komplexitet.
The Tree Width of Separation Logic with Recursive Definitions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}