Back to search

Institutional Repository of Vilnius University

Funkcinių kairėn pasvirusių raudonai-juodų medžių automatizuotas formalus verifikavimas Dafny aplinkoje /

Abstract

dc:description

Automated 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.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Praninskas, Džiugas,. Funkcinių kairėn pasvirusių raudonai-juodų medžių automatizuotas formalus verifikavimas Dafny aplinkoje /. Institutional Repository of Vilnius University, 2026. https://repository.vu.lt/VU:ELABAETD308337866&prefLang=en_US