Algoritmos para decidir definibilidad de relaciones en fragmentos de primer orden
Tesis (Lic. en Ciencias de la Computación)--Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación, 2016.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | bachelorThesis |
| Language: | spa |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/11086/4164 |
| _version_ | 1801214855263289344 |
|---|---|
| author | Ventura, Pablo Gabriel |
| author2 | Campercholi, Miguel Alejandro Carlos |
| author_facet | Campercholi, Miguel Alejandro Carlos Ventura, Pablo Gabriel |
| author_sort | Ventura, Pablo Gabriel |
| collection | Repositorio Digital Universitario |
| description | Tesis (Lic. en Ciencias de la Computación)--Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación, 2016. |
| format | bachelorThesis |
| id | rdu-unc.4164 |
| institution | Universidad Nacional de Cordoba |
| language | spa |
| publishDate | 2016 |
| record_format | dspace |
| spelling | rdu-unc.41642022-10-13T11:33:14Z Algoritmos para decidir definibilidad de relaciones en fragmentos de primer orden Ventura, Pablo Gabriel Campercholi, Miguel Alejandro Carlos Teoría de modelos Model theory Teoría de modelos finitos Definibilidad Relaciones Algoritmos Morfismos Fragmentos de primer orden Finite model theory Definability Algorithms Morphisms Fragments of the first order Tesis (Lic. en Ciencias de la Computación)--Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación, 2016. En este trabajo desarrollamos algoritmos para decidir definibilidad de relaciones sobre familias finitas de estructuras finitas de primer orden. Presentamos algoritmos para los siguientes tipos de fórmulas: abiertas, abiertas positivas, existenciales, existenciales positivas y fórmulas sin restricciones. El punto de partida para estos algoritmos es una serie de resultados teóricos que caracterizan la definibilidad en términos de la preservación de morfismos. Presentamos además procedimientos para generar las álgebras de relaciones definibles en los formatos arriba enumerados. Adicionalmente, introducimos el paquete Definability desarrollado para SageMath, en el cual se implementan los algoritmos desarrollados. Las pruebas de este paquete inspiraron un teorema que caracteriza las relaciones binarias definibles por existenciales positivas en reticulados distributivos. In this work we develop algorithms to decide definability of relations over finite families of finite first order structures. We present algorithms for the following kinds of formulas: open, positive open, existential, positive existential and without restrictions. The starting point to these algorithms is a series of theoretical results characterizing definability in terms of preservation of morphisms. We also present procedures to generate the algebras of defi nable relations for each of the above listed formats. Additionally, we introduce a package for SageMath, Definability, where the algorithms are implemented. The testing of this package inspired a theorem characterizing the binary relations definable by positive existential formulas over distributive lattices. 2016-10-17T15:36:45Z 2016-10-17T15:36:45Z 2016-03 bachelorThesis http://hdl.handle.net/11086/4164 spa Atribución-NoComercial-SinDerivadas 2.5 Argentina http://creativecommons.org/licenses/by-nc-nd/2.5/ar/ |
| spellingShingle | Teoría de modelos Model theory Teoría de modelos finitos Definibilidad Relaciones Algoritmos Morfismos Fragmentos de primer orden Finite model theory Definability Algorithms Morphisms Fragments of the first order Ventura, Pablo Gabriel Algoritmos para decidir definibilidad de relaciones en fragmentos de primer orden |
| title | Algoritmos para decidir definibilidad de relaciones en fragmentos de primer orden |
| title_full | Algoritmos para decidir definibilidad de relaciones en fragmentos de primer orden |
| title_fullStr | Algoritmos para decidir definibilidad de relaciones en fragmentos de primer orden |
| title_full_unstemmed | Algoritmos para decidir definibilidad de relaciones en fragmentos de primer orden |
| title_short | Algoritmos para decidir definibilidad de relaciones en fragmentos de primer orden |
| title_sort | algoritmos para decidir definibilidad de relaciones en fragmentos de primer orden |
| topic | Teoría de modelos Model theory Teoría de modelos finitos Definibilidad Relaciones Algoritmos Morfismos Fragmentos de primer orden Finite model theory Definability Algorithms Morphisms Fragments of the first order |
| url | http://hdl.handle.net/11086/4164 |
| work_keys_str_mv | AT venturapablogabriel algoritmosparadecidirdefinibilidadderelacionesenfragmentosdeprimerorden |