• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 66
  • 11
  • 7
  • 5
  • 3
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 1
  • 1
  • 1
  • 1
  • Tagged with
  • 122
  • 122
  • 41
  • 19
  • 18
  • 12
  • 11
  • 11
  • 11
  • 10
  • 10
  • 10
  • 10
  • 9
  • 9
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
71

Expressiveness and Succinctness of First-Order Logic on Finite Words

Weis, Philipp P 13 May 2011 (has links)
Expressiveness, and more recently, succinctness, are two central concerns of finite model theory and descriptive complexity theory. Succinctness is particularly interesting because it is closely related to the complexity-theoretic trade-off between parallel time and the amount of hardware. We develop new bounds on the expressiveness and succinctness of first-order logic with two variables on finite words, present a related result about the complexity of the satisfiability problem for this logic, and explore a new approach to the generalized star-height problem from the perspective of logical expressiveness. We give a complete characterization of the expressive power of first-order logic with two variables on finite words. Our main tool for this investigation is the classical Ehrenfeucht-Fra¨ıss´e game. Using our new characterization, we prove that the quantifier alternation hierarchy for this logic is strict, settling the main remaining open question about the expressiveness of this logic. A second important question about first-order logic with two variables on finite words is about the complexity of the satisfiability problem for this logic. Previously it was only known that this problem is NP-hard and in NEXP. We prove a polynomialsize small-model property for this logic, leading to an NP algorithm and thus proving that the satisfiability problem for this logic is NP-complete. Finally, we investigate one of the most baffling open problems in formal language theory: the generalized star-height problem. As of today, we do not even know whether there exists a regular language that has generalized star-height larger than 1. This problem can be phrased as an expressiveness question for first-order logic with a restricted transitive closure operator, and thus allows us to use established tools from finite model theory to attack the generalized star-height problem. Besides our contribution to formalize this problem in a purely logical form, we have developed several example languages as candidates for languages of generalized star-height at least 2. While some of them still stand as promising candidates, for others we present new results that prove that they only have generalized star-height 1.
72

Strong conceptual completeness and various stability theoretic results in continuous model theory

Albert, Jean-Martin January 2010 (has links)
<p>In this thesis we prove a strong conceptual completeness result for first-order continuous logic. Strong conceptual completeness was proved in 1987 by Michael Makkai for classical first-order logic, and states that it is possible to recover a first-order theory T by looking at functors originating from the category Mod(T) of its models. </p> <p> We then give a brief account of simple theories in continuous logic, and give a proof that the characterization of simple theories using dividing holds in continuous structures. These results are a specialization of well established results for thick cats which appear in [Ben03b] and in [Ben03a].</p> <p> Finally, we turn to the study of non-archimedean Banach spaces over non-trivially valued fields. We give a natural language and axioms to describe them, and show that they admit quantifier elimination, and are N0-stable. We also show that the theory of non-archimedean Banach spaces has only one N 1-saturated model in any cardinality. </p> / Thesis / Doctor of Philosophy (PhD)
73

Characterisation of countably infinitely categorical theories

Karlsson, Edward January 2023 (has links)
This thesis looks at characterising countably infinitely categorical theories. That is theories for which every countably infinite model is isomorphic to every other countably infinite model. The thesis looks at the Lindenbaum-Tarski algebra, Henkin theories, types and then ends with the Ryll-Nardzewski theorem which provides several equivalences to a theory being countably infinitely categorical.
74

Completeness of the Predicate Calculus in the Basic Theory of Predication

Florio, Salvatore 25 October 2010 (has links)
No description available.
75

On the Abstract Expressive Power of Description Logics with Concrete Domains: Extended Version

Baader, Franz, De Bortoli, Filippo 02 September 2024 (has links)
Concrete domains have been introduced in Description Logic (DL) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. The primary research goal in this context was to find restrictions on the concrete domain such that its integration into certain DLs preserves decidability or tractability. In this paper, we investigate the abstract expressive power of logics extended with concrete domains, namely which classes of first-order interpretations can be expressed using these logics. In the first part of the paper, we show that, under natural conditions on the concrete domain D (which also play a role for decidability), extensions of first-order logic (FOL) or 𝒜ℒ𝒞 with D share important formal properties with FOL, such as the compactness and the Löwenheim-Skolem property. Nevertheless, their abstract expressive power need not be contained in that of FOL. In the second part of the paper, we investigate whether finitely bounded homogeneous structures, which preserve decidability if employed as concrete domains, can be used to express certain universal first-order sentences, which then could be added to DL knowledge bases without destroying decidability. We show that this requires rather strong conditions on said sentences or an extended scheme for integrating the concrete domain that leads to undecidability.
76

Contributions to Descriptive Set Theory

Atmai, Rachid 08 1900 (has links)
In this dissertation we study closure properties of pointclasses, scales on sets of reals and the models L[T2n], which are very natural canonical inner models of ZFC. We first characterize projective-like hierarchies by their associated ordinals. This solves a conjecture of Steel and a conjecture of Kechris, Solovay, and Steel. The solution to the first conjecture allows us in particular to reprove a strong partition property result on the ordinal of a Steel pointclass and derive a new boundedness principle which could be useful in the study of the cardinal structure of L(R). We then develop new methods which produce lightface scales on certain sets of reals. The methods are inspired by Jackson’s proof of the Kechris-Martin theorem. We then generalize the Kechris-Martin Theorem to all the Π12n+1 pointclasses using Jackson’s theory of descriptions. This in turns allows us to characterize the sets of reals of a certain initial segment of the models L[T2n]. We then use this characterization and the generalization of Kechris-Martin theorem to show that the L[T2n] are unique. This generalizes previous work of Hjorth. We then characterize the L[T2n] in term of inner models theory, showing that they actually are constructible models over direct limit of mice with Woodin cardinals, a counterpart to Steel’s result that the L[T2n+1] are extender models, and finally show that the generalized contiuum hypothesis holds in these models, solving a conjecture of Woodin.
77

Chaînes et dépendance / Linear orders and dependence

De aldama sánchez, Ricardo 18 December 2009 (has links)
Le cadre général de cette thèse est celui de la propriété d’indépendance en théorie des modèles. Les théories sans cette propriété sont appelées NIP ou dépendantes. L’objectif principal est de trouver de nouveaux exemples de théories appartenant à cette classe. Nous montrons d’abord un résultat isolé qui répond une question de Pillay : dans un groupe NIP possédant une partie infinie de classe de nilpotence finie, on y trouve un sous-groupe définissable de même classe de nilpotence et contenant cette partie infinie. Le reste de la thèse est motivé par deux cadres extrêmement proches : les groupes abéliens munis d’une chaîne de sous-groupes uniformément définissables, et les groupes abéliens valués. Dans le premier cas nous identifions une certaine théorie et nous étudions plusieurs extensions de cette théorie. Nous prouvons une élimination des quantificateurs dans chacune des ses extensions, grâce à laquelle la NIP en découle facilement. Le dernier résultat est le plus substantiel. Nous montrons qu’une théorie naturelle de chaîne colorée munie quasi-automorphismes n’a pas la propriété d’indépendance. Nous appliquons ensuite ce résultat à une certaine théorie de groupes valués, étudiée par Simonetta dans le contexte des groupes C-minimaux, pour en conclure qu’elle est NIP. Nous montrons aussi d’une façon assez directe (en utilisant des résultats de Rubin et Poizat) qu’une chaîne colorée munie d’automorphismes est NIP. / This PhD thesis is in the general area of the independence property in model theory.Theories without this property are called NIP or dependent. The main objective of this thesis is to find new examples belonging to this class. Firstly, we prove an isolated result that answers a question stated by Pillay : if a NIP group contains an infinite set of finite nilpotency class, then there exists a definable subgroup of the same nilpotency class containing this set. The rest of this thesis is motivated by two extremely closed related contexts : abelian groups equipped with an uniformly definable chain of subgroups, and valued groups. In the first case we identify a theory and study several extensions of it. We prove quantifier elimination in each of these extensions, and use it to easily conclude that they are NIP. The last result is the most significant one. We prove that a natural theory of linear orderings equipped with quasi-automorphisms doesn’t have the independence property. Then we apply this result to a particular theory of valued abelian groups, which has been studied by Simonetta in the context of C-minimal groups, to conclude that it is NIP. We also prove in a rather straightforward way (using results by Rubin and Poizat) that a linear ordering equipped with automorphisms is NIP
78

Théorie des modèles d'expansions de corps valués : phénomènes de séparation / Model theory of expansions of valued fields : separation phenomena

Rioux, Romain 18 September 2017 (has links)
Cette thèse est consacrée à l'étude d'un point de vue modèle théorique de corps valués algébriquement clos enrichis d'un prédicat qui représente soit un sous-groupe multiplicatif soit un sous-corps. Nous donnons un résultat d'élimination partielle des quantificateurs pour les structures du type (M , G), où M est un corps valué algébriquement clos et où G un sous-groupe multiplicatif sur lequel la valuation est injective... / This thesis is dedicated to the model theoretic study of algebraically closed valued fields equipped with a additional unary predicate for either a multiplicative subgroup or a subfield.We give a result of relative quantifier elimination for structures of the kind (M , G), where M is an algebraically closed valued field and G is a multiplicative subgroup on wich the valuation is injective...
79

Ax-Schanuel type inequalities in differentially closed fields

Aslanyan, Vahagn January 2017 (has links)
In this thesis we study Ax-Schanuel type inequalities for abstract differential equations. A motivating example is the exponential differential equation. The Ax-Schanuel theorem states positivity of a predimension defined on its solutions. The notion of a predimension was introduced by Hrushovski in his work from the 1990s where he uses an amalgamation-with-predimension technique to refute Zilber's Trichotomy Conjecture. In the differential setting one can carry out a similar construction with the predimension given by Ax-Schanuel. In this way one constructs a limit structure whose theory turns out to be precisely the first-order theory of the exponential differential equation (this analysis is due to Kirby (for semiabelian varieties) and Crampin, and it is based on Zilber's work on pseudo-exponentiation). One says in this case that the inequality is adequate. Thus, by an Ax-Schanuel type inequality we mean a predimension inequality for a differential equation. Our main question is to understand for which differential equations one can find an adequate predimension inequality. We show that this can be done for linear differential equations with constant coefficients by generalising the Ax-Schanuel theorem. Further, the question turns out to be closely related to the problem of recovering the differential structure in reducts of differentially closed fields where we keep the field structure (which is quite an interesting problem in its own right). So we explore that question and establish some criteria for recovering the derivation of the field. We also show (under some assumptions) that when the derivation is definable in a reduct then the latter cannot satisfy a non-trivial adequate predimension inequality. Another example of a predimension inequality is the analogue of Ax-Schanuel for the differential equation of the modular j-function due to Pila and Tsimerman. We carry out a Hrushovski construction with that predimension and give an axiomatisation of the first-order theory of the strong Fra&iuml;ss&eacute; limit. It will be the theory of the differential equation of j under the assumption of adequacy of the predimension. We also show that if a similar predimension inequality (not necessarily adequate) is known for a differential equation then the fibres of the latter have interesting model theoretic properties such as strong minimality and geometric triviality. This, in particular, gives a new proof for a theorem of Freitag and Scanlon stating that the differential equation of j defines a trivial strongly minimal set.
80

Groupes hyperboliques et logique du premier ordre / Hyperbolic groups and first-order logic

André, Simon 15 July 2019 (has links)
Deux groupes sont dits élémentairement équivalents s'ils satisfont les mêmes énoncés du premier ordre dans le langage des groupes. Aux environs de l'année 1945, Tarski posa la question suivante, connue désormais comme le problème de Tarski : les groupes libres non abéliens sont-ils élémentairement équivalents ? Une réponse positive à cette fameuse question fut apportée plus d'un demi-siècle plus tard par Sela, et en parallèle par Kharlampovich et Myasnikov, comme le point d'orgue de deux volumineuses séries de travaux. Dans la foulée, Sela généralisa aux groupes hyperboliques sans torsion, dont les groupes libres sont des représentants emblématiques, les méthodes de nature géométrique qu'il avait précédemment introduites à l'occasion de son travail sur le problème de Tarski. Les résultats rassemblés ici s'inscrivent dans cette lignée, en s'en démarquant toutefois dans la mesure où ils traitent des théories du premier ordre des groupes hyperboliques en présence de torsion. Dans un premier chapitre, on démontre, entre autres, que tout groupe de type fini qui est élémentairement équivalent à un groupe hyperbolique est lui-même hyperbolique. On démontre ensuite que les groupes virtuellement libres sont presque homogènes, ce qui signifie que deux éléments qui sont indiscernables du point de vue de la logique du premier ordre sont dans la même orbite sous l'action du groupes des automorphismes du groupe ambiant, à une indétermination finie près. Enfin, on donne une classification complète des groupes virtuellement libres de type fini du point de l'équivalence élémentaire à deux quantificateurs. / Two groups are said to be elementarily equivalent if they satisfy the same first-order sentences in the language of groups, that is the same mathematical statements whose variables are only interpreted as elements of a group. Around 1945, Tarski asked the following question : are non-abelian free groups elementarily equivalent? An affirmative answer to this famous Tarski's problem was given in 2006 by Sela and independently by Kharlampovich and Myasnikov, as the culmination of two voluminous series of papers. Then, Sela gave a classification of all finitely generated groups that are elementarily equivalent to a given torsion-free hyperbolic group. The results contained in the present thesis fall into this context and deal with first-order theories of hyperbolic groups with torsion. In the first chapter, we prove that any finitely generated group that is elementarily equivalent to a hyperbolic group is itself a hyperbolic group. Then, we prove that virtually free groups are almost homogeneous, meaning that elements are almost determined up to automorphism by their type, i.e. the first-order formulas they satisfy. In the last chapter, we give a complete classification of finitely generated virtually free groups up to elementary equivalence with two quantifiers.

Page generated in 0.0426 seconds