<?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-22T10:10:19Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/117613" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/117613</identifier><datestamp>2026-05-15T17:53:41Z</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">Ong, Shawn</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="chair" lang="en_US">Kozen, Dexter</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Halpern, Joseph</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Bindel, David</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2025-08-21T14:14:02Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2025-08-21T14:14:02Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2025-05</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Submission ID: 14936</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Publication ID: 31999427</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/117613</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="doi">https://doi.org/10.7298/1bxz-wj13</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">16938288</dim:field>
   <dim:field mdschema="dc" element="description" lang="en_US">157 pages</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">In order to reason about the capabilities and limitations of a specific com-puting model or programming language, a formal system that can model the behavior of a computational device is required. Once such a correspondence is established, we have access to tools to reason about the performed computation from both denotational and operational viewpoints: for example, the equational theory may be axiomatized, and we can classify the computations which can be carried out by the corresponding model of computation. Even in otherwise lim- ited models of computation, the combination of probability and nondetermin- ism in state-based systems is a particularly challenging problem, chiefly due to the provable lack of a distributive law between the powerset and Giry monads. This thesis focuses on the theory of a version of probabilistic Kleene al- gebra with angelic nondeterminism and the corresponding class of automata. This approach implements semantics via distributions over multisets in order to overcome the theoretical barriers arising from the absence of a distributive law. Chapter 3 introduces the model and establishes a correspondence between the expression and automaton models by proving a Kleene theorem. Such a theorem demonstrates that the two models of computation are equivalent and is the first instance of such a theorem for models including both probability and nondeterminism. This chapter also explore the coalgebraic theory, as well as demonstrating both operational and denotational semantics, in addition to some equational reasoning principles. In Chapter 4 of this thesis, we further extend this theory by investigating the significant decision problems related to this model of computation. In particular, we provide a decision procedure for language equivalence and an algorithm for determining whether a relation is a bisimulation. These algorithms both build off of a novel correspondence be- tween distributions over multisets and formal power series, which allows us to leverage results from polynomial algebra.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="rights" lang="*">Attribution 4.0 International</dim:field>
   <dim:field mdschema="dc" element="rights" qualifier="uri" lang="*">https://creativecommons.org/licenses/by/4.0/</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Automata Theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Formal Languages</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Kleene Theorem</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Nondeterminism</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Probability</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Theory of Computation</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">A Kleene Theorem and Decision Problems for Probability and Angelic Nondeterminism</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="relation" qualifier="localuri">https://newcatalog.library.cornell.edu/catalog/16938288</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="discipline">Applied Mathematics</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., Applied Mathematics</dim:field>
   <dim:field mdschema="dcterms" element="license">https://hdl.handle.net/1813/59810.2</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">Ong, Shawn</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="c18f15a6-0d92-4b1c-b4c1-722678b97435">
	&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&lt;/Language>
   	&lt;Title>A Kleene Theorem and Decision Problems for Probability and Angelic Nondeterminism&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2025-05&lt;/PublicationDate>
   	&lt;DOI>https://doi.org/10.7298/1bxz-wj13&lt;/DOI>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Ong, Shawn&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;License>https://creativecommons.org/licenses/by/4.0/&lt;/License>
    &lt;Keyword>Automata Theory&lt;/Keyword>
    &lt;Keyword>Formal Languages&lt;/Keyword>
    &lt;Keyword>Kleene Theorem&lt;/Keyword>
    &lt;Keyword>Nondeterminism&lt;/Keyword>
    &lt;Keyword>Probability&lt;/Keyword>
    &lt;Keyword>Theory of Computation&lt;/Keyword>
   	&lt;Abstract>In order to reason about the capabilities and limitations of a specific com-puting model or programming language, a formal system that can model the behavior of a computational device is required. Once such a correspondence is established, we have access to tools to reason about the performed computation from both denotational and operational viewpoints: for example, the equational theory may be axiomatized, and we can classify the computations which can be carried out by the corresponding model of computation. Even in otherwise lim- ited models of computation, the combination of probability and nondetermin- ism in state-based systems is a particularly challenging problem, chiefly due to the provable lack of a distributive law between the powerset and Giry monads. This thesis focuses on the theory of a version of probabilistic Kleene al- gebra with angelic nondeterminism and the corresponding class of automata. This approach implements semantics via distributions over multisets in order to overcome the theoretical barriers arising from the absence of a distributive law. Chapter 3 introduces the model and establishes a correspondence between the expression and automaton models by proving a Kleene theorem. Such a theorem demonstrates that the two models of computation are equivalent and is the first instance of such a theorem for models including both probability and nondeterminism. This chapter also explore the coalgebraic theory, as well as demonstrating both operational and denotational semantics, in addition to some equational reasoning principles. In Chapter 4 of this thesis, we further extend this theory by investigating the significant decision problems related to this model of computation. In particular, we provide a decision procedure for language equivalence and an algorithm for determining whether a relation is a bisimulation. These algorithms both build off of a novel correspondence be- tween distributions over multisets and formal power series, which allows us to leverage results from polynomial algebra.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>