Relational and Allegorical Semantics for Constraint Logic Programming

El cálculo de relaciones binarias fue creado por De Morgan en 1860 para ser posteriormente desarrollado en gran medida por Peirce y Schröder. Tarski, Givant, Freyd y Scedrov demostraron que las álgebras relacionales son capaces de formalizar la lógica de primer orden, la lógica de orden superior así como la teoría de conjuntos. A partir de los resultados matemáticos de Tarski y Freyd, esta tesis desarrolla semánticas denotacionales y operacionales para la programación lógica con restricciones usando el álgebra relacional como base. La idea principal es la utilización del concepto de semántica ejecutable, semánticas cuya característica principal es el que la ejecución es posible utilizando el razonamiento estándar del universo semántico, este caso, razonamiento ecuacional. En el caso de este trabajo, se muestra que las álgebras relacionales distributivas con un operador de punto fijo capturan toda la teoría y metateoría estándar de la programación lógica con restricciones incluyendo los árboles utilizados en la búsqueda de demostraciones. La mayor parte de técnicas de optimización de programas, evaluación parcial e interpretación abstracta pueden ser llevadas a cabo utilizando las semánticas aquí presentadas. La demostración de la corrección de la implementación resulta extremadamente sencilla. En la primera parte de la tesis, un programa lógico con restricciones es traducido a un conjunto de términos relacionales. La interpretación estándar en la teoría de conjuntos de dichas relaciones coincide con la semántica estándar para CLP. Las consultas contra el programa traducido son llevadas a cabo mediante la reescritura de relaciones. Para concluir la primera parte, se demuestra la corrección y equivalencia operacional de esta nueva semántica, así como se define un algoritmo de unificación mediante la reescritura de relaciones. La segunda parte de la tesis desarrolla una semántica para la programación lógica con restricciones usando la teoría de alegorías—versión categórica del álgebra de relaciones—de Freyd. Para ello, se definen dos nuevos conceptos de Categoría Regular de Lawvere y _-Alegoría, en las cuales es posible interpretar un programa lógico. La ventaja fundamental que el enfoque categórico aporta es la definición de una máquina categórica que mejora e sistema de reescritura presentado en la primera parte. Gracias al uso de relaciones tabulares, la máquina modela la ejecución eficiente sin salir de un marco estrictamente formal. Utilizando la reescritura de diagramas, se define un algoritmo para el cálculo de pullbacks en Categorías Regulares de Lawvere. Los dominios de las tabulaciones aportan información sobre la utilización de memoria y variable libres, mientras que el estado compartido queda capturado por los diagramas. La especificación de la máquina induce la derivación formal de un juego de instrucciones eficiente. El marco categórico aporta otras importantes ventajas, como la posibilidad de incorporar tipos de datos algebraicos, funciones y otras extensiones a Prolog, a la vez que se conserva el carácter 100% declarativo de nuestra semántica. ABSTRACT The calculus of binary relations was introduced by De Morgan in 1860, to be greatly developed by Peirce and Schröder, as well as many others in the twentieth century. Using different formulations of relational structures, Tarski, Givant, Freyd, and Scedrov have shown how relation algebras can provide a variable-free way of formalizing first order logic, higher order logic and set theory, among other formal systems. Building on those mathematical results, we develop denotational and operational semantics for Constraint Logic Programming using relation algebra. The idea of executable semantics plays a fundamental role in this work, both as a philosophical and technical foundation. We call a semantics executable when program execution can be carried out using the regular theory and tools that define the semantic universe. Throughout this work, the use of pure algebraic reasoning is the basis of denotational and operational results, eliminating all the classical non-equational meta-theory associated to traditional semantics for Logic Programming. All algebraic reasoning, including execution, is performed in an algebraic way, to the point we could state that the denotational semantics of a CLP program is directly executable. Techniques like optimization, partial evaluation and abstract interpretation find a natural place in our algebraic models. Other properties, like correctness of the implementation or program transformation are easy to check, as they are carried out using instances of the general equational theory. In the first part of the work, we translate Constraint Logic Programs to binary relations in a modified version of the distributive relation algebras used by Tarski. Execution is carried out by a rewriting system. We prove adequacy and operational equivalence of the semantics. In the second part of the work, the relation algebraic approach is improved by using allegory theory, a categorical version of the algebra of relations developed by Freyd and Scedrov. The use of allegories lifts the semantics to typed relations, which capture the number of logical variables used by a predicate or program state in a declarative way. A logic program is interpreted in a _-allegory, which is in turn generated from a new notion of Regular Lawvere Category. As in the untyped case, program translation coincides with program interpretation. Thus, we develop a categorical machine directly from the semantics. The machine is based on relation composition, with a pullback calculation algorithm at its core. The algorithm is defined with the help of a notion of diagram rewriting. In this operational interpretation, types represent information about memory allocation and the execution mechanism is more efficient, thanks to the faithful representation of shared state by categorical projections. We finish the work by illustrating how the categorical semantics allows the incorporation into Prolog of constructs typical of Functional Programming, like abstract data types, and strict and lazy functions.

Sistemas de distribución en entornos de televisión

Actualmente los entornos de televisión manejan gran cantidad de señales procedentes de diferentes fuentes y suministradas en diferentes estándares: SD-SDI,HD-SDI, 3G, DVB-ASI, señales moduladas en banda L. En la gran mayoría de los centros de radiodifusión es necesario al menos en alguno de los pasos del transporte de señales o de su explotación, la replicación de las diferentes señales de entrada a sus diferentes destinos. En el siguiente PFC se tratará de dar a conocer, los principales sistemas que se emplean en los entornos de televisión para la distribución de las señales que se utilizan en los mismos. Los sistemas distributivos se encargan de distribuir y replicar la señal de entrada a ellos hacia diferentes destinos. La principal idea con la que se diseñan estos sistemas es que la señal de entrada no sufra ningún tipo de degradación como fruto de la replicación o división, siendo incluso aconsejable que determinados sistemas regeneren la señal de entrada a sus salidas. El proyecto se divide en tres capítulos: - Capítulo de conceptos teóricos: En el que se presentarán, los fundamentos teóricos que justifican la tecnología utilizada por los diferentes sistemas. - Capítulo de distribución de señales SDI y ASI: En el cual se presentarán los principales sistemas utilizados, para la distribución de señales SD-SDI, HDSDI, 3G y DVB-ASI. - Capítulo de distribución de señales en banda-L: Donde se mostrarán, los principales sistemas de distribución de señales moduladas en banda-L. Al finalizar la lectura del mismo, el lector debería conocer los principales sistemas que se utilizan en la distribución de señales SDI y ASI y en la distribución de señales en banda L. Comprender mediante la teoría expuesta, y los sistemas presentados, las diferentes problemáticas que afrontan los diferentes equipos y la tecnología que subyace en un segundo plano para solventar las problemáticas. Nowadays, broadcast environments, manage an extensive amount of signals from several sources, using differents standards: SD-SDI, HD-SDI, 3G, DVBASI, modulated L band signals. In most of the broadcast infraestructures, it´s usually needed, at any of the transmissions steps, to replicate the source signal to many destinations. This PFC is intended to shown the main systems used to distribute and replicate signals in broadcast environments. Distributive Systems are used to distribute and replicate the source signals to as many destinations as are needed. The main idea behind the design of those systems is to preserve the integrity of the original signal, due to replications or division classical pathologies. Even it is recomendad that those systems are able to regenerate the original signal, trying to avoid or compesate those pathologies. The PFC is divided in three chapters: - Chapter 1: Theorical concepts: In this chapter is presented the minimal theory needed to understand the complex of the tecnology, for those distributive systems. - Chapter 2: Distribution of SDI and ASI signals: It is shown the main systems used to replicate and distribution of the SDI and ASI signals. It will also treatment the state of the art of the actually new systems. - Chapter 3: Distribution of L band signals. It will be shown the main systems used for L band signals At the end of reading this PFC, the reader must known the main systems used for distribution SDI and ASI signals, also L band signals. It is important to understand the contents of the PFC, the systems, the several problems and the background tecnology that is needed to afront the replication known patologies.

Employment rate impacts of charging the Heavy Good Vehicle corridor (Madrid-Sevilla) across Spanish regions: a Random Utility Based Multiregional Input-Output approach

The implementation of a charging policy for heavy goods vehicles in European Union (EU) member countries has been imposed to reflect costs of construction and maintenance of infrastructure as well as externalities such as congestion, accidents and environmental impact. In this context, EU countries approved the Eurovignette directive (1999/62/EC) and its amending directive (2006 /38/EC) which established a legal framework to regulate the system of tolls. Even if that regulation seek s to increase the efficien cy of freight, it will trigger direct and indirect effects on Spain’s regional economies by increasing transport costs. This paper presents the development of a multiregional Input-Output methodology (MRIO) with elastic trade coefficients to predict in terregional trade, using transport attributes integrated in multinomial logit models. This method is highly useful to carry out an ex-ante evaluation of transport policies because it involves road freight transport cost sensitivity, and determine regional distributive and substitution economic effect s of countries like Spain, characterized by socio-demographic and economic attributes, differentiated region by region. It will thus be possible to determine cost-effective strategies, given different policy scenarios. MRIO mode l would then be used to determine the impact on the employment rate of imposing a charge in the Madrid-Sevilla corridor in Spain. This methodology is important for measuring the impact on the employment rate since it is one of the main macroeconomic indicators of Spain’s regional and national economic situation. A previous research developed (DESTINO) using a MRIO method estimated employment impacts of road pricing policy across Spanish regions considering a fuel tax charge (€/liter) in the entire shortest cost path network for freight transport. Actually, it found that the variation in employment is expected to be substantial for some regions, and negligible for others. For example, in this Spanish case study of regional employment has showed reductions between 16.1% (Rioja) and 1.4% (Madrid region). This variation range seems to be related to either the intensity of freight transport in each region or dependency of regions to transport intensive economic sect ors. In fact, regions with freight transport intensive sectors will lose more jobs while regions with a predominantly service economy undergo a fairly insignificant loss of employment. This paper is focused on evaluating a freight transport vehicle-kilometer charge (€/km) in a non-tolled motorway corridor (A-4) between Madrid-Sevilla (517 Km.). The consequences of the road pricing policy implementation show s that the employment reductions are not as high as the diminution stated in the previous research because this corridor does not affect the whole freight transport system of Spain.

Interregional trade changes in Spain caused by the introduction of a road fee charge for heavy goods vehicles

The introduction of a homogeneous road charging system according to the Directive 2011/76/EU for the use of roads is still under development in most European Union (EU) member states. Spain, like other EU members, has been encouraged to introduce a charging system for Heavy Goods Vehicles (HGVs) throughout the country. This nationwide charge has been postponed because there are serious concerns about their advantages from an economic point of view. Within this context, this paper applies an integrated modeling approach to shape elastic trade coefficients among regions by using a random utility based multiregional Input- Output (RUBMRIO) approach and a road transport network model in order to determine regional distributive and substitutive economic effects by simulating the introduction of a distance-based charge (?/km) considering 7,053.8 kilometers of free highways linking the capitals of the Spanish regions. In addition, an in-depth analysis of interregional trade changes is developed to evaluate and characterize the role of the road charging approach in trade relations among regions and across freight intensive economic sectors. For this purpose, differences in trade relations are described and assessed between a base-case or ?do nothing? scenario and a road fee-charge setting scenario. The results show that the specific amount of the charge set for HGVs affect each region differently and to a different extent because in some regions the price of commodities and the Generalized Transport Cost will decrease its competiveness within the country.