Institutional Repository of Vilnius University
Funkcinių kairėn pasvirusių raudonai-juodų medžių automatizuotas formalus verifikavimas Dafny aplinkoje /
Abstract
dc:descriptionAutomated Formal Verification of Functional Left-Leaning Red-Black Trees in the Dafny framework This thesis presents a formal verification of a functional implementation of the 2-3 variant of Sedgewick's left-leaning red-black tree (LLRB) using the Dafny programming language and its underlying Z3 SMT solver. The work is structured in two tiers. The first tier establishes a fully verified implementation of search and insertion: all five structural invariants (binary search tree ordering, no-red-red, equal black-height, left-leaning, and black root) are proved to be preserved by the insertion operation, and the operation's functional semantics — that the resulting tree represents the original map updated with the new key-value pair — is established as a Hoare-style postcondition. The verification required twenty lemmas, three levels of weakened invariants for the recursive helper, and explicit use of Dafny's {:opaque} and {:isolate_assertions} attributes for solver resource management. The second tier attempts deletion. Where the verification did not succeed, the failures are categorized into three distinct modes: structural invariant propagation through composite transformations, intermediate invariant design for the descent state, and termination through non-trivial transformations. The first two are shown to reflect architectural limits of SMT-backed verification; the third was solved during the work by introducing a treeSize measure function. A central empirical observation emerges from the combined experience: aggregate properties (key sets, value maps, black-height) are automatically preserved by the solver across structural rearrangements, while structural properties (BST ordering, color invariants) are not. This boundary characterizes Dafny's suitability profile for recursive data structure verification. Comparisons with prior work in Isabelle/HOL and Coq, and with an earlier Dafny LLRB verification by Peña (2020), confirm that the additional manual proof effort on the Dafny side reflects structural overhead in quantifier instantiation and lemma infrastructure rather than intrinsic algorithmic complexity.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Praninskas, Džiugas,
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD308337866&prefLang=en_US