Abstrakt. Vi beskriver en algoritm för att bestämma den första ordningen multisorterade teorin BAPA, som kombinerar 1) Booleska algebras av uppsättningar av otolkade element (BA) och 2) Presburger aritmetiska operationer (PA). BAPA kan uttrycka förhållandet mellan heltalsvariabler och kardinaliteter av en priori obundet finita uppsättningar, och stöder godtycklig kvantifiering över uppsättningar och heltal. Vår motivation för BAPA är att bestämma verifieringsförhållanden som uppstår i den statiska analysen av datastrukturkonsistensegenskaper. Datastrukturer använder ofta ett heltalsvariabel för att hålla reda på antalet element de lagrar; en invariant av en sådan datastruktur är att värdet av heltalsvariabeln är lika med antalet element som lagras i datastrukturen. När innehållet i datastrukturen representeras av en uppsättning kan de resulterande begränsningarna fångas upp i BAPA. BAPA-formler med kvantifier-alternationer uppstår vid verifiering av program med annoteringar som innehåller kvantifieringar, eller vid bevis på simuleringsförhållandeförhållanden för förfining och likvärdighet av programfragment. Dessutom kan BAPA begränsningar användas för att bevisa avslutandet av program som manipulerar datastrukturer, och har applikationer i begränsningar databaser. Vi ger en formell beskrivning av ett beslutsförfarande för BAPA, vilket innebär att BAPA kan fatta beslut. Vi analyserar vår algoritm och får en elementär övre gräns på körtiden, vilket ger den första komplexiteten bunden till BAPA. Eftersom det fungerar genom en minskning till PA, vår algoritm ger decidable av en kombination av uppsättningar av otolkade element med någon decidable förlängning av PA. Vår algoritm kan också användas för att ge en optimal beslutsförfarande för BA genom en minskning till PA med avgränsade kvantifiers. Vi har implementerat vår algoritm och använt den för att skriva ut verifieringsvillkor i Jahob-systemet för datastrukturkonsistenskontroll av Java-program; vår erfarenhet av algoritmen är lovande.
Kuncak, etc. ge ett beslutsförfarande för ett kvantifierat språk av uppsättningar otolkade element med kardinalitetsbegränsningar REF.
An algorithm for deciding BAPA: Boolean Algebra with Presburger Arithmetic
{'venue': 'In 20th International Conference on Automated Deduction, CADE-20', 'journal': None, 'mag_field_of_study': ['Computer Science']}