<?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-22T11:08:05Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/10820" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/10820</identifier><datestamp>2026-05-13T16:37:03Z</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">Minnes, Mor Mia</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2008-05-16T20:46:28Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2013-05-16T06:21:46Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2008-05-16T20:46:28Z</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/10820</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">6397140</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">Finite state automata are Turing machines with fixed finite bounds on resource use.  Automata lend themselves well to real-time computations and efficient algorithms. Continuing a tradition of studying computability in mathematics, we examine automatic structures, mathematical objects which can be represented by automata, and apply resulting observations to computer science.&#xd;
&#xd;
We measure the complexity of automatic structures via  well-established concepts from model theory, topology, and set theory. We prove the following results. The ordinal height of any automatic well-founded partial order is bounded by \omega^\omega.  The ordinal heights of automatic well-founded relations are unbounded below the first uncomputable ordinal.  For any computable ordinal, there is an automatic structure of Scott rank at least that ordinal.  Moreover, there are automatic structures of Scott rank the first uncomputable ordinal and the successor of the first uncomputable ordinal. For any computable ordinal, there is an automatic successor tree of Cantor-Bendixson rank that ordinal.  &#xd;
&#xd;
Next, we study infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced via such operations have finite degree and can be described by finite automata over a one-letter alphabet. We investigate&#xd;
algorithmic properties of such graphs in terms of their finite presentations. In particular, we ask how hard it is to check whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another, and whether the graph is connected. We give polynomial-time algorithms answering each of these questions. For a fixed input graph, the algorithm for infinite component membership works in constant time and reachability is decided uniformly by a single automaton.&#xd;
Hence, we improve on previous work, in which nonelementary or nonuniform algorithms were found.&#xd;
&#xd;
We turn our attention to automata techniques for deciding first-order logical theories.  These techniques are useful in Integer Linear Programming and Mixed Integer Linear Programming, which in turn have applications in diverse areas of computer science and engineering.  We extend known work to address the enumeration problem for linear programming solutions.  Then, we apply a similar paradigm to give an automata theoretic decision procedure for the p-adic valued ring under addition and for formal Laurent series over a finite field with valuation and addition.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en_US">en_US</dim:field>
   <dim:field mdschema="dc" element="relation" qualifier="isformatof">bibid: 6397140</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Mathematical Logic</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Theoretical Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Finite automata</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Computable model theory</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">Computability and Complexity Properties of Automatic Structures and their Applications</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</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">Minnes, Mor Mia</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="4a528e08-7816-4868-b91c-c09247d3976c">
	&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>Computability and Complexity Properties of Automatic Structures and their Applications&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2008-05-16T20:46:28Z&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Minnes, Mor Mia&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>Mathematical Logic&lt;/Keyword>
    &lt;Keyword>Theoretical Computer Science&lt;/Keyword>
    &lt;Keyword>Finite automata&lt;/Keyword>
    &lt;Keyword>Computable model theory&lt;/Keyword>
   	&lt;Abstract>Finite state automata are Turing machines with fixed finite bounds on resource use.  Automata lend themselves well to real-time computations and efficient algorithms. Continuing a tradition of studying computability in mathematics, we examine automatic structures, mathematical objects which can be represented by automata, and apply resulting observations to computer science.&#xd;
&#xd;
We measure the complexity of automatic structures via  well-established concepts from model theory, topology, and set theory. We prove the following results. The ordinal height of any automatic well-founded partial order is bounded by \omega^\omega.  The ordinal heights of automatic well-founded relations are unbounded below the first uncomputable ordinal.  For any computable ordinal, there is an automatic structure of Scott rank at least that ordinal.  Moreover, there are automatic structures of Scott rank the first uncomputable ordinal and the successor of the first uncomputable ordinal. For any computable ordinal, there is an automatic successor tree of Cantor-Bendixson rank that ordinal.  &#xd;
&#xd;
Next, we study infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced via such operations have finite degree and can be described by finite automata over a one-letter alphabet. We investigate&#xd;
algorithmic properties of such graphs in terms of their finite presentations. In particular, we ask how hard it is to check whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another, and whether the graph is connected. We give polynomial-time algorithms answering each of these questions. For a fixed input graph, the algorithm for infinite component membership works in constant time and reachability is decided uniformly by a single automaton.&#xd;
Hence, we improve on previous work, in which nonelementary or nonuniform algorithms were found.&#xd;
&#xd;
We turn our attention to automata techniques for deciding first-order logical theories.  These techniques are useful in Integer Linear Programming and Mixed Integer Linear Programming, which in turn have applications in diverse areas of computer science and engineering.  We extend known work to address the enumeration problem for linear programming solutions.  Then, we apply a similar paradigm to give an automata theoretic decision procedure for the p-adic valued ring under addition and for formal Laurent series over a finite field with valuation and addition.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>