Back to search

Clemson University

A Well-Designed, Tree-Based, Generic Map Component to Challenge the Progress towards Automated Verification

Abstract

dc:description.abstract

This thesis presents a non-trivial candidate software component assembly that presents an opportunity and a challenge to the progress towards automated verification. It presents an opportunity because the data abstraction implementation can serve as a proof of concept of the idea that well-designed and well-annotated software components with mathematical specifications and well-engineered implementation(s) lead to generated verification conditions (VCs) of correctness that are "obvious" to prove. It presents a challenge because verification of the implementation involves multiple theories and the use of a tree concept that is based on a general tree theory for which there are no special-purpose solvers. The thesis contains a specification for a conceptualization of a tree with a position that makes it easy to explore and navigate a tree even as it avoids any explicit references to simplify reasoning. The thesis also contains concept enhancements for trees and an implementation layered using trees for a data abstraction for searching (a version of maps). A key contribution is the development of the implementation so that it is amenable for verification with internal assertions such as representation invariants and abstraction relations, operation specifications, loop invariants, and progress metrics, all of which involve the general tree theory.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mbwambo, Nicodemus M.J.
Contributors dc:contributor
  • Dr. Murali Sitaraman, Committee Chair
  • Dr. Brian Dean
  • Dr. Feng Luo

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/2657

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Mbwambo, Nicodemus M.J.. A Well-Designed, Tree-Based, Generic Map Component to Challenge the Progress towards Automated Verification. Thesis thesis, https://open.clemson.edu/all_theses/2657