On p-optimal proof systems and logics for PTIME

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

Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.

Learning the ropes and embracing the rules: CFSP institutions as arenas for learning and strategic socialisation

The aim of this article is to analyse those situations in which learning and socialisation take place within the context of the Common Foreign and Security Policy (CFSP), in particular, at the level of experts in the Council Working Groups. Learning can explain the institutional development of CFSP and changes in the foreign policies of the Member States. Some scope conditions for learning and channels of institutionalisation are identified. Socialisation, resulting from learning within a group, is perceived as a strategic action by reflective actors. National diplomats, once they arrive in Brussels, learn the new code of conduct of their Working Groups. They are embedded in two environments and faced with two logics: the European one in the Council and the national one in the Ministries of Foreign Affairs (MFA). The empirical evidence supports the argument that neither rational nor sociological approaches alone can account for these processes.

The Ideas Debate in International and European Studies: Towards a Cartography and Critical Assessment

The appeal to ideas as causal variables and/or constitutive features of political processes increasingly characterises political analysis. Yet, perhaps because of the pace of this ideational intrusion, too often ideas have simply been grafted onto pre-existing explanatory theories at precisely the point at which they seem to get into difficulties, with little or no consideration either of the status of such ideational variables or of the character or consistency of the resulting theoretical hybrid. This is particularly problematic for ideas are far from innocent variables – and can rarely, if ever, be incorporated seamlessly within existing explanatory and/or constitutive theories without ontological and epistemological consequence. We contend that this tendency along with the limitations of the prevailing Humean conception of causality, and associated epistemological polemic between causal and constitutive logics, continue to plague almost all of the literature that strives to accord an explanatory role to ideas. In trying to move beyond the current vogue for epistemological polemic, we argue that the incommensurability thesis between causal and constitutive logics is only credible in the context of a narrow, Humean, conception of causation. If we reject this in favour of a more inclusive (and ontologically realist) understanding then it is perfectly possible to chart the causal significance of constitutive processes and reconstrue the explanatory role of ideas as causally constitutive.

L'aprenentatge basat en problemes en models híbrids de docència-aprenentatge

La Facultat de Ciències de la Salut i de la Vida ha utilitzat des de 2004 la metodologia d'aprenentatge basat en problemes (en endavant ABP) com a mètode docent en els seus estudis de Biologia. En aquest període hem après algunes de les claus de l'aplicació del mètode en els nostres estudis. En primer lloc, cal disposar d'elements formatius que afavoreixin la formació dels tutors que participin en el projecte. Per assolir aquest objectiu hem dissenyat un portal on els nostres professors poden disposar de materials útils per a la seva activitat, així com de documents que permetin entendre millor el que suposa l'ABP. En segon lloc, el projecte tenia l'objectiu de dissenyar i avaluar activitats que permetessin integrar les pràctiques de laboratori en la lògica de la resolució de problemes pròpia de l'ABP. En aquest sentit vam dissenyar dues activitats en el tercer curs de la llicenciatura que anomenaren aprenentatge basat en el laboratori (ABL). Per aquest motiu es van dissenyar problemes que tinguessin una primera part de resolució a l'aula en grup de tutoria i una segona que obligués els estudiants a realitzar experiments de laboratori dirigits a entendre i resoldre les qüestions plantejades al grup de tutoria. L'ABL-1 fou un projecte de biologia cel·lular i destinat a aprofundir en els mecanismes implicats en els fenòmens de diferenciació dels miòcits. L'ABL-2 era un projecte conjunt dels professors de Fisiologia vegetal, Bioestadística i Microbiologia. En aquest cas es desitjava que els estudiants plantegessin la resolució a un problema que suposava la manipulació genètica de cèl·lules vegetals per fer possible que produïssin una substància específica, l'escopolamina. Finalment els estudiants havien d'escriure un article original com a projecte final de cada ABL. Els resultats dels dos anys d'experimentació han esta altament satisfactoris, d'acord amb les enquestes completades per alumnes i professors.

Les communautés bulu contre la plantation industrielle HEVECAM au Cameroun

In 1975 the Kribi region (Southern Cameroon) became host of the rubber plantation HEVECAM, the third largest employer in Cameroon. The establishment of the plantation has been preceded by the expropriation of customary land and by the destruction of the rainforest used by local populations. As a result, conflicts – mostly latent – pitting neighbouring Bulu communities against the plantation have occurred, especially during the last few years. Drawing on fieldwork data as well as on anthropological, economic and historical materials, I try to explore a new way of looking at such environmental conflicts by arguing that they reflect the struggle between two distinct institutional logics with different impacts on the environment, i.e. the logic of property versus the one of possession. In short, the logic of possession corresponds to a multi-functional community-based forest management, while the logic of property gave birth to the commercial monoculture model, the highest stage of the transformation of an ecosystem in order to match the requirements of property. It is argued that the conflict between the logic of possession and the logic of property is at the heart of many cases of “environmentalisms of the poor” that arise in reaction to “development”.

MEVA-Ambiental: MEtodologia per a la Valoració de l'Aprenentatge. Centrada en l'educació ambiental

Aquest projecte abasta el disseny i el desenvolupament d’un model prototípic de Metodologia per a la Valoració de l’Aprenentatge Ambiental, a la qual anomenem “MEVA-Ambiental”. Per a fer possible aquesta fita ens hem basat en fonaments ontològics i constructivistes per representar i analitzar el coneixement a fi de poder quantificar l’Increment de Coneixement (IC). Per nosaltres l’IC esdevé un indicador socio-educatiu que ens servirà per a determinar l’efectivitat dels tallers d’educació ambiental en percentatge. En procedir d’aquesta manera, les qualificacions resultats poden es poden prendre com punt de partida per a desenvolupar estudis en el temps i comprendre com “s’ancora” el nou coneixement a l’estructura cognitiva dels aprenents. Més enllà del plantejament teòric de mètode, també proveïm la solució tècnica que mostra com n’és de funcional i d’aplicable la part empírica metodològica. A aquesta solució que hem anomenat “MEVA-Tool”, és una eina virtual que automatitza la recollida i tractament de dades amb una estructura dinàmica basada en “qüestionaris web” que han d’emplenar els estudiants, una “base de dades” que acumula la informació i en permet un filtratge selectiu, i més “Llibre Excel” que en fa el tractament informatiu, la representació gràfica dels resultats, l’anàlisi i conclusions.

Mètodes algebraics i de teoria de la prova per a la formalització del raonament vague

Projecte de recerca elaborat a partir d’una estada a la Università degli studi di Siena, Italy , entre 2007 i 2009. El projecte ha consistit en un estudi de la formalització lògica del raonament en presència de vaguetat amb els mètodes de la Lògica Algebraica i de la Teoria de la Prova. S'ha treballat fonamental en quatre direccions complementàries. En primer lloc, s'ha proposat un nou plantejament, més abstracte que el paradigma dominant fins ara, per l'estudi dels sistemes de lògica borrosa. Fins ara en l'estudi d'aquests sistemes l'atenció havia recaigut essencialment en l'obtenció de semàntiques basades en tnormes contínues (o almenys contínues per l'esquerra). En primer nivell de major abstracció hem estudiat les propietats de completesa de les lògiques borroses (tant proposicionals com de primer ordre) respecte de semàntiques definides sobre qualsevol cadena de valors de veritat, no necessàriament només sobre l'interval unitat dels nombres reals. A continuació, en un nivell encara més abstracte, s’ha pres l'anomenada jerarquia de Leibniz de la Lògica Algebraica Abstracta que classifica tots els sistemes lògics amb un bon comportament algebraic i s'ha expandit a una nova jerarquia (que anomenem implicacional) que permet definir noves classes de lògiques borroses que contenen quasi totes les conegudes fins ara. En segon lloc, s’ha continuat una línia d'investigació iniciada els darrers anys consistent en l'estudi de la veritat parcial com a noció sintàctica (és a dir, com a constants de veritat explícites en els sistemes de prova de les lògiques borroses). Per primer cop, s’ha considerat la semàntica racional per les lògiques proposicionals i la semàntica real i racional per les lògiques de primer ordre expandides amb constants. En tercer lloc, s’ha tractat el problema més fonamental del significat i la utilitat de les lògiques borroses com a modelitzadores de (part de) els fenòmens de la vaguetat en un darrer article de caràcter més filosòfic i divulgatiu, i en un altre més tècnic en què defensem la necessitat i presentem l'estat de l'art de l'estudi de les estructures algèbriques associades a les lògiques borroses. Finalment, s’ha dedicat la darrera part del projecte a l'estudi de la complexitat aritmètica de les lògiques borroses de primer ordre.

A Comparative analysis of oil production setors in Saudi Arabia and the United Arab Emirates

Aquest article s'aplica un enfocament comparatiu de la gestió del sector petrolier en dos països rics en petroli a l'Orient Mitjà: Aràbia Saudita i els Emirats Àrabs Units (EAU). Més explícitament, s'examinen els factors que millor expliquen la variació en les estratègies que han vingut aplicant en el sector des de l'establiment de les seves empreses petrolieres nacionals (NOC). Recorrent a la literatura sobre expropiació / privatització en el camp d'Estudis de l'Energia, en aquest treball es proposa un marc teòric per analitzar la lògica que hi ha al darrera de les diferents formes d'exploració i les estratègies de producció en el sector petrolier. Teòricament, aquesta investigació té com a objectiu avançar en un conjunt d'eines d'anàlisi per abordar millor i entendre els determinants reals del procés de presa de decisions en el upstream. Empíricament, el model es prova en els casos divergents d'Aràbia Saudita i els Emirats Àrabs Units, i una sèrie de lliçons s'han extret. En última instància, aquest treball ha d'augmentar la conscienciació entre els erudits i els polític, tant sobre el poc coneixement que tenim sobre els mecanismes interns que impulsen les estratègies ascendents en el majors estats productor de petroli.

España y Suecia: apuntes comparativos sobre las políticas públicas para la implantación de la TDT

En este artículo se aportan algunos de los resultados preliminares de mi tesis doctoral: “Las políticas públicas de la televisión digital terrestre en la Unión Europea. Estudio comparado de Suecia y España”. Mediante el análisis de las estructuras institucionales implicadas en la transición analógico-digital de la plataforma de difusión terrestre, sus lógicas legitimadoras y las estrategias desarrolladas, se pretende contribuir a la identificación de buenas prácticas y de factores clave de éxito que ayuden a diseñar políticas públicas más efectivas.

Computing infinite plans for LTL goals using a classical planner

Classical planning has been notably successful in synthesizing finite plans to achieve states where propositional goals hold. In the last few years, classical planning has also been extended to incorporate temporally extended goals, expressed in temporal logics such as LTL, to impose restrictions on the state sequences generated by finite plans. In this work, we take the next step and consider the computation of infinite plans for achieving arbitrary LTL goals. We show that infinite plans can also be obtained efficiently by calling a classical planner once over a classical planning encoding that represents and extends the composition of the planningdomain and the B¨uchi automaton representingthe goal. This compilation scheme has been implemented and a number of experiments are reported.

Federalism and democracy. The case of minority nations: a federalist deficit

In this chapter, after pointing out the different logics that lie behind the familiar ideas of democracy and federalism, I have dealt with the case of plurinational federal democracies. Having put forward a double criterion of an empirical nature with which to differentiate between the existence of minority nations within plurinational democracies (section 2), I suggest three theoretical criteria for the political accommodation of these democracies. In the following section, I show the agonistic nature of the normative discussion of the political accommodation of this kind of democracies, which bring monist and pluralist versions of the demos of the polity into conflict (section 3.1), as well as a number of conclusions which are the result of a comparative study of 19 federal and regional democracies using four analytical axes: the uninational/plurinational axis; the unitarianism-federalism axis; the centralisation-decentralisation axis; and the symmetry-asymmetry axis (section 3.2). This analysis reveals shortcomings in the constitutional recognition of national pluralism in federal and regional cases with a large number of federated units/regions with political autonomy; a lower degree of constitutional federalism and a greater asymmetry in the federated entities or regions of plurinational democracies. It also reveals difficulties to establish clear formulas in these democracies in order to encourage a “federalism of trust” based on the participation and protection of national minorities in the shared government of plurinational federations/regional states. Actually, there is a federal deficit in this kind polities according to normative liberal-democratic patterns and to what comparative analysis show. Finally, this chapter advocates the need for a greater normative and institutional refinement in plurinational federal democracies. In order to achieve this, it is necessary to introduce a deeper form of “ethical” pluralism -which displays normative agonistic trends, as well as a more “confederal/asymmetrical” perspective, congruent with the national pluralism of these kind of polities.

Del patrimonio natural de los peces al patrimonio cultural del pescado: el Espai del Peix de Palamós

By submitting a brief example of the production process in the maritime heritage and fishing, we try to show that, among the different maritime heritage production processes that are occurring today in the Costa Brava (Catalonia, Spain), different “logics” are guiding these processes, which are causing a real transformation of the concept of maritime heritage and practices associated with it