Vi beskriver en familj av beslutsförfaranden som utvidgar beslutsförfarandet för kvantifierfria begränsningar för rekursiva algebraiska datatyper (term algebras) för att stödja rekursiva abstraktionsfunktioner. Våra abstraktion funktioner är katamorfismer (term algebra homomorphisms) kartläggning algebraic data typ värden in i värden i andra decledable teorier (t.ex. set, multiset, listor, heltal, booleaner). Varje instans av vår beslutsförfarande familj är sund; vi identifierar en brett tillämplig många-till-ett villkor på abstraktion funktioner som innebär fullständighet. Fullständiga fall av vårt beslut förfarande inkluderar följande korrekthet uttalanden: 1) en funktionell datastruktur genomförande uppfyller en rekursivt specificerad invariant, 2) sådan datastruktur överensstämmer med ett kontrakt som ges i form av uppsättningar, multiset, listor, storlekar, eller höjder, 3) en omvandling av en formel (eller lambda term) abstrakt syntax träd ändrar uppsättningen av fria variabler på det angivna sättet.
Suter m.fl. REF beskriver beslutsförfaranden för teorin om algebraiska datatyper som utvidgas med abstraktionsfunktioner till decidable abstrakta domäner.
Decision procedures for algebraic data types with abstractions
{'venue': "POPL '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}