Bakalářská práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Tuned Sifting in CUDD for Satisfiability Solving

Jakub Szymsza
Anotace

Q3B je SMT solver používající binární rozhodovací diagramy (BDDs). Nedávno vyvinutá verze tohoto nástroje pracuje nad parciálními BDDs. Pro dynamické zmenšení diagramů používá Q3B techniku siftingu. Vedle popsání teoretických základů binárních rozhodovacích diagramů a SMT solvingu tato práce představuje opravu sifting algoritmu pro parciální BDDs v knihovně CUDD. Dále je vyhodnocen vliv různých nastavení …více

Abstract

Q3B is an SMT solver using binary decision diagrams (BDDs). A recently developed version of the tool works with partial BDDs. Q3B uses sifting as a technique to dynamically reduce the BDD size. Besides describing the theoretical basis of BDDs and SMT solving, this thesis presents the adjustment of the sifting algorithm in the CUDD library to properly work with partial BDDs. Further, it evaluates the …více

Zadání práce
Binary decision diagram (BDD) is a successful data structure for storing a set of bitvectors of a given length. The size of this structure depends on the ordering of stored bits. Sifting is a technique for automatic modification of this ordering that can reduce the BDD size. The goal of the thesis is to present current sifting techniques for BDDs, describe the current implementation of sifting in the library CUDD, adopt this implementation to partial BDDs, extend the sifting in CUDD with the possibility to specify the order of some pairs of bits in all considered orderings, and experimentally evaluate the effect of various sifting settings on the performance of the SMT solver Q3B and its version based on partial BDDs.
Práce zkontrolována:
19. 5. 2023 18:02, prof. RNDr. Jan Strejček, Ph.D., učo 3366
Jazyk práce
angličtina angličtina
Termín obhajoby
28. 6. 2023
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Jan Strejček, Ph.D., učo 3366
KTP FI MU

Oponent

RNDr. Nikola Beneš, Ph.D., učo 72525
KPSK FI MU

Konzultant

RNDr. Martin Jonáš, Ph.D., učo 359542
KTP FI MU

Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Informatika
  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.
  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.
  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.
  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.
  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.