{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/40960"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/40960","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Extensions Of Kleene Algebra For Program Verification","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.","abstract_html":"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 &quot;star&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.","abstract_has_math":false,"creators":["Mamouras, Konstantinos"],"institution":"Cornell University","degree_name":"Ph. D., Computer Science","degree_level":"Doctor of Philosophy","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":["Kozen,Dexter Campbell"],"committee_members":["Constable,Robert Lee","Shore,Richard A"],"year":2015,"date_issued":"2015-08-17","date_published":"2015-08-17","updated_at":"2026-11-19T03:18:46Z","subjects":["Kleene algebra","program verification","completeness"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["9255232"],"render_values":[{"text":"9255232","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/40960","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/40960","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F40960","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.chair","label":"Chair","values":["Kozen,Dexter Campbell"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Constable,Robert Lee","Shore,Richard A"]},{"key":"dc:creator","label":"Author","values":["Mamouras, Konstantinos"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2015-10-15T18:01:37Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2020-08-17T06:01:01Z"]},{"key":"dc:date.issued","label":"Date","values":["2015-08-17"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Computer Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Kleene algebra","program verification","completeness"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["9255232"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/40960"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"b7e66b63-43ee-4d3c-9112-9cb258b64720\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Extensions Of Kleene Algebra For Program Verification</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2015-08-17</PublicationDate> <Authors> <Author> <DisplayName>Mamouras, Konstantinos</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Kleene algebra</Keyword> <Keyword>program verification</Keyword> <Keyword>completeness</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Mamouras, Konstantinos"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Extensions Of Kleene Algebra For Program Verification"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"b7e66b63-43ee-4d3c-9112-9cb258b64720\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Extensions Of Kleene Algebra For Program Verification</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2015-08-17</PublicationDate> <Authors> <Author> <DisplayName>Mamouras, Konstantinos</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Kleene algebra</Keyword> <Keyword>program verification</Keyword> <Keyword>completeness</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Mamouras, Konstantinos"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:contributor.chair":["Kozen,Dexter Campbell"],"dc:contributor.committeemember":["Constable,Robert Lee","Shore,Richard A"],"dc:creator":["Mamouras, Konstantinos"],"dc:date.accessioned":["2015-10-15T18:01:37Z"],"dc:date.available":["2020-08-17T06:01:01Z"],"dc:date.issued":["2015-08-17"],"dc:description.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."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["9255232"],"dc:identifier.uri":["https://hdl.handle.net/1813/40960"],"dc:language.iso":["en_US"],"dc:subject":["Kleene algebra","program verification","completeness"],"dc:title":["Extensions Of Kleene Algebra For Program Verification"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Computer Science"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-11-19T03:18:46Z"}