{"id":{"repo_id":"vilnius","oai_identifier":"oai:vu.lt:elaba:308337866"},"canonical_url":"https://search.ndltd.org/etd/vilnius/oai:vu.lt:elaba:308337866","repository":{"repo_id":"vilnius","name":"Vilnius University","base_url":"https://epublications.vu.lt/oai"},"display":{"title":"Funkcinių kairėn pasvirusių raudonai-juodų medžių automatizuotas formalus verifikavimas Dafny aplinkoje /","abstract":"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&#241;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.","abstract_html":"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&#x27;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&#x27;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&#x27;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&#x27;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&amp;#241;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.","abstract_has_math":false,"creators":["Praninskas, Džiugas,"],"institution":"Institutional Repository of Vilnius University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-19T10:12:59Z","subjects":[],"languages":["lit"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://repository.vu.lt/VU:ELABAETD308337866&prefLang=en_US","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://repository.vu.lt/VU:ELABAETD308337866&prefLang=en_US","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":"open","embargo_until":null,"access_note":null},"source_record":{"url":"https://epublications.vu.lt/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Avu.lt%3Aelaba%3A308337866","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Praninskas, Džiugas,"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2026"]},{"key":"dc:publisher","label":"Institution","values":["Institutional Repository of Vilnius University"]},{"key":"dc:relation","label":"Dc Relation","values":["https://epublications.vu.lt/object/elaba:308337866/308337866.pdf"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/bachelorThesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["lit"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://repository.vu.lt/VU:ELABAETD308337866&prefLang=en_US"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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&#241;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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Funkcinių kairėn pasvirusių raudonai-juodų medžių automatizuotas formalus verifikavimas Dafny aplinkoje /","Automated formal verification of functional left-leaning red-black trees in the dafny framework."]}]}],"canonical_facts":{"dc:creator":["Praninskas, Džiugas,"],"dc:date":["2026"],"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&#241;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."],"dc:format":["application/pdf"],"dc:identifier":["https://repository.vu.lt/VU:ELABAETD308337866&prefLang=en_US"],"dc:language":["lit"],"dc:publisher":["Institutional Repository of Vilnius University"],"dc:relation":["https://epublications.vu.lt/object/elaba:308337866/308337866.pdf"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:title":["Funkcinių kairėn pasvirusių raudonai-juodų medžių automatizuotas formalus verifikavimas Dafny aplinkoje /","Automated formal verification of functional left-leaning red-black trees in the dafny framework."],"dc:type":["info:eu-repo/semantics/bachelorThesis"]},"updated_at":"2026-11-19T10:12:59Z"}