Deciding Kleene Algebra Terms Equivalence in Coq

This paper presents a mechanically verified implementation of an algorithm for deciding the equivalence of Kleene algebra terms within the Coq proof assistant. The algorithm decides equivalence of two given regular expressions through an iterated process of testing the equivalence of their partial derivatives and does not require the construction of the corresponding automata. Recent theoretical and experimental research provides evidence that this method is, on average, more efficient than the classical methods based on automata. We present some performance tests, comparisons with similar approaches, and also introduce a generalization of the algorithm to decide the equivalence of terms of Kleene algebra with tests. The motivation for the work presented in this paper is that of using the libraries developed as trusted frameworks for carrying out certified program verification.

Implementation for spatial data of the shared nearest neighbour with metric data structures

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Sovereign debt and CRAs: Where does the power lie?

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics

Using relational algebra on the specification of real world ETL processes

Modeling Extract-Transform-Load (ETL) processes of a Data Warehousing System has always been a challenge. The heterogeneity of the sources, the quality of the data obtained and the conciliation process are some of the issues that must be addressed in the design phase of this critical component. Commercial ETL tools often provide proprietary diagrammatic components and modeling languages that are not standard, thus not providing the ideal separation between a modeling platform and an execution platform. This separation in conjunction with the use of standard notations and languages is critical in a system that tends to evolve through time and which cannot be undermined by a normally expensive tool that becomes an unsatisfactory component. In this paper we demonstrate the application of Relational Algebra as a modeling language of an ETL system as an effort to standardize operations and provide a basis for uncommon ETL execution platforms.

A relational algebra approach to ETL modeling

The MAP-i Doctoral Programme in Informatics, of the Universities of Minho, Aveiro and Porto

Combining non-dominance, objective-order and spread metric to extend firefly algorithm to multi-objective optimization

In this paper, we propose an extension of the firefly algorithm (FA) to multi-objective optimization. FA is a swarm intelligence optimization algorithm inspired by the flashing behavior of fireflies at night that is capable of computing global solutions to continuous optimization problems. Our proposal relies on a fitness assignment scheme that gives lower fitness values to the positions of fireflies that correspond to non-dominated points with smaller aggregation of objective function distances to the minimum values. Furthermore, FA randomness is based on the spread metric to reduce the gaps between consecutive non-dominated solutions. The obtained results from the preliminary computational experiments show that our proposal gives a dense and well distributed approximated Pareto front with a large number of points.

Recurrence relations for Clifford algebra-valued orthogonal polynomials

The theory of orthogonal polynomials of one real or complex variable is well established as well as its generalization for the multidimensional case. Hypercomplex function theory (or Clifford analysis) provides an alternative approach to deal with higher dimensions. In this context, we study systems of orthogonal polynomials of a hypercomplex variable with values in a Clifford algebra and prove some of their properties.

A linear algebra approach to OLAP

Inspired by the relational algebra of data processing, this paper addresses the foundations of data analytical processing from a linear algebra perspective. The paper investigates, in particular, how aggregation operations such as cross tabulations and data cubes essential to quantitative analysis of data can be expressed solely in terms of matrix multiplication, transposition and the Khatri–Rao variant of the Kronecker product. The approach offers a basis for deriving an algebraic theory of data consolidation, handling the quantitative as well as qualitative sides of data science in a natural, elegant and typed way. It also shows potential for parallel analytical processing, as the parallelization theory of such matrix operations is well acknowledged.

Representaciones de grupos y álgebras de Lie

Este proyecto cuenta con 7 subproyectos.Subproyecto: Restricciones de representaciones de cuadrado integrable.Se continuará trabajando en el problema de restringir representaciones de cuadrado integrable en un grupo de Lie a un subgrupo semisimple o la factor unipotente de un subgrupo parabólico. En particular, se continuará analizando el caso de restringir desde el grupo SO(2n,1) al subgrupo SO(2) x SO(2n-2,1) y al factor unipotente del parabólico minimal de un grupo de Lie clásico de rango uno. Subproyecto: Representación metapléctica y grupos de Heisenberg generalizados. Se estudia la restricción de la representación metapléctica a subgrupos del grupo metapléctico. Subproyecto: Álgebras de tipo H. Se estudiarán estructuras de biálgebra en las álgebras de tipo H, álgebras de Lie nilpotentes de dos etapas. Se continuará con el estudio de cuantizaciones de álgebras de tipo H. Se estudiarán propiedades geométricas de las funciones theta generalizadas que surgen de álgebras de tipo H. Subproyecto: Módulos de peso máximo. Se intenta dar una respuesta al problema de clasificación de módulos quasifinitos de peso máximo sobre ciertas álgebras de dimensión infinita. Subproyecto: Cuantización de las álgebras de tipo H. Se tratará de cuantizar las álgebras de tipo H, álgebras de Lie nilpotentes de dos etapas. Se trabajará con una definición más general de las álgebras de Heisenberg, tratando de encontrar teoremas tipo Stone-Von Neumann y generalizaciones de las funciones theta. Subproyecto: Continuación analítica de integrales de coeficientes matriciales. Se analiza la existencia de continuación holomorfa de la integral a lo largo de un grupo semisimple real de las potencias complejas de un coeficiente matricial de una representación irreducible admisible. Subproyecto: Cálculo explícito de soluciones fundamentales de operadores invariantes. Se analizan condiciones en el polinomio que define un operador diferencial k-invariante para que resulte hipoellítico. Se trata en particular el caso del grupo SO(n,1). Subproyecto 7: Generadores de Goldie. Se trata de encontrar algoritmos para el cálculo de generadores de Goldie.

Algebras de Lie de tipo H

Es mi intención centrar mis investigaciones en los próximos años en las álgebras de Lie tipo H. Es nuestro objetivo encontrar nuevas familias de álgebras regulares no de tipo H y verificar la existencia o no de irreducibles cumpliendo de estas propiedades. En particular es interesante plantear su cuantización, es decir encontrar estructuras de álgebras de Hopf que sean deformaciones del álgebra envolvente correspondiente al álgebra de Lie en estudio. En particular estudiaremos si existen cuantizaciones quasitriangulares lo que nos llevaría soluciones de la ecuación de Yang-Baxter cuántica. Hasta ahora hemos logrado la cuantización en ciertos casos particulares. Para comprender cómo deben ser hechas las cuantizaciones en forma más general es necesario realizar un estudio sistemático de las estructuras de la biálgebra de las álgebras de Lie de tipo H. En particular se tratarán de detectar estructuras de biálgebra quasitriangulares y por consiguientes soluciones de la ecuación de Yang-Baxter clásica. Es un resultado conocido que las funciones de theta se pueden expresar como coeficiente matricial de la representación de Stone-Von Neumann. De los teoremas de Stone-Von Neumann para álgebras de tipo H surgen entonces funciones que serían una generalización de las funciones theta; es nuestro objetivo encontrar propiedades de estas funciones que puedan ser de interés.

Estructura, representaciones y cohomología de álgebras de Lie nilpotents. Structure, represntations and cohomology of nilpotent Lie algebras.

El objetivo de este proyecto es obtener resultados de calidad en el área de las representaciones y cohomología de álgebras de Lie complejas nilpotentes de dimensión finita. Los objetivos específicos son (1) Demostrar que la familia de nilradicales parabólicos de las subálgebras de Lie semisimples satisfacen la conjetura del rango toral. (2) Calcular explícitamente la cohomología, aunque sea en grados bajos, de las álgebras de Lie 3-pasos nilpotentes libres y las álgebras $\mathfrak{gl}(2,A_{k})$ donde $A_{k}$ es el álgebra de quiver truncada en $k$ asociada a un quiver cíclico de $k$ flechas (y $k$ vértices). (3) Determinar explícitamente qué diagramas de Young aparecen en la cohomología, calculada por Kostant, de los nilradicales parabólicos de las subálgebras de Lie semisimples. (4) Mejorar las actuales cotas para las representaciones fieles de dimensión mínima de álgebras de Lie 3-pasos nilpotentes.

Combinatorial and metric properties of Thompson's group T

We discuss metric and combinatorial properties of Thompson's group T, such as the normal forms for elements and uniqueness of tree pair diagrams. We relate these properties to those of Thompson's group F when possible, and highlight combinatorial differences between the two groups. We define a set of unique normal forms for elements of T arising from minimal factorizations of elements into convenient pieces. We show that the number of carets in a reduced representative of T estimates the word length, that F is undistorted in T, and that cyclic subgroups of T are undistorted. We show that every element of T has a power which is conjugate to an element of F and describe how to recognize torsion elements in T.

(When) would i lie to you? comment on? deception: the role of consequences?

This paper reconsiders the evidence on lying or deception presented in Gneezy (2005,American Economic Review). We argue that Gneezy?s data cannot reject the hipótesis that people are one of two kinds: either a person will never lie, or a person will lie whenever she prefers the outcome obtained by lying over the outcome obtained by telling the truth. This implies that so long as lying induces a preferred outcome over truth-telling, a person?s decisión of whether to lie may be completely insensitive to other changes in the induced outcomes, such as exactly how much she monetarily gains relative to how much she hurts an anonymous partner. We run new but similar experiments to those of Gneezy in order to test this hypothesis. We find that our data cannot reject this hypothesis either, but we also discover substantial differences in behavior between our sub jects and Gneezy?s sub jects.

Stable rank of leavitt path algebra

We characterize the values of the stable rank for Leavitt path algebras, by giving concrete criteria in terms of properties of the underlying graph.