We focus on first-order definability in the quasiordered class of finite digraphs ordered by embeddability. At first we will prove definability of each digraph up to size three. We will need to add to the quasiorder structure some digraphs as constants, so we try to find the needed set of constants as small as possible with small digraph as well. Gradually we make instruments that we can use to express the inner structure of each digraphs in the language of embeddability. At the end we investigate definability in the closely related lattice of universal classes of digraphs. We show that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice.

Thesis (Ph. D.)--University of Chicago, Dept. of Mathematics, June 2000. / Includes bibliographical references. Also available on the Internet.

In this dissertation separation and selection theorems are presented. It begins by presenting a detailed proof of the Inductive Definability Theorem of D. Cenzer and R.D. Mauldin, including their boundedness principle for monotone coanalytic operators.

This thesis investigates the connections between henselian valuations and absolute Galois groups. There are fundamental links between these: On one hand, the absolute Galois group of a field often encodes information about (henselian) valuations on that field. On the other, in many cases a henselian valuation imposes a certain structure on an absolute Galois group which makes it easier to study. We are particularly interested in the question of when a field admits a non-trivial parameter-free definable henselian valuation. By a result of Prestel and Ziegler, this does not hold for every henselian valued field. However, improving a result by Koenigsmann, we show that there is a non-trivial parameter-free definable valuation on every henselian valued field. This allows us to give a range of conditions under which a henselian field does indeed admit a non-trivial parameter-free definable henselian valuation. Most of these conditions are in fact of a Galois-theoretic nature. Throughout the thesis, we discuss a number of applications of our results. These include fields elementarily characterized by their absolute Galois group, model complete henselian fields and henselian NIP fields of positive characteristic, as well as PAC and hilbertian fields.

Answering object queries (i.e. instance retrieval) is a central task in ontology based data access (OBDA). Performing this task involves reasoning with respect to a knowledge base K (i.e. ontology) over some description logic (DL) dialect L. As the expressive power of L grows, so does the complexity of reasoning with respect to K. Therefore, eliminating the need to reason with respect to a knowledge base K is desirable. In this work, we propose an optimization to improve performance of answering object queries by eliminating the need to reason with respect to the knowledge base and, instead, utilizing cached query results when possible. In particular given a DL dialect L, an object query C over some knowledge base K and a set of cached query results S={S1, ..., Sn} obtained from evaluating past queries, we rewrite C into an equivalent query D, that can be evaluated with respect to an empty knowledge base, using cached query results S' = {Si1, ..., Sim}, where S' is a subset of S. The new query D is an interpolant for the original query C with respect to K and S. To find D, we leverage a tool for enumerating interpolants of a given sentence with respect to some theory. We describe a procedure that maps a knowledge base K, expressed in terms of a description logic dialect of first order logic, and object query C into an equivalent theory and query that are input into the interpolant enumerating tool, and resulting interpolants into an object query D that can be evaluated over an empty knowledge base. We show the efficacy of our approach through experimental evaluation on a Lehigh University Benchmark (LUBM) data set, as well as on a synthetic data set, LUBMMOD, that we created by augmenting an LUBM ontology with additional axioms.

No description available.

No description available.

FERREIRA, Francicleber Martins. Modelos minimais e hierarquia de expressividade. 2007. 109 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-29T18:55:46Z No. of bitstreams: 1 2007_dis_fmferreira.pdf: 752533 bytes, checksum: 98c57917ae2bd6af5de38f25d9ce7c39 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-29T18:56:33Z (GMT) No. of bitstreams: 1 2007_dis_fmferreira.pdf: 752533 bytes, checksum: 98c57917ae2bd6af5de38f25d9ce7c39 (MD5) / Made available in DSpace on 2016-06-29T18:56:33Z (GMT). No. of bitstreams: 1 2007_dis_fmferreira.pdf: 752533 bytes, checksum: 98c57917ae2bd6af5de38f25d9ce7c39 (MD5) Previous issue date: 2007 / Neste trabalho, o conceito de Modelo Minimal e seu uso na semântica de certas lógicas são estudados. Nós analisamos o poder expressivo de diversas lógicas que usam o conceito de Modelo Minimal para definir sua relação de satisfação. Os principais teoremas estudados foram o Teorema de Löwenheim-Skolem e o Teorema de Definibilidade de Beth. No Capítulo 1, nós damos algumas motivações e revisamos alguns conceitos básicos de Lógica. No Capítulo 2, nos estudamos a Lógica de Menor Ponto Fixo|LFP. Nós exibimos uma prova de que o Teorema de Beth não vale para LFP. Nós usamos teorias infinitas para provar isso. Utilizando um resultado de Hodkinson para L!!1!, nós mostramos que o Teorema de Beth continua não valendo mesmo para teorias finitas de LFP. Nós continuamos estudando problemas de definibilidade para LFP e demonstramos que, para tipos especiais de definições implícitas formadas por Sistemas Recursivos, que funcionam como definições recursivas em determinados contextos, existe uma definição explícita. Nós promavos ainda que o Teorema de LÄowenheim-Skolem Descendente vale para qualquer conjunto de fórmulas de LFP, independentemente de sua cardinalidade. No Capítulo 3, a Circunscrição de McCarthy e as Teorias Circunscritivas Aninhadas de Lifschitz, uma generalização da primeira. Nós abordamos o poder expressivo de Circunscrição e a falha do Teorema de LÄowenheim-Skolem Descendente. Nós também investigamos questões de definibilidade no contexto de Circunscrição. Nós encerramos esse capítulo mostrando que as Teorias Circunscritivas Aninhadas possuem poder expressivo comparável com o da Lógica de Segunda-Ordem. No Capítulo 4, nós estendemos uma lógica criada por van Benthem dando origem a duas outras lógicas, a saber, U-MIN e I-MIN. Nós provamos que ambas são equivalentes entre si em poder expressivo e daí em diante chamamos U-MIN de MIN. Nós introduzimos a Lógica Si-MIN de minimalização simultânea e provamos que Si-MIN é equivalente a U-MIN e I-MIN e também à Lógica de Segunda-Ordem. Nós então propomos o fragmento MIN¢ de MIN, cujo poder expressivo situa-se entre o da Lógica de Segunda-Ordem e o de LFP. No Capítulo 5, nós reunimos nossas conclusões e apontamos trabalhos futuros.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Neste trabalho, o conceito de Modelo Minimal e seu uso na semÃntica de certas lÃgicas sÃo estudados. NÃs analisamos o poder expressivo de diversas lÃgicas que usam o conceito de Modelo Minimal para definir sua relaÃÃo de satisfaÃÃo. Os principais teoremas estudados foram o Teorema de LÃwenheim-Skolem e o Teorema de Definibilidade de Beth. No CapÃtulo 1, nÃs damos algumas motivaÃÃes e revisamos alguns conceitos bÃsicos de LÃgica. No CapÃtulo 2, nos estudamos a LÃgica de Menor Ponto Fixo|LFP. NÃs exibimos uma prova de que o Teorema de Beth nÃo vale para LFP. NÃs usamos teorias infinitas para provar isso. Utilizando um resultado de Hodkinson para L!!1!, nÃs mostramos que o Teorema de Beth continua nÃo valendo mesmo para teorias finitas de LFP. NÃs continuamos estudando problemas de definibilidade para LFP e demonstramos que, para tipos especiais de definiÃÃes implÃcitas formadas por Sistemas Recursivos, que funcionam como definiÃÃes recursivas em determinados contextos, existe uma definiÃÃo explÃcita. NÃs promavos ainda que o Teorema de LÃowenheim-Skolem Descendente vale para qualquer conjunto de fÃrmulas de LFP, independentemente de sua cardinalidade. No CapÃtulo 3, a CircunscriÃÃo de McCarthy e as Teorias Circunscritivas Aninhadas de Lifschitz, uma generalizaÃÃo da primeira. NÃs abordamos o poder expressivo de CircunscriÃÃo e a falha do Teorema de LÃowenheim-Skolem Descendente. NÃs tambÃm investigamos questÃes de definibilidade no contexto de CircunscriÃÃo. NÃs encerramos esse capÃtulo mostrando que as Teorias Circunscritivas Aninhadas possuem poder expressivo comparÃvel com o da LÃgica de Segunda-Ordem. No CapÃtulo 4, nÃs estendemos uma lÃgica criada por van Benthem dando origem a duas outras lÃgicas, a saber, U-MIN e I-MIN. NÃs provamos que ambas sÃo equivalentes entre si em poder expressivo e daà em diante chamamos U-MIN de MIN. NÃs introduzimos a LÃgica Si-MIN de minimalizaÃÃo simultÃnea e provamos que Si-MIN à equivalente a U-MIN e I-MIN e tambÃm à LÃgica de Segunda-Ordem. NÃs entÃo propomos o fragmento MIN de MIN, cujo poder expressivo situa-se entre o da LÃgica de Segunda-Ordem e o de LFP. No CapÃtulo 5, nÃs reunimos nossas conclusÃes e apontamos trabalhos futuros.

Une partie symétrique X d'un groupe G est un sous-groupe K-approximatif s'il existe une partie finie E ⊂ G de taille K telle que X2 ⊂ E.X. L'étude combinatoire des groupes approximatifs a grandement bénéficié des apports de la Théorie des Modèles : en 2009, Hrushovski montre qu'une ultralimite de groupes approximatifs finis possède une composante connexe modèle-théorique, donc un quotient localement compact X/H. En appliquant les résultats de Gleason et Yamabe sur le cinquième problème de Hilbert, cela permet de trouver un morphisme vers un groupe de Lie, et d'en déduire des résultats de nilpotence. Cela a permis à Breuillard, Green et Tao de classifier tous les groupes approximatifs finis, en retrouvant un quotient X/H de manière combinatoire. Dans cette thèse, on s'intéresse à la construction d'un sous-groupe H type-définissable et d'indice borné, qui garantit l'existence d'un quotient localement compact. On montre que l'approche combinatoire de Breuillard, Green et Tao peut être vue de cette manière, et on la généralise à tous les groupes approximatifs définissablement moyennables. On montre aussi que si H est type-définissable dans un langage L∗, alors on peut construire un sous-groupe H qui est type-définissable sur un langage réduit L, et toujours d'indice borné. L'existence de H ne dépend donc pas du choix du langage / A symmetric subset X in a group G is a K-approximate subgroup if there exists a finite set E ⊂ G of cardinality K such that X2 ⊂ E.X. The study of approximate subgroups in multiplicative combinatorics experienced a significate advance through the use of model theory. In 2009, Hrushovski showed that an ultralimit of finite approximate subgroups has a model-theoretic connected component, thus a locally compact quotient X/H. Using the results of Gleason and Yamabe about Hilbert’s fifth problem, this allows the construction of a morphism to a Lie group, and deduce some results about nilpotency. This lead to the theorem of Breuillard, Green and Tao classifying all finite approximate subgroups, using a combinatorial construction of the quotient X/H. In this thesis, we are intersested in the conditions needed to construct a type definable subgroup H of bounded index in X. This implies the existence of a locally compact quotient.We show that the combinatorial construction of Breuillard, Green and Tao can be seen in a definable way, and give a generalisation to all definably amenable approximate subgroups. Also, we show that if H is type-definable in a language L∗, then it is possible to construct a subgroup H which is type-definable in a reduct L, still with bounded index. Thus the existence of a subgroup H does not depend on the choice of a base language.