Verifieringsproblem kräver att resonera i teorier om datastrukturer och fragment av aritmetisk. Därför behövs beslutsförfaranden för sådana teorier, för att vara inbäddad i, eller gränssnitt med, bevis assistenter eller programvara modell kontroller. Sådana beslutsförfaranden bör vara sunda och fullständiga, för att undvika falska negativa och falska positiva, effektiva, för att hantera stora problem, och lätta att kombinera, eftersom de flesta problem omfattar flera teorier. Den omskrivningsbaserade metoden för beslutsförfaranden syftar till att ta itu med dessa ibland motstridiga frågor på ett enhetligt sätt, genom att utnyttja de befogenheter som den allmänna första ordningen har. I denna artikel generaliserar vi det omskrivningsbaserade tillvägagångssättet från att bestämma tillfredsställandet av uppsättningar av jord ordagranna till att besluta om godtyckliga markformler i teorin. Därefter presenterar vi polynomiska rewrite-based satisfiability procedurer för teorier om poster med förlängning och heltal offset. Generaliseringen av den rewrite-baserade metoden för godtyckliga markformler och polynomets tillfredsställande procedur för teorin om poster med extendalitet använder samma nyckel egenskap - benämnd variabel-inaktivitet - som gör att man kan kombinera teorier på ett enkelt sätt i den rewrite-baserade metoden.
Således kan metoden för REF betraktas som en "ren" utvidgning av den omskrivningsbaserade metoden till T-beslutsproblem, i den meningen att allt resonemang görs av en första-order rewrite-baserad bevisare.
On variable-inactivity and polynomial T-satisfiability procedures
{'venue': 'J. Log. Comput.', 'journal': 'J. Log. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}