Algoritmos para decidir definibilidad de fragmentos de lógica en primer orden

Tesis (Doctor en Ciencias de la Computación)--Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2023.

Guardado en:
Detalles Bibliográficos
Autor principal: Ventura, Pablo Gabriel
Otros Autores: Campercholi, Miguel Alejandro Carlos
Formato: bachelorThesis
Lenguaje:Español
Publicado: 2023
Materias:
Teoría de modelos finitos
Definibilidad
Relaciones
Algoritmos
Morfismos
Fragmentos de primer orden
Model theory
Finite model theory
Definability
Relations
Algorithms
Morphisms
First order fragments
Acceso en línea:http://hdl.handle.net/11086/548395
Aporte de:
Repositorio Digital Universitario (UNC) de Universidad Nacional de Córdoba
id I10-R141-11086-548395
record_format dspace
spelling I10-R141-11086-5483952023-08-31T13:17:38Z Algoritmos para decidir definibilidad de fragmentos de lógica en primer orden Ventura, Pablo Gabriel Campercholi, Miguel Alejandro Carlos Teoría de modelos finitos Definibilidad Relaciones Algoritmos Morfismos Fragmentos de primer orden Model theory Finite model theory Definability Relations Algorithms Morphisms First order fragments Tesis (Doctor en Ciencias de la Computación)--Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2023. Fil: Ventura, Pablo Gabriel. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina. Dada una estructura A, decimos que un conjunto T es definible en primer orden sin cuantificadores si y solo si existe una fórmula sin cuantificadores φ tal queA ⊨φ(x) para todo x∈T, mientras que A ⊭φ(x) para todo x∈A\T. Esta tesis doctoral aborda la definibilidad de primer orden sin cuantificadores desde un enfoque computacional. Se han desarrollado algoritmos eficientes basados en propiedades semánticas de los modelos y se han implementado para su uso como asistentes de investigación. También se presenta un manual de uso para las herramientas y un conjunto de pruebas para comprobar su eficiencia empíricamente. Finalmente, se ha estudiado la complejidad de estos problemas de definibilidad y se han presentado resultados teóricos que establecen los límites de su eficiencia computacional. Given a structure A, we say that a set T is definable in first-order logic without quantifiers if and only if there exists a first-order formula φ without quantifiers such that A ⊨φ(x) for all x∈T, while A ⊭φ(x) for all x∈A\T. This doctoral thesis addresses first-order definability without quantifiers from a computational approach. Efficient algorithms based on semantic properties of models have been developed and implemented for use as research assistants. A usage manual for the tools and a set of tests to empirically verify their efficiency are also presented. Finally, the complexity of these definability problems has been studied and theoretical results establishing the limits of their computational efficiency have been presented. Fil: Ventura, Pablo Gabriel. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina. 2023-08-08T14:41:45Z 2023-08-08T14:41:45Z 2023-06-29 bachelorThesis http://hdl.handle.net/11086/548395 spa Attribution-NonCommercial-NoDerivatives 4.0 Internacional http://creativecommons.org/licenses/by-nc-nd/4.0/
institution Universidad Nacional de Córdoba
institution_str I-10
repository_str R-141
collection Repositorio Digital Universitario (UNC)
language Español
topic Teoría de modelos finitos
Definibilidad
Relaciones
Algoritmos
Morfismos
Fragmentos de primer orden
Model theory
Finite model theory
Definability
Relations
Algorithms
Morphisms
First order fragments
spellingShingle Teoría de modelos finitos
Definibilidad
Relaciones
Algoritmos
Morfismos
Fragmentos de primer orden
Model theory
Finite model theory
Definability
Relations
Algorithms
Morphisms
First order fragments
Ventura, Pablo Gabriel
Algoritmos para decidir definibilidad de fragmentos de lógica en primer orden
topic_facet Teoría de modelos finitos
Definibilidad
Relaciones
Algoritmos
Morfismos
Fragmentos de primer orden
Model theory
Finite model theory
Definability
Relations
Algorithms
Morphisms
First order fragments
description Tesis (Doctor en Ciencias de la Computación)--Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2023.
author2 Campercholi, Miguel Alejandro Carlos
author_facet Campercholi, Miguel Alejandro Carlos
Ventura, Pablo Gabriel
format bachelorThesis
author Ventura, Pablo Gabriel
author_sort Ventura, Pablo Gabriel
title Algoritmos para decidir definibilidad de fragmentos de lógica en primer orden
title_short Algoritmos para decidir definibilidad de fragmentos de lógica en primer orden
title_full Algoritmos para decidir definibilidad de fragmentos de lógica en primer orden
title_fullStr Algoritmos para decidir definibilidad de fragmentos de lógica en primer orden
title_full_unstemmed Algoritmos para decidir definibilidad de fragmentos de lógica en primer orden
title_sort algoritmos para decidir definibilidad de fragmentos de lógica en primer orden
publishDate 2023
url http://hdl.handle.net/11086/548395
work_keys_str_mv AT venturapablogabriel algoritmosparadecidirdefinibilidaddefragmentosdelogicaenprimerorden
_version_ 1782014476119179264

Ejemplares similares