Komplementationsbaserade

Komplementationsbaserade är ett arbetsbegrepp som används inom flera teoretiska och tillämpade områden för att lösa problem genom att använda komplementet av en uppsättning, egenskap eller språk. Metoden bygger på dualitet och ofta på De Morgans lagar: genom att analysera vad som inte gäller (komplementet) får man ofta en bättre eller mer hanterbar bild av problemet och kan använda befintliga algoritmer för att hantera problemet i den komplementära formen.

Användningsområden och syfte

Inom formell verifiering, automatteori och logik används komplementationsbaserade tekniker ofta för att omvandla innehålls- eller nåbarhetsproblem till jämförbara eller enklare tomhetsproblem. Till exempel kan frågan om ett språk A är en delmängd av ett språk B undersökas genom att undersöka om snittet av A och komplementet till B är tomt. Liknande principer används i modellkontroll, där det kan vara fördelaktigt att negatera en specifikation eller egenskap och därefter undersöka kombinationen av systemmodell och den negativa egenskapen.

Metod och arbetssätt

I praktiken innebär komplementationsbaserade metoder ofta konstruktion av automatoner eller logiska representationer som accepterar komplementet av ett givet objekt, följt av en tomhets- eller innehållsbetraktning i en sammansatt struktur (t.ex. en produkt av automatoner). Resultatet används sedan för att dra slutsatser om originalproblemet. Tekniken kräver ofta noggrann hantering av komplexitet, eftersom komplettering kan leda till explosionsimport i storlek, särskilt inom automata- eller logikkontexter.

Relation till andra metoder

Komplementationsbaserade metoder är nära relaterade till duala problem och att använda negation som mellanled. De står i kontrast till rakt framskrivna eller konstruktiva metoder och används ofta när direkta metoder är svåra eller när befintliga verktyg är bättre lämpade för konkurrerande format som tomhets- eller innehållsbestämningar.

Se även

Komplement, dualitet, automatteori, modellkontroll, satslogik.