No description available.

We extend previous work on classifying o-minimal types, and develop several applications. Marker developed a dichotomy of o-minimal types into "cuts" and "noncuts," with a further dichotomy of cuts being either "uniquely" or "non-uniquely realizable." We use this classification to extend work by van den Dries and Miller on bounding growth rates of definable functions in Chapter 3, and work by Marker on constructing certain "small" extensions in Chapter 4. We further sub-classify "non-uniquely realizable cuts" into three categories in Chapter 2, and we give define the notion of a "decreasing" type in Chapter 5, which is a presentation of a type well-suited for our work. Using this definition, we achieve two results: in Chapter 5.2, we improve a characterization of definable types in o-minimal theories given by Marker and Steinhorn, and in Chapter 6 we answer a question of Speissegger's about extending a continuous function to the boundary of its domain. As well, in Chapter 5.3, we show how every elementary extension can be presented as decreasing.

Let F denote the field of real numbers, complex numbers, or a finite algebraic extension of the p-adic field. We prove that the special linear group SLn(F) with the usual topology induced by F is a minimal topological group. This is accomplished by first proving the minimality of the upper triangular group in SLn(F). The proof for the upper triangular group uses an induction argument on a chain of upper triangular subgroups and relies on general results for locally compact topological groups, quotient groups, and subgroups. Minimality of SLn(F) is concluded by appealing to the associated Lie group decomposition as the product of a compact group and an upper triangular group. We also prove the universal minimality of homeomorphism groups of one dimensional manifolds, and we give a new simple proof of the universal minimality of S∞.

Orientador: Ali Messaoudi / Banca: Salvador Addas Zanata / Banca: Claudio Aguinaldo Buzzi / Resumo: Uma substituicão é uma aplicação de um conjunto nito A (alfabeto) ao conjunto das palavras nitas sobre A. Neste trabalho, estudaremos propriedades topológicas e métricas dos sistemas din^amicos associados a substituicões. Em particular, mostraremos que, para uma classe de substituicões, o sistema dinâmico associado é minimal e ergódico. / Abstract: A substitution is a map from a nite set A (alphabet) to the set of nite words whose letters belong to A. In this work, we study some topological and metrical properties of the dynamical system associated to a substitution. In particular, we prove that for a class of substitutions, the associated dynamical system is minimal and ergodic. / Mestre

La thèse se situe à la charnière de l'informatique théorique et de la logique mathématique. Elle se concentre en particulier sur les aspects mathématiques de la vérification et du contrôle. La thèse se focalise sur l'étude de deux sous-classes d'automates hybrides: les automates temporisés pondérés et les automates hybrides o-minimaux. Concernant les automates temporisés pondérés, en introduisant un nouvel algorithme, nous donnons une caractérisation exacte de la complexité du problème d'atteignabilité optimal en prouvant qu'il est PSpace-complet. Nous prouvons que le model-checking de la logique WCTL est en général indécidable. Nous nous intéressons alors à une restriction de la logique WCTL. Nous montrons que la décidabilité du model-checking de WCTL restreint dépend de la dimension de l'automate et du fait que le temps soit discret ou dense. Finalement pour, nous prouvons que le problème de contrôle optimal est en général indécidable. Nous prouvons cependant que ce même problème est décidable pour les automates temporisés pondérés de dimension 1. En ce qui concerne les automates hybrides o-minimaux, à l'aide d'un encodage symbolique des trajectoires par des mots, nous sommes parvenus à prouver l'existence d'une bisimulation finie pour ces automates. De plus (toujours en utilisant nos encodages des trajectoires par des mots), nous avons obtenu des résultats de décidabilité pour des problèmes de jeux sur ces mêmes automates hybrides o-minimaux. Pour une classe d'automates hybrides o-minimaux, nous avons prouvé (i) que l'existence de stratégie gagnante pouvait être décidée et (ii) que ces stratégies gagnantes pouvaient être synthétisées.

Abstract In this thesis, we will study very small full trios and full AFLs inside the family of context-free languages. Especially, we are interested in the existence of the smallest nontrivial full trios and full AFLs. This is an old research subject, and it has not been studied much since the 1970s. A conjecture by Autebert et al. states that there does not exist a nontrivial minimal full trio inside the family of context-free languages (2) (see also (1)). First, we will show that there does not exist a nontrivial minimal full trio or a nontrivial minimal full AFL with respect to the bounded context-free languages. This result solves another old conjecture stated by Autebert et al. (1). Then we will try to generalize our result to also concern unbounded context-free languages. We will make some progress, but the problem still remains open.

In recent years the field of real numbers expanded by a multiplicative subgroup has been studied extensively. In this thesis, the known results will be extended to expansions of the real field. I will consider the structure R consisting of the field of real numbers and an irrational power function. Using Schanuel conditions, I will give a first-order axiomatization of expansions of R by a dense multiplicative subgroup which is a subset of the real algebraic numbers. It will be shown that every definable set in such a structure is a boolean combination of existentially definable sets and that these structures have o-minimal open core. A proof will be given that the Schanuel conditions used in proving these statements hold for co-countably many real numbers. The results mentioned above will also be established for expansions of R by dense multiplicative subgroups which are closed under all power functions definable in R. In this case the results hold under the assumption that the Conjecture on intersection with tori is true. Finally, the structure consisting of R and the discrete multiplicative subgroup 2^{Z} will be analyzed. It will be shown that this structure is not model complete. Further I develop a connection between the theory of Diophantine approximation and this structure.

QC 20100414

Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-02-28Bitstream added on 2014-06-13T20:47:31Z : No. of bitstreams: 1 dutra_ag_me_sjrp.pdf: 367017 bytes, checksum: 7f6e068667f2c81f80e87e474b0e7f14 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Uma substituicão é uma aplicação de um conjunto nito A (alfabeto) ao conjunto das palavras nitas sobre A. Neste trabalho, estudaremos propriedades topológicas e métricas dos sistemas din amicos associados a substituicões. Em particular, mostraremos que, para uma classe de substituicões, o sistema dinâmico associado é minimal e ergódico. / A substitution is a map from a nite set A (alphabet) to the set of nite words whose letters belong to A. In this work, we study some topological and metrical properties of the dynamical system associated to a substitution. In particular, we prove that for a class of substitutions, the associated dynamical system is minimal and ergodic.

<div>We further the research in o-minimal topology by studying in full generality definable topological spaces in o-minimal structures. These are topological spaces $(X, \tau)$, where $X$ is a definable set in an o-minimal structure and the topology $\tau$ has a basis that is (uniformly) definable. Examples include the canonical o-minimal "euclidean" topology, “definable spaces” in the sense of van den Dries [17], definable metric spaces [49], as well as generalizations of classical non-metrizable topological spaces such as the Split Interval and the Alexandrov Double Circle.</div><div><br></div><div>We develop a usable topological framework in our setting by introducing definable analogues of classical topological properties such as separability, compactness and metrizability. We characterize these notions, showing in particular that, whenever the underlying o-minimal structure expands $(\mathbb{R},<)$, definable separability and compactness are equivalent to their classical counterparts, and a similar weaker result for definable metrizability. We prove the equivalence of definable compactness and various other properties in terms of definable curves and types. We show that definable topological spaces in o-minimal expansions of ordered groups and fields have properties akin to first countability. Along the way we study o-minimal definable directed sets and types. We prove a density result for o-minimal types, and provide an elementary proof within o-minimality of a statement related to the known connection between dividing and definable types in o-minimal theories.</div><div><br></div><div>We prove classification and universality results for one-dimensional definable topological spaces, showing that these can be largely described in terms of a few canonical examples. We derive in particular that the three element basis conjecture of Gruenhage [25] holds for all infinite Hausdorff definable topological spaces in o-minimal structures expanding $(\mathbb{R},<)$, i.e. any such space has a definable copy of an interval with the euclidean, discrete or lower limit topology.</div><div><br></div><div>A definable topological space is affine if it is definably homeomorphic to a euclidean space. We prove affineness results in o-minimal expansions of ordered fields. This includes a result for Hausdorff one-dimensional definable topological spaces. We give two new proofs of an affineness theorem of Walsberg [49] for definable metric spaces. We also prove an affineness result for definable topological spaces of any dimension that are Tychonoff in a definable</div><div>sense, and derive that a large class of locally affine definable topological spaces are affine.</div>