The principal focus of this thesis is the study of the real numbers regarded as a structure endowed with its usual addition and multiplication and the operations of raising to real powers. For our first main result we prove that any statement in the language of this structure is equivalent to an existential statement, and furthermore that this existential statement can be chosen independently of the concrete interpretations of the real power functions in the statement; i.e. one existential statement will work for any choice of real power functions. This result we call uniform model completeness. For the second main result we introduce the first order theory of raising to an infinite power, which can be seen as the theory of a class of real closed fields, each expanded by a power function with infinite exponent. We note that it follows from the first main theorem that this theory is model-complete, furthermore we prove that it is decidable if and only if the theory of the real field with the exponential function is decidable. For the final main theorem we consider the problem of expanding an arbitrary o-minimal expansion of a field by a non-trivial exponential function whilst preserving o-minimality. We show that this can be done under the assumption that the structure already defines exponentiation on a bounded interval, and a further assumption about the prime model of the structure.

We investigate definability in henselian fields. Specifically, we are interested in those sets and substructures that are existentially definable or definable with `few' parameters. Our general approach is to use various versions of henselianity to understand the `local structure' of these definable sets. The fields in which we are most interested are those of positive characteristic, for example the local fields F_q((t)), but many of our methods and results also apply to p-adic and real closed fields. In positive characteristic we have to deal with inseparable field extensions and we develop the method of Λ-closure to `translate' inseparable field extensions into separable ones. In the first part of the thesis we focus on existentially definable sets, which are projections of algebraic sets. Our main tool is the Implicit Function Theorem (for polynomials) which is equivalent to t-henselianity, by work of Prestel and Ziegler. This enables us to prove that existentially definable sets are `large' in various senses. Using the Implicit Function Theorem, we also obtain a nonuniform local elimination of the existential quantifier. The non-uniformity and local character of this result at present forms an obstacle to full quantifier-elimination. From these technical statements we can deduce characterisations of, for example, existentially definable subfields and existentially definable transcendentals. We prove that a dense, regular extension of t-henselian fields is existentially closed which, in particular, implies the old result of Ershov that F_p(t)^h ≤_Ǝ F_p((t)). Using the existential closedness of large fields in henselian fields, we are able to apply many of these results to large fields. This answers questions for imperfect large fields that were answered in the perfect case by Fehm.</p> In the second part of the thesis, we work with power series fields F((t)) and subsets which are F- definable (and not contained in F). We use a `hensel-like' lemma to characterise F-orbits of (singleton) elements of F((t)). It turns out that all such orbits are Ǝ-t-definable. Consequently, we may apply our earlier results about existentially definable subsets to F-definable subsets. We can use this to characterise F-definable subfields of F((t)). As a further corollary, we obtain an Ǝ-0̸-definition of F_p[[t]] in F<sub>p<sub>((t)).

Logical deduction and abstraction from detail are fundamental, yet distinct aspects of reasoning about programs. This dissertation shows that the combination of logic and abstract interpretation enables a unified and simple treatment of several theoretical and practical topics which encompass the model theory of temporal logics, the analysis of satisfiability solvers, and the construction of Craig interpolants. In each case, the combination of logic and abstract interpretation leads to more general results, simpler proofs, and a unification of ideas from seemingly disparate fields. The first contribution of this dissertation is a framework for combining temporal logics and abstraction. Chapter 3 introduces trace algebras, a new lattice-based semantics for linear and branching time logics. A new representation theorem shows that trace algebras precisely capture the standard trace-based semantics of temporal logics. We prove additional representation theorems to show how structures that have been independently discovered in static program analysis, model checking, and algebraic modal logic, can be derived from trace algebras by abstract interpretation. The second contribution of this dissertation is a framework for proving when two lattice-based algebras satisfy the same logical properties. Chapter 5 introduces functions called subsumption and bisubsumption and shows that these functions characterise logical equivalence of two algebras. We also characterise subsumption and bisubsumption using fixed points and finitary logics. We prove a representation theorem and apply it to derive the transition system analogues of subsumption and bisubsumption. These analogues strictly generalise the well studied notions of simulation and bisimulation. Our fixed point characterisations also provide a technique to construct property preserving abstractions. The third contribution of this dissertation is abstract satisfaction, an abstract interpretation framework for the design and analysis of satisfiability procedures. We show that formula satisfiability has several different fixed point characterisations, and that satisfiability procedures can be understood as abstract interpreters. Our main result is that the propagation routine in modern sat solvers is a greatest fixed point computation involving abstract transformers, and that clause learning is an abstract transformer for a form of negation. The final contribution of this dissertation is an abstract interpretation based analysis of algorithms for constructing Craig interpolants. We identify and analyse a lattice of interpolant constructions. Our main result is that existing algorithms are two of three optimal abstractions of this lattice. A second new result we derive in this framework is that the lattice of interpolation algorithms can be ordered by logical strength, so that there is a strongest and a weakest possible construction.

O ponto central dessa dissertação é expor categorialmente as funções de verdade do cálculo proposicional clássico, assim como provar, também categorialmente, que a definição dada se comporta tal como as tabelas de verdade dos operadores. Para tanto é feita uma exposição axiomática de teoria de categorias, salientando as construções e conceitos que servirão para o propósito principal da dissertação. É dada uma maior atenção ao conceito de Topos, estrutura onde as funções de verdade são em princípio construídas. Tal exposição é precedida de uma breve exposição da história de teoria de categorias. Por fim é apresentada uma possível nova estrutra, mais simples que Topos, onde também se constrói as funções de verdade. / The main purpose of this dissertation is to give a categorial account of the truth functions from the classic propositional calculus, as well as to prove, also categorially, that the definition given behave as the truth tables of the operators. For this end, an axiomatic exposition of category theory is made, focusing on constructions and concepts which will be used for the main purpose of the dissertation. More attention is given to the concept of Topos, structure where the truth functions are primarily constructed. Preceded by a brief exposition of Category Theory history. At the end, a new possible structure in which truth functions may be constructed, simpler than a Topos, is presented.

The scheduling and Control Group at the University of South Australia has been studying the optimal control of trains for many years, and has developed in-cab devices that help drivers stay on time and minimise energy use. In this thesis, we re-examine the optimal control theory for the train control problem. In particular, we study the optimal control around steep sections of track. To calculate an optimal driving strategy we need a realistic model of train performance. In particular, we need to know a coefficient of rolling resistance and a coefficient of aerodynamic drag. In practice, these coefficients are different for every train and difficult to predict. In the thesis, we study the use of mathematical filters to estimate model parameters from observations of actual train performance.

<p>This thesis treats ultrasheaves, sheaves on the category of ultrafilters. </p><p>In the classical theory of ultrapowers, you start with an ultrafilter and, given a structure, you construct the ultrapower of the structure over the ultrafilter. The fundamental result is Los's theorem for ultrapowers giving the connection between what formulas are satisfied in the ultrapower and in the original structure. In this thesis we instead start with the category of ultrafilters (denoted <b>U</b>). On this category <b>U</b> we build the topos of sheaves on <b>U</b> (the ultrasheaves), which we think of as generalized ultrapowers. </p><p>The theorem for ultrapowers corresponding to Los's theorem is Moerdijk's theorem, first proved by Moerdijk for the topos Sh(<b>F</b>) of sheaves on filters. In the thesis we prove that Los's theorem follows from Moerdijk's theorem. We also investigate the exact relation between the topos of ultrasheaves and Moerdijk's topos Sh(<b>F</b>) and prove that Sh(<b>U</b>) is the double negation subtopos of Sh(<b>F</b>). </p><p>The connection between ultrapowers and ultrasheaves is investigated in detail. We also prove some model theoretic results for ultrasheaves, for instance we prove that they are saturated models. The Rudin-Keisler ordering is a tool used in set theory to study ultrafilters. It has a strong relationship to the category <b>U</b>. Blass has given a model theoretic characterization of this ordering and in the thesis we give a new proof of his result. </p><p>One common use of ultrapowers is to give non-standard models. In the thesis we prove that you can model internal set theory (IST) in the ultrasheaves. IST, introduced by Nelson, is a non-standard set theory, an axiomatic approach to non-standard mathematics.</p>

<p>In this thesis we introduce and study a notion of effectivity (or computability) for test functions and for distributions. This is done using the theory of effective (Scott-Ershov) domains and effective domain representations.</p><p>To be able to construct effective domain representations of the spaces of test functions considered in distribution theory we need to develop the theory of admissible domain representations over countable pseudobases. This is done in the first paper of the thesis. To construct an effective domain representation of the space of distributions, we introduce and develop a notion of partial continuous function on domains. This is done in the second paper of the thesis. In the third paper we apply the results from the first two papers to develop an effective theory of distributions using effective domains. We prove that the vector space operations on each space, as well as the standard embeddings into the space of distributions effectivise. We also prove that the Fourier transform (as well as its inverse) on the space of tempered distributions is effective. Finally, we show how to use convolution to compute primitives on the space of distributions. In the last paper we investigate the effective properties of a structure theorem for the space of distributions with compact support. We show that each of the four characterisations of the class of compactly supported distributions in the structure theorem gives rise to an effective domain representation of the space. We then use effective reductions (and Turing-reductions) to study the reducibility properties of these four representations. We prove that three of the four representations are effectively equivalent, and furthermore, that all four representations are Turing-equivalent. Finally, we consider a similar structure theorem for the space of distributions supported at 0.</p>

The thesis consists of three independent parts. Part I: Polynomial amoebas We study the amoeba of a polynomial, as de ned by Gelfand, Kapranov and Zelevinsky. A central role in the treatment is played by a certain convex function which is linear in each complement component of the amoeba, which we call the Ronkin function. This function is used in two di erent ways. First, we use it to construct a polyhedral complex, which we call a spine, approximating the amoeba. Second, the Monge-Ampere measure of the Ronkin function has interesting properties which we explore. This measure can be used to derive an upper bound on the area of an amoeba in two dimensions. We also obtain results on the number of complement components of an amoeba, and consider possible extensions of the theory to varieties of codimension higher than 1. Part II: Differential equations in the complex plane We consider polynomials in one complex variable arising as eigenfunctions of certain differential operators, and obtain results on the distribution of their zeros. We show that in the limit when the degree of the polynomial approaches innity, its zeros are distributed according to a certain probability measure. This measure has its support on the union of nitely many curve segments, and can be characterized by a simple condition on its Cauchy transform. Part III: Radon transforms and tomography This part is concerned with different weighted Radon transforms in two dimensions, in particular the problem of inverting such transforms. We obtain stability results of this inverse problem for rather general classes of weights, including weights of attenuation type with data acquisition limited to a 180 degrees range of angles. We also derive an inversion formula for the exponential Radon transform, with the same restriction on the angle.

This thesis treats ultrasheaves, sheaves on the category of ultrafilters. In the classical theory of ultrapowers, you start with an ultrafilter and, given a structure, you construct the ultrapower of the structure over the ultrafilter. The fundamental result is Los's theorem for ultrapowers giving the connection between what formulas are satisfied in the ultrapower and in the original structure. In this thesis we instead start with the category of ultrafilters (denoted <b>U</b>). On this category <b>U</b> we build the topos of sheaves on <b>U</b> (the ultrasheaves), which we think of as generalized ultrapowers. The theorem for ultrapowers corresponding to Los's theorem is Moerdijk's theorem, first proved by Moerdijk for the topos Sh(<b>F</b>) of sheaves on filters. In the thesis we prove that Los's theorem follows from Moerdijk's theorem. We also investigate the exact relation between the topos of ultrasheaves and Moerdijk's topos Sh(<b>F</b>) and prove that Sh(<b>U</b>) is the double negation subtopos of Sh(<b>F</b>). The connection between ultrapowers and ultrasheaves is investigated in detail. We also prove some model theoretic results for ultrasheaves, for instance we prove that they are saturated models. The Rudin-Keisler ordering is a tool used in set theory to study ultrafilters. It has a strong relationship to the category <b>U</b>. Blass has given a model theoretic characterization of this ordering and in the thesis we give a new proof of his result. One common use of ultrapowers is to give non-standard models. In the thesis we prove that you can model internal set theory (IST) in the ultrasheaves. IST, introduced by Nelson, is a non-standard set theory, an axiomatic approach to non-standard mathematics.

In this thesis we introduce and study a notion of effectivity (or computability) for test functions and for distributions. This is done using the theory of effective (Scott-Ershov) domains and effective domain representations. To be able to construct effective domain representations of the spaces of test functions considered in distribution theory we need to develop the theory of admissible domain representations over countable pseudobases. This is done in the first paper of the thesis. To construct an effective domain representation of the space of distributions, we introduce and develop a notion of partial continuous function on domains. This is done in the second paper of the thesis. In the third paper we apply the results from the first two papers to develop an effective theory of distributions using effective domains. We prove that the vector space operations on each space, as well as the standard embeddings into the space of distributions effectivise. We also prove that the Fourier transform (as well as its inverse) on the space of tempered distributions is effective. Finally, we show how to use convolution to compute primitives on the space of distributions. In the last paper we investigate the effective properties of a structure theorem for the space of distributions with compact support. We show that each of the four characterisations of the class of compactly supported distributions in the structure theorem gives rise to an effective domain representation of the space. We then use effective reductions (and Turing-reductions) to study the reducibility properties of these four representations. We prove that three of the four representations are effectively equivalent, and furthermore, that all four representations are Turing-equivalent. Finally, we consider a similar structure theorem for the space of distributions supported at 0.