Desarrollo de un sistema de clasificación de recursos electrónicos en el ámbito de la lógica matemática

El presente trabajo define una taxonomía para la clasificación de recursos digitales del ámbito de la lógica tradicional, y más concretamente los recursos que se podrían generar en el ámbito de la asignatura de Lógica Matemática del plan de estudios de las titulaciones de Ingeniería Técnica de Gestión y de Sistemas impartidas en la Universitat Oberta de Catalunya (UOC).

Correcció d'exercicis de lògica per l'ACME

La Universitat de Girona, i més concretament el Departament d’Informàtica i Matemàtica Aplicada, ja fa uns anys que ha posat en marxa el Projecte Avaluació Continuada i Millora de l’Ensenyament, també anomenat ACME. Aquest projecte és una plataforma d'e-learning, és a dir, un sistema d’aprenentatge a través de la xarxa que potencia la col•laboració digital i el bescanvi d’informació entre alumne i professor. El creixement que ha experimentat la plataforma, ha estat possible gràcies al disseny modular de l’aplicació, on cada nova funcionalitat que estava essent desenvolupada evolucionava de manera independent a la resta de la plataforma i sense comprometre’n el funcionament. Per afegir un nou mòdul a l’ACME, s’utilitzen els mòduls de base que confereixen l'estructura a la plataforma i les eines per incorporar nous mòduls, amb el que la implantació d’aquests a la plataforma és d’elevada senzillesa. Actualment, la majoria de les assignatures de primer del Grau d’Informàtica ja disposen d’exercicis adaptats a la plataforma, el que dóna una uniformitat en les eines i plataformes que utilitzen els alumnes en la seva formació. Però no hi són totes les assignatures, falta incloure l’assignatura de Lògica a la plataforma. D’aquesta manera, tant els alumnes com els professors de l’assignatura, podran treure profit dels beneficis esmentats que aporta l’ACME. Concretament, a l’assignatura de Lògica es disposava d’uns aplicatius a la plataforma Moodle de la Universitat de Girona on es guiava a l’alumne en la resolució dels exercicis. Aquest mètode és molt interessant com a mètode pedagògic per a l’aprenentatge inicial de l’assignatura, però no representa un repte real on els alumnes hagin d’aplicar els seus coneixements per a la seva realització. Els alumnes també disposaven d’un dossier on se’ls proposava uns exercicis molt complets, i a les pàgines finals d’aquest se’ls donava la solució. Aleshores, de manera voluntària els alumnes realitzaven els exercicis i comprovaven amb la solució si havien aprés a resoldre’ls. Per tant, tant els responsables de l'assignatura de Lògica com els responsables de la plataforma ACME van veure que es podrien desenvolupar eines a l'ACME per tal de corregir de forma automàtica els exercicis de l'assignatura. Incorporar l’assignatura de Lògica a l’ACME permet que els alumnes es vegin més involucrats a fer exercicis durant els curs de manera continuada, gràcies als terminis d’entrega, i facilita als professors la seva tasca deslliurant-los de les correccions i oferint-los-hi eines de seguiment

A general construction of internal sheaves in algebraic set theory

We present a solution to the problem of defining a counterpart in Algebraic Set Theory of the construction of internal sheaves in Topos Theory. Our approach is general in that we consider sheaves as determined by Lawvere-Tierney coverages, rather than by Grothen-dieck coverages, and assume only a weakening of the axioms for small maps originally introduced by Joyal and Moerdijk, thus subsuming the existing topos-theoretic results.

Sharpened lower bounds for cut elimination

We present sharpened lower bounds on the size of cut free proofs for first-order logic. Prior lower bounds for eliminating cuts from a proof established superexponential lower bounds as a stack of exponentials, with the height of the stack proportional to the maximum depth d of the formulas in the original proof. Our new lower bounds remove the constant of proportionality, giving an exponential stack of height equal to d − O(1). The proof method is based on more efficiently expressing the Gentzen-Solovay cut formulas as low depth formulas.

On absoluteness of categoricity in abstract elementary classes

"Vegeu el resum a l'inici del document del fitxer adjunt"

Isomorphism relations on computable structures

"Vegeu el resum a l'inici del document del fitxer adjunt"

Generalized descriptive set theory and classification theory

Descriptive set theory is mainly concerned with studying subsets of the space of all countable binary sequences. In this paper we study the generalization where countable is replaced by uncountable. We explore properties of generalized Baire and Cantor spaces, equivalence relations and their Borel reducibility. The study shows that the descriptive set theory looks very different in this generalized setting compared to the classical, countable case. We also draw the connection between the stability theoretic complexity of first-order theories and the descriptive set theoretic complexity of their isomorphism relations. Our results suggest that Borel reducibility on uncountable structures is a model theoretically natural way to compare the complexity of isomorphism relations.

Potential isomorphism of elementary substructures of a strictly stable homogeneous model

"Vegeu el resum a l'inici del document del fitxer adjunt."

Strong isomorphism reductions in complexity theory

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees.

The non-absoluteness of model existence in uncountable cardinals for Lw1,w

"Vegeu el resum a l'inici del document del fitxer adjunt"

On Borel equivalence relations in generalized Baire space

"Vegeu el resum a l'inici del document del fitxer adjunt."

A Variant of Higher-Order Anti-Unification

We present a rule-based Huet’s style anti-unification algorithm for simply-typed lambda-terms in ɳ long β normal form, which computes a least general higher-order pattern generalization. For a pair of arbitrary terms of the same type, such a generalization always exists and is unique modulo α equivalence and variable renaming. The algorithm computes it in cubic time within linear space. It has been implemented and the code is freely available

An Efficient Nominal Unification Algorithm

Nominal Unification is an extension of first-order unification where terms can contain binders and unification is performed modulo α equivalence. Here we prove that the existence of nominal unifiers can be decided in quadratic time. First, we linearly-reduce nominal unification problems to a sequence of freshness and equalities between atoms, modulo a permutation, using ideas as Paterson and Wegman for first-order unification. Second, we prove that solvability of these reduced problems may be checked in quadràtic time. Finally, we point out how using ideas of Brown and Tarjan for unbalanced merging, we could solve these reduced problems more efficiently