[pt] Este trabalho emprega conceitos e ferramentas de Teoria das Categorias e Teoria de Topoi para construir um modelo matemático de problemas, reduções entre problemas, espaços e estratégias de busca heurística. Mais precisamente, uma estratégia de construção de espaços de busca é representada por um funtor de uma certa categoria de problemas para uma certa categoria de florestas. A coleção de todos estes funtores forma um topos, um modelo específico equipado com uma lógica interna própria. Esta lógica interna é usada, então, para definir estratégias de busca e heurísticas em Teoria Local dos Conjuntos. Possíveis aplicações do trabalho incluem (1) a especificação lógica e a classificação de heurísticas e meta-heurísticas usadas na prática e (2) uma versão mais abstrata e geral de resultados específicos relacionando a estrutura de problemas com métodos de resolução adequados. / [en] This work employs concepts and tools from Category Theory and Topos Theory to construct a mathematical model for problems, reductions between problems, heuristic search spaces and strategies. More precisely, a search space construction strategy is represented by a functor from a certain category of problems to a certain category of forests. The collection of all such functors forms a topos, a specific model equipped with its own internal logic. This internal logic is then used to define search satrategies and heuristics in Local Set Theory. Possible applications of this work include (1) the logical specification and classification of heuristics and metaheuristics used in pratice and (2) a more abstract and general rendering of specific results relating the structure of problems to adequate problem-solving methods.

In dieser Arbeit wird das Fraïssé-Hrushowskis Amalgamationsverfahren in Zusammenhang mit nilpotenten graduierten Lie Algebren über einem endlichen Körper untersucht. Die Prädimensionen die in der Konstruktion auftauchen sind mit dem gruppentheoretischen Begriff der Defizienz zu vergleichen, welche auf homologische Methoden zurückgeführt werden kann. Darüber hinaus wird die Magnus-Lazardsche Korrespondenz zwischen den oben genannten Lie Algebren und nilpotenten Gruppen von Primzahl-Exponenten beschrieben. Dabei werden solche Gruppen durch die Baker-Haussdorfsche Formel in den entsprechenden Algebren definierbar interpretiert. Es wird eine omega-stabile Lie Algebra von Nilpotenzklasse 2 und Morleyrang omega + omega erhalten, indem man eine unkollabierte Version der von Baudisch konstruierten "new uncountably categorical group" betrachtet. Diese wird genau analysiert. Unter anderem wird die Unabhängigkeitsrelation des Nicht-Gabelns durch die Konfiguration des freien Amalgams charakterisiert. Mittels eines induktiven Ansatzes werden die Grundlagen entwickelt, um neue Prädimensionen für Lie Algebren der Nilpotenzklassen größer als zwei zu schaffen. Dies erweist sich als wesentlich schwieriger als im Fall 2. Wir konzentrieren uns daher auf die Nilpotenzklasse 3, als Induktionsbasis des oben genannten Prozesses. In diesem Fall wird die Invariante der Defizienz auf endlich erzeugte Lie Algebren adaptiert. Erstes Hauptergebnis der Arbeit ist der Nachweis dass diese Definition zu einem vernüftigen Begriff selbst-genügender Erweiterungen von Lie Algebren führt und sehr nah einer gewünschten Prädimension im Hrushovskischen Sinn ist. Wir zeigen – als zweites Hauptergebnis – ein erstes Amalgamationslemma bezüglich selbst-genügender Einbettungen. / In this work, the so called Fraïssé-Hrushowski amalgamation is applied to nilpotent graded Lie algebras over the p-elements field with p a prime. We are mainly concerned with the uncollapsed version of the original process. The predimension used in the construction is compared with the group theoretical notion of deficiency, arising from group Homology. We also describe in detail the Magnus-Lazard correspondence, to switch between the aforementioned Lie algebras and nilpotent groups of prime exponent. In this context, the Baker-Hausdorff formula allows such groups to be definably interpreted in the corresponding algebras. Starting from the structures which led to Baudisch’ new uncountably categorical group, we obtain an omega-stable Lie algebra of nilpotency class 2, as the countable rich Fraïssé limit of a suitable class of finite Lie algebras. We study the theory of this structure in detail: we show its Morley rank is omega+omega and a complete description of non-forking independence is given, in terms of free amalgams. In a second part, we develop a new framework for the construction of deficiency-predimensions among graded Lie algebras of nilpotency class higher than 2. This turns out to be considerably harder than the previous case. The nil-3 case in particular has been extensively treated, as the starting point of an inductive procedure. In this nilpotency class, our main results concern a suitable deficiency function, which behaves for many aspects like a Hrushovski predimension. A related notion of self-sufficient extension is given. We also prove a first amalgamation lemma with respect to self-sufficient embeddings.

The aim of distributional semantics is to design computational techniques that can automatically learn the meanings of words from a body of text. The twin challenges are: how do we represent meaning, and how do we learn these representations? The current state of the art is to represent meanings as vectors - but vectors do not correspond to any traditional notion of meaning. In particular, there is no way to talk about 'truth', a crucial concept in logic and formal semantics. In this thesis, I develop a framework for distributional semantics which answers this challenge. The meaning of a word is not represented as a vector, but as a 'function', mapping entities (objects in the world) to probabilities of truth (the probability that the word is true of the entity). Such a function can be interpreted both in the machine learning sense of a classifier, and in the formal semantic sense of a truth-conditional function. This simultaneously allows both the use of machine learning techniques to exploit large datasets, and also the use of formal semantic techniques to manipulate the learnt representations. I define a probabilistic graphical model, which incorporates a probabilistic generalisation of model theory (allowing a strong connection with formal semantics), and which generates semantic dependency graphs (allowing it to be trained on a corpus). This graphical model provides a natural way to model logical inference, semantic composition, and context-dependent meanings, where Bayesian inference plays a crucial role. I demonstrate the feasibility of this approach by training a model on WikiWoods, a parsed version of the English Wikipedia, and evaluating it on three tasks. The results indicate that the model can learn information not captured by vector space models.

Die vorliegende Dissertation besteht aus zwei Teilen, deren gemeinsames Thema in der Frage besteht, wie mächtig Zufall als Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit -- Eigenschaften haben können, die von Computeralgorithmen genutzt werden können. In zwei konkreten Fällen geben wir bis dahin unbekannte deterministische Konstruktionen solcher Strukturen: Wir derandomisieren eine randomisierte Reduktion von Alekhnovich und Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen konstruieren, und wir geben eine Reduktion von einem Problem über bipartite Graphen auf das Problem, den minmax-Wert in Dreipersonenspielen zu berechnen. Im zweiten Teil untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie durch zufällige Relationssymbole angereichert werden. Unser Ziel ist es, Techniken aus der deskriptiven Komplexitätstheorie für die Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und tatsächlich können wir zeigen, dass unsere randomisierten Logiken randomisierte Komlexitätsklassen einfangen, die in der Komplexitätstheorie untersucht werden. Unter Benutzung starker Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch negative Derandomisierungsergebnisse für unsere Logiken. Auf der negativen Seite zeigen wir, dass randomisierte erststufige Logik gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt, sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger Logik enthalten, und auch nicht in infinitärer Zähllogik auf beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass randomisierte erststufige Logik auf Strukturen mit einem unären Vokabular derandomisiert werden kann und auf additiven Strukturen in monadischer Logik zweiter Stufe enthalten ist. / This thesis is comprised of two main parts whose common theme is the question of how powerful randomness as a computational resource is. In the first part we deal with random structures which possess -- with high probability -- properties than can be exploited by computer algorithms. We then give two new deterministic constructions for such structures: We derandomise a randomised reduction due to Alekhnovich and Razborov by constructing certain unbalanced bipartite expander graphs, and we give a reduction from a problem concerning bipartite graphs to the problem of computing the minmax-value in three-player games. In the second part we study the expressive power of various logics when they are enriched by random relation symbols. Our goal is to bridge techniques from descriptive complexity with the study of randomised complexity classes, and indeed we show that our randomised logics do capture complexity classes under study in complexity theory. Using strong results on the expressive power of first-order logic and the computational power of bounded-depth circuits, we give both positive and negative derandomisation results for our logics. On the negative side, we show that randomised first-order logic gains expressive power over standard first-order logic even on structures with a built-in addition relation. Furthermore, it is not contained in monadic second-order logic on ordered structures, nor in infinitary counting logic on arbitrary structures. On the positive side, we show that randomised first-order logic can be derandomised on structures with a unary vocabulary and is contained in monadic second-order logic on additive structures.

We investigate the expressive power of different fragments of higher-order logics over finite relational structures (or equivalently, relational databases) with special emphasis in higher-order logics of order greater than or equal three. Our main results concern the study of the effect on the expressive power of higher-order logics, of simultaneously bounding the arity of the higher-order variables and the alternation of quantifiers.

This thesis is concerned with aspects of the model theory of infinite soluble groups. The results proved lie on the border between group theory and model theory: the questions asked are of a model-theoretic nature but the techniques used are mainly group-theoretic in character. We present a characterization of those groups contained in the universal closure of a restricted wreath product U wr G, where U is an abelian group of zero or finite square-free exponent and G is a torsion-free soluble group with a bound on the class of its nilpotent subgroups. For certain choices of G we are able to use this characterization to prove further results about these groups; in particular, results related to the decidability of their universal theories. The latter part of this work consists of a number of independent but related topics. We show that if G is a finitely generated abelian-by-metanilpotent group and H is elementarily equivalent to G then the subgroups gamma_n(G) and gamma_n(H) are elementarily equivalent, as are the quotient groups G/gamma_n(G) and G/gamma_n(H). We go on to consider those groups universally equivalent to F_2(VN_c), where the free groups of the variety V are residually finite p-groups for infinitely many primes p, distinguishing between the cases when c = 1 and when c > 2. Finally, we address some important questions concerning the theories of free groups in product varieties V_k · · ·V_1, where V_i is a nilpotent variety whose free groups are torsion-free; in particular we address questions about the decidability of the elementary and universal theories of such groups. Results mentioned in both of the previous two paragraphs have applications here.

Cette thèse est consacrée à l’étude des groupes linéaires définissables dans les corpsp-adiques. Les tores anisotropes jouent un rôle central tout au long de ce travail. Nousdonnons une description modèle-théorique et algébrique des Qp-tores anisotropes dedimension 1.L’étude des sous-groupes de Cartan de SL2(Qp) (où Qp est un corps élémentairementéquivalent à Qp) nous permet de donner une description complète de tous les sous-groupes définissables de SL2(Qp).Nous nous intéressons également aux groupes linéaires définissables dans des enri-chissements p-minimaux d’un corps p-adiquement clos. Nous introduisons une notionde p-connexité pour les groupes. Et nous établissons que tout groupe linéaire com-mutatif p-connexe définissable dans une telle structure est isomorphe à un groupesemi-algébrique.Enfin des résultats sur la généricité et la générosité dans SL2(Qp) sont donnés. / This thesis is dedicated to the study of linear definable groups in p-adic fields. Ani-sotropic tori play an important role in this work. We give a model-theoretic andalgebraic description of anisotropic Qp-tori of dimension 1.The study of Cartan subgroups in SL2(Qp) (where Qp is a field elementarily equi-valent to Qp) permit us to give a complete description of all definable subgroups ofSL2(Qp).We are seeing also linear groups definable in p-minimal expansions of p-adically closedfields. We introduce a notion of p-connexity for groups. We etablish that every linearcommutative p-connected group definable in such structure is isomorphic to a semi-algebraic group.Finally some results on genericity and generosity in SL2(Qp) are given.

There now exists an abundant collection of conjectures and results, of various complexities, regarding the diophantine properties of Shimura varieties. Two central such statements are the Andre-Oort and Zilber-Pink Conjectures, the first of which is known in many cases, while the second is known in very few cases indeed. The motivating result for much of this document is the modular case of the Andre-Oort Conjecture, which is a theorem of Pila. It is most commonly viewed as a statement about the simplest kind of Shimura varieties, namely modular curves. Here, we tend instead to view it as a statement about the properties of the classical modular j-function. It states, given a complex algebraic variety V, that V contains only finitely many maximal special subvarieties, where a special variety is one which arises from the arithmetic behaviour of the j-function in a certain natural way. The central question of this thesis is the following: what happens if in such statements we replace the j-function with some other kind of modular function; one which is less well-behaved in one way or another? Such modular functions are naturally called nonclassical modular functions. This question, as we shall see, can be studied using techniques of o-minimality and point-counting, but some interesting new features arise and must be dealt with. After laying out some of the classical theory, we go on to describe two particular types of nonclassical modular function: almost holomorphic modular functions and quasimodular functions (which arise naturally from the derivatives of the j-function). We go on to prove some results about the diophantine properties of these functions, including several natural Andre-Oort-type theorems, then conclude by discussing some bigger-picture questions (such as the potential for nonclassical variants of, say, Zilber-Pink) and some directions for future research in this area.

Orientador: Walter Alexandre Carnielli / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-08-12T22:46:52Z (GMT). No. of bitstreams: 1 Freire_RodrigodeAlvarenga_D.pdf: 761227 bytes, checksum: 3b1a0de92aa93b50f2bfc602bf6173bc (MD5) Previous issue date: 2009 / Resumo: Esta Tese tem como objetivo elucidar, ao menos parcialmente, a questão do significado da Teoria de Modelos para uma reflexão sobre o conhecimento matemático no século XX. Para isso, vamos buscar, primeiramente, alcançar uma compreensão da própria reflexão sobre o conhecimento matemático, que será denominada de Fundamentos do Pensamento Matemático no século XX, e da própria relevância fundacional. Em seguida, analisaremos, dentro do contexto fundacional estabelecido, o papel da Teoria de Modelos e da sua interação com a Álgebra, em geral, e, finalmente, empreenderemos um estudo de caso específico. Nesse estudo de caso mostraremos que a Teoria de Galois pode ser vista como um conteúdo lógico, e buscaremos compreender o significado fundacional desse enquadramento modelo-teórico para uma parte da Álgebra clássica. / Abstract: The aim of the present Thesis is to bring some light to the question about the status and relevance of Model Theory to a reflection about the mathematical knowledge in the twentieth century. To pursue this target, we will, first of all, try to reach a comprehension of the reflection about the mathematical knowledge, itself, what will be designated as Foundations of Mathematical Thought in the twentieth century, and of the foundational relevance, itself. In the sequel, we will provide an analysis, of the role of Model Theory and its interaction with Algebra, in general, within the established foundational setting and, finally, we will discuss a specific study case. In this study case we will show that Galois Theory can be seen as a logical content, and we will try to understand the foundational meaning of this model-theoretic framework for some part of classical Algebra. / Doutorado / Logica / Doutor em Filosofia

Le travail de cette thèse a pour objet les interactions entre deux approches d'étude des équations différentielles: la théorie des modèles des corps différentiellement clos d'une part et l'étude dynamique des équations différentielles réelles d'autre part. Dans le premier chapitre, on présente un formalisme d'algèbre différentielle, en termes de D-schémas à la Buium au-dessus du corps des nombres réels (muni de la dérivation triviale), qui permet de rendre compte de ces deux approches d'étude en même temps. Le résultat principal est un critère d'orthogonalité aux constantes pour le type générique d'une D-variétés réelle absolument irréductible, basé sur la dynamique topologique de son flot réel analytique associé. Le deuxième chapitre est consacré aux équations différentielles algébriques décrivant le flot géodésique de variétés algébriques réelles munies de 2-formes symétriques non-dégénérées. A l'aide du critère précédent, on démontre un théorème d'orthogonalité aux constantes "en courbure strictement négative'', s'appuyant sur les résultats d'Anosov et de ses successeurs concernant la dynamique topologique - la propriété de mélange topologique faible - du flot géodésique d'une variété riemannienne compacte à courbure strictement négative. En dimension 2, on conjecture en fait une description plus précise - son type générique est minimal de prégéométrie triviale - de la structure associée aux équations différentielles géodésiques unitaires. On présente, dans le troisième chapitre, des motivations et des résultats partiels concernant cette conjecture. / This thesis is dedicated to studying the interactions between two different approaches regarding differential equations: the model-theory of differentially closed fields on the one side and the dynamical analysis of real differential equations, on the other side. In the first chapter, we present a formalism from differential algebra, in terms of D-varieties à la Buium over the field of real numbers (endowed with the trivial derivation), that allows one to realise both approaches at the same time. The main result is a criterion of orthogonality to the constants, based on the topological dynamic of its associated real analytic flow. The second chapter is dedicated to the algebraic differential equations describing the (unitary) geodesic flow of a real algebraic variety endowed with an algebraic, non-degenerated symmetric 2-form. Using the previous criterion, we prove a theorem of orthogonality to the constants "in negative curvature'', that relies on the results of Anosov and of his followers, regarding the topological dynamic - the weakly mixing topological property - for the geodesic flow of a compact Riemannian manifold with negative curvature. In dimension 2, we conjecture a more precise description - its generic type is minimal and has a trivial pregeometry- for the structure associated to the unitary geodesic equation. In the third chapter, we present some motivations and partial results on this conjecture.