<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T08:31:52Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/40960" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/40960</identifier><datestamp>2026-05-14T13:56:01Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Mamouras, Konstantinos</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="chair">Kozen,Dexter Campbell</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember">Constable,Robert Lee</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember">Shore,Richard A</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2015-10-15T18:01:37Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2020-08-17T06:01:01Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2015-08-17</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/40960</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">9255232</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract">Kleene algebra (KA) is an algebraic system that captures completely the laws of equivalence for regular expressions. It is also useful for reasoning about a multitude of computationally interesting structures. Of central interest in KA is a "star" operation that typically describes some kind of repetition or iteration. A combination of Kleene algebra with Boolean algebra has been proposed under the name of Kleene algebra with tests (KAT). This logical system can model the conventional programming constructs of imperative iterative programs, e.g. while loops and conditionals, and it has proven useful for various program verification tasks. In this dissertation we investigate variations and extensions of KA and KAT that are useful for program verification and for reasoning about mathematical structures that appear in computer science. At a technical level, we are interested in establishing completeness theorems, which assert that a proposed logical system is strong enough to capture all properties that are true in a mathematical structure or in a class of mathematical structures. Such results assure us of the quality of a logical system, and their proof often (certainly for the systems that we study here) reveals a systematic way of creating proof objects that certify properties of interest. The first part of this thesis explores generic extensions of KA and KAT with extra equational assumptions. Such extensions are meant to capture in the context of program verification some crucial properties of the domain of computation.  We present a very general completeness meta-theorem that instantiates into several useful concrete completeness results. The second part focuses on extensions of KAT with extra mutable state that enable many useful semantics-preserving program transformations. The transformations we intend to cover are motivated by classical examples from the area of program schematology. We offer a rigorous and mathematically appealing algebraic approach, which replaces the typical combinatorial arguments about flowchart schemes with equational reasoning. Finally, a typed variation of KA is investigated that intends to capture properties of mathematical structures that appear in domain theory. The main result is that our proposed typed KA with products is strong enough to establish all the abstract properties of parametric fixpoints in the standard semantic model CPO, which is the category of [omega]-CPOs and [omega]-continuous maps.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en_US</dim:field>
   <dim:field mdschema="dc" element="subject">Kleene algebra</dim:field>
   <dim:field mdschema="dc" element="subject">program verification</dim:field>
   <dim:field mdschema="dc" element="subject">completeness</dim:field>
   <dim:field mdschema="dc" element="title">Extensions Of Kleene Algebra For Program Verification</dim:field>
   <dim:field mdschema="dc" element="type">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="discipline">Computer Science</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="grantor">Cornell University</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="level">Doctor of Philosophy</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="name">Ph. D., Computer Science</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">Mamouras, Konstantinos</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="b7e66b63-43ee-4d3c-9112-9cb258b64720">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en_US&lt;/Language>
   	&lt;Title>Extensions Of Kleene Algebra For Program Verification&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2015-08-17&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Mamouras, Konstantinos&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>Kleene algebra&lt;/Keyword>
    &lt;Keyword>program verification&lt;/Keyword>
    &lt;Keyword>completeness&lt;/Keyword>
   	&lt;Abstract>Kleene algebra (KA) is an algebraic system that captures completely the laws of equivalence for regular expressions. It is also useful for reasoning about a multitude of computationally interesting structures. Of central interest in KA is a &amp;quot;star&amp;quot; operation that typically describes some kind of repetition or iteration. A combination of Kleene algebra with Boolean algebra has been proposed under the name of Kleene algebra with tests (KAT). This logical system can model the conventional programming constructs of imperative iterative programs, e.g. while loops and conditionals, and it has proven useful for various program verification tasks. In this dissertation we investigate variations and extensions of KA and KAT that are useful for program verification and for reasoning about mathematical structures that appear in computer science. At a technical level, we are interested in establishing completeness theorems, which assert that a proposed logical system is strong enough to capture all properties that are true in a mathematical structure or in a class of mathematical structures. Such results assure us of the quality of a logical system, and their proof often (certainly for the systems that we study here) reveals a systematic way of creating proof objects that certify properties of interest. The first part of this thesis explores generic extensions of KA and KAT with extra equational assumptions. Such extensions are meant to capture in the context of program verification some crucial properties of the domain of computation.  We present a very general completeness meta-theorem that instantiates into several useful concrete completeness results. The second part focuses on extensions of KAT with extra mutable state that enable many useful semantics-preserving program transformations. The transformations we intend to cover are motivated by classical examples from the area of program schematology. We offer a rigorous and mathematically appealing algebraic approach, which replaces the typical combinatorial arguments about flowchart schemes with equational reasoning. Finally, a typed variation of KA is investigated that intends to capture properties of mathematical structures that appear in domain theory. The main result is that our proposed typed KA with products is strong enough to establish all the abstract properties of parametric fixpoints in the standard semantic model CPO, which is the category of [omega]-CPOs and [omega]-continuous maps.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>