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.

Konzeptuelle Modelle sind zur Gestaltung und Steuerung von Informationssystemen ein akzeptiertes und weit verbreitetes Instrument. Sie werden sowohl zur Gestaltung der Organisationsstruktur als auch zur Entwicklung der unterstützenden IT-Systeme verwendet. Für diesen Aufgabenbereich existiert eine hohe Nachfrage nach externer Unterstützung, da spezifische Fachkenntnisse und Erfahrungen notwendig sind. In diesem Zusammenhang werden seit Jahrzehnten Ansätze zur Wiederverwendung in Wissenschaft und Praxis diskutiert. Die Akzeptanz und Verbreitung von explizit zur Wiederverwendung konstruierten Modellen (Referenzmodelle) bleiben jedoch deutlich hinter den Erwartungen zurück. Die vorliegende Arbeit trägt zur Untersuchung möglicher Ursachen für den ausbleibenden Erfolg von Referenzmodellen bei. Der Forschung liegt die Vermutung zugrunde, dass die Potentiale von Referenzmodellen nicht zufriedenstellend ausgeschöpft werden können, weil die existierenden bzw. verwendeten Modellierungsmethoden die theoretischen Anforderungen an die Wiederverwendung von modellhaft dargestellten Lösungen zur Unternehmensgestaltung nicht erfüllen. Die vorliegende Arbeit fasst neun Einzelpublikationen zum Themenbereich Evolutionäre Referenzmodelle zu einer kumulativen Dissertation zusammen. Es werden in einem argumentativdeduktiven Verfahren konstruktivistische Theorien zur systematischen Weiterentwicklung und Wiederverwendung konzeptueller Unternehmensmodelle untersucht. Die auf dieseWeise resultierende Erweiterung der allgemeinen Modelltheorie wurde ihrerseits argumentativ-konzeptionell mit Hilfe von semiformalen Argumentationsmodellen aufbereitet. Im Ergebnis werden ein theoretisches Rahmenwerk zur evolutionären Referenzmodellierung präsentiert und 23 konzeptionelle Anforderungen definiert, die eine gezielte Methodenentwicklung für die evolutionäre Referenzmodellierung steuern sollen.

No description available.

Automata theory, one of the main branches of theoretical computer science, established its roots in the middle of the 20th century. One of its most fundamental concepts is that of a finite automaton, a basic yet powerful model of computation. In essence, finite automata provide a method to finitely represent possibly infinite sets of strings. Such a set of strings is also called a language, and the languages which can be described by finite automata are known as regular languages. Owing to their versatility, regular languages have received a great deal of attention over the years. Other formalisms were shown to be expressively equivalent to finite automata, most notably regular grammars, regular expressions, and monadic second order (MSO) logic. To increase expressiveness, the fundamental idea underlying finite automata and regular languages was also extended to describe not only languages of strings, or words, but also of infinite words by Büchi and Muller, finite trees by Doner and Thatcher and Wright, infinite trees by Rabin, nested words by Alur and Madhusudan, and pictures by Blum and Hewitt, just to name a few examples. In a parallel line of development, Schützenberger introduced weighted automata which allow the description of quantitative properties of regular languages. In subsequent works, many of these descriptive formalisms and extensions were combined and their relationships investigated. For example, weighted regular expressions and weighted logics have been developed as well as regular expressions for trees and pictures, regular grammars for trees, pictures, and nested words, and logical characterizations for regular languages of trees, pictures, and nested words. In this work, we focus on two of these extensions and their relationship, namely weighted automata and weighted logics. Just as the classical Büchi-Elgot-Trakhtenbrot Theorem established the coincidence of regular languages with languages definable in monadic second order logic, weighted automata have been shown to be expressively equivalent to a specific fragment of a weighted monadic second order logic by Droste and Gastin. We explore several aspects of weighted automata and of this weighted logic. More precisely, the thesis considers the following topics. In the first part, we extend the classical Feferman-Vaught Theorem to the weighted setting. The Feferman-Vaught Theorem is one of the fundamental theorems in model theory. The theorem describes how the computation of the truth value of a first order sentence in a generalized product of relational structures can be reduced to the computation of truth values of first order sentences in the contributing structures and the evaluation of an MSO sentence in the index structure. The theorem itself has a long-standing history. It builds upon work of Mostowski, and was shown in subsequent works to hold true for MSO logic. Here, we show that under appropriate assumptions, the Feferman-Vaught Theorem also holds true for a weighted MSO logic with arbitrary commutative semirings as weight structure. In the second part, we lift four decidability results from max-plus word automata to max-plus tree automata. Max-plus word and tree automata are weighted automata over the max-plus semiring and assign real numbers to words or trees, respectively. We show that, like for max-plus word automata, the equivalence, unambiguity, and sequentiality problems are decidable for finitely ambiguous max-plus tree automata, and that the finite sequentiality problem is decidable for unambiguous max-plus tree automata. In the last part, we develop a logic which is expressively equivalent to quantitative monitor automata. Introduced very recently by Chatterjee, Henzinger, and Otop, quantitative monitor automata are an automaton model operating on infinite words. Quantitative monitor automata possess several interesting features. They are expressively equivalent to a subclass of nested weighted automata, an automaton model which for many valuation functions has decidable emptiness and universality problems. Also, quantitative monitor automata are more expressive than weighted Büchi-automata and their extension with valuation functions. We introduce a new logic which we call monitor logic and show that it is expressively equivalent to quantitative monitor automata.

No description available.