Abstrakt. Motiverade av ansökningar till programverifiering, studerar vi ett beslutsförfarande för tillfredsställelse i ett uttrycksfullt fragment av en teori av matriser, som parameteriseras av teorierna av matriselementen. Beslutsförfarandet minskar tillfredsställelsen av en formel av fragmentet till tillfredsställande av en likformig kvantifier-fri formel i den kombinerade teorin om jämlikhet med otolkade funktioner (EUF), Presburger aritmetik, och elementteorier. Detta fragment tillåter en begränsad användning av universell kvantifiering, så att en kvantifier alternation tillåts, med vissa syntaktiska begränsningar. Det gör det möjligt att till exempel uttrycka att ett påstående innehåller för alla element i ett visst indexintervall, att två matriser är lika i ett givet intervall, eller att en matris sorteras. Vi demonstrerar dess uttrycksfullhet genom tillämpningar för verifiering av sorteringsalgoritmer och parameteriserade system. Vi bevisar också att tillfredsställande är obeslutsamt för flera naturliga förlängningar till fragmentet. Slutligen beskriver vi vårt genomförande i πVC verifiera kompilatorn.
I REF presenteras i synnerhet ett tillfredsställande beslutsförfarande för ett decibelt fragment av en teori om matriser.
What’s decidable about arrays
{'venue': 'In Proc. VMCAI, LNCS 3855', 'journal': None, 'mag_field_of_study': ['Computer Science']}