Concurrent tabling

In the past few years Tabling has emerged as a powerful logic programming model. The integration of concurrent features into the implementation of Tabling systems is demanded by need to use recently developed tabling applications within distributed systems, where a process has to respond concurrently to several requests. The support for sharing of tables among the concurrent threads of a Tabling process is a desirable feature, to allow one of Tabling’s virtues, the re-use of computations by other threads and to allow efficient usage of available memory. However, the incremental completion of tables which are evaluated concurrently is not a trivial problem. In this dissertation we describe the integration of concurrency mechanisms, by the way of multi-threading, in a state of the art Tabling and Prolog system, XSB. We begin by reviewing the main concepts for a formal description of tabled computations, called SLG resolution and for the implementation of Tabling under the SLG-WAM, the abstract machine supported by XSB. We describe the different scheduling strategies provided by XSB and introduce some new properties of local scheduling, a scheduling strategy for SLG resolution. We proceed to describe our implementation work by describing the process of integrating multi-threading in a Prolog system supporting Tabling, without addressing the problem of shared tables. We describe the trade-offs and implementation decisions involved. We then describe an optimistic algorithm for the concurrent sharing of completed tables, Shared Completed Tables, which allows the sharing of tables without incurring in deadlocks, under local scheduling. This method relies on the execution properties of local scheduling and includes full support for negation. We provide a theoretical framework and discuss the implementation’s correctness and complexity. After that, we describe amethod for the sharing of tables among threads that allows parallelism in the computation of inter-dependent subgoals, which we name Concurrent Completion. We informally argue for the correctness of Concurrent Completion. We give detailed performance measurements of the multi-threaded XSB systems over a variety of machines and operating systems, for both the Shared Completed Tables and the Concurrent Completion implementations. We focus our measurements inthe overhead over the sequential engine and the scalability of the system. We finish with a comparison of XSB with other multi-threaded Prolog systems and we compare our approach to concurrent tabling with parallel and distributed methods for the evaluation of tabling. Finally, we identify future research directions.

Derivation methods for hybrid knowledge bases with rules and ontologies

Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática

Automatic sleep apnea detection and sleep classification using the ECG and the SpO2 signals

Dissertation for a Masters Degree in Computer and Electronic Engineering

O reconhecimento de si no cyborg: Uma análise cinematográfica das implicações sociais do surgimento do pós-humano

Dissertação apresentada para cumprimento dos requisitos necessários à obtenção do grau de Mestre em Ciências da Comunicação

Vertente transatlântica do ELSJ: pode a UE ser Norm-Maker?

Dissertação apresentada para cumprimento dos requisitos necessários à obtenção do grau de Mestre em Estudos Europeus

The tight grip of a debt based global economy: A study on banking regulation and the implementation of the Basel II Accord in Portugal

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

A volumetric hybrid representation for obstacle detection in all-terrain robots

This dissertation presents an approach aimed at three-dimensional perception’s obstacle detection on all-terrain robots. Given the huge amount of acquired information, the adversities such environments present to an autonomous system and the swiftness, thus required, from each of its navigation decisions, it becomes imperative that the 3-D perceptional system to be able to map obstacles and passageways in the most swift and detailed manner. In this document, a hybrid approach is presented bringing the best of several methods together, combining the lightness of lesser meticulous analyses with the detail brought by more thorough ones. Realizing the former, a terrain’s slope mapping system upon a low resolute volumetric representation of the surrounding occupancy. For the latter’s detailed evaluation, two novel metrics were conceived to discriminate the little depth discrepancies found in between range scanner’s beam distance measurements. The hybrid solution resulting from the conjunction of these two representations provides a reliable answer to traversability mapping and a robust discrimination of penetrable vegetation from that constituting real obstructions. Two distinct robotic platforms offered the possibility to test the hybrid approach on very different applications: a boat, under an European project, the ECHORD Riverwatch, and a terrestrial four-wheeled robot for a national project, the Introsys Robot.

Humor and the framing of the public sphere and public opinion in Portugal (1797-1834)

In his Answer to the Question: What is Enlightenment (1784), Kant puts forward his belief that the vocation to think freely, which humankind is endowed with, is bound to make sure that “the public use of reason” will at last act “even on the fundamental principles of government and the state [will] find it agreeable to treat man – who is now more than a machine – in accord with his dignity”. The critical reference to La Mettrie (1747), by opposing the machine to human dignity, will echo, in the dawn of the 20th century, in Bergson’s attempt to explain humor. Besides being exclusive to humans, humor is also a social phenomenon. Freud (1905) assures that pleasure originated by humor is collective, it results from a “social process”: jokes need an audience, a “third party”, in order to work and have fun. Assuming humor as a social and cultural phenomenon, this paper intends to sustain that it played a role in the framing of the public sphere and of public opinion in Portugal during the transition from Absolute Monarchy to Liberalism. The search for the conditions which made possible the critical exercise of sociability is at the root of the creation of the public sphere in the sense developed by Habermas (1962), whose perspective, however, has been questioned by those who point 2 out the alleged idealism of the concept – as opposed, for example, to Bakhtin (1970), whose work stresses diversity and pluralism. This notwithstanding, the concept of public sphere is crucial to the building of public opinion, which is, in turn, indissoluble from the principle of publicity, as demonstrated by Bobbio (1985). This paper discusses the historical evolution of the concept of public opinion from Ancient Greece doxa, through Machiavelli’s “humors” (1532), the origin of the expression in Montaigne (1580) and the contributions of Hobbes (1651), Locke (1690), Swift (1729), Rousseau (1762) or Hume (1777), up to the reflection of Lippman (1922) and Bourdieu’s critique (1984). It maintains that humor, as it appears in Portuguese printed periodicals from 1797 (when Almocreve de Petas was published for the first time) to the end of the civil war (1834) – especially in those edited by José Daniel Rodrigues da Costa but also in O Piolho Viajante, by António Manuel Policarpo da Silva, or in the ones written by José Agostinho de Macedo, as well as in a political “elite minded” periodical such as Correio Braziliense –, contributed to the framing of the public sphere and of public opinion in Portugal.

Integrated data model and DSL modifications

Companies are increasingly more and more dependent on distributed web-based software systems to support their businesses. This increases the need to maintain and extend software systems with up-to-date new features. Thus, the development process to introduce new features usually needs to be swift and agile, and the supporting software evolution process needs to be safe, fast, and efficient. However, this is usually a difficult and challenging task for a developer due to the lack of support offered by programming environments, frameworks, and database management systems. Changes needed at the code level, database model, and the actual data contained in the database must be planned and developed together and executed in a synchronized way. Even under a careful development discipline, the impact of changing an application data model is hard to predict. The lifetime of an application comprises changes and updates designed and tested using data, which is usually far from the real, production, data. So, coding DDL and DML SQL scripts to update database schema and data, is the usual (and hard) approach taken by developers. Such manual approach is error prone and disconnected from the real data in production, because developers may not know the exact impact of their changes. This work aims to improve the maintenance process in the context of Agile Platform by Outsystems. Our goal is to design and implement new data-model evolution features that ensure a safe support for change and a sound migration process. Our solution includes impact analysis mechanisms targeting the data model and the data itself. This provides, to developers, a safe, simple, and guided evolution process.

Estudo de viabilidade da valorização de resíduos da cultura do arroz por co-pirólise e co-gasificação para a produção de energia renovável

Anualmente, milhares de toneladas de resíduos agrícolas são gerados no mundo, sendo a cultura do arroz uma das que mais contribui para a sua produção, especialmente com casca e palha de arroz, além dos plásticos gerados nas etapas de colheita, transporte e transformação do produto. Tradicionalmente estes resíduos são descartados ou aproveitados através de vias pouco eficientes, com consequências negativas para o ambiente. Múltiplas tecnologias têm sido estudadas e desenvolvidas para assim transformar estes resíduos em produtos de interesse: (i) gasificação, (ii) combustão e (iii) pirólise. Na presente dissertação foi avaliada a viabilidade da construção duma central de valorização de resíduos da cultura de arroz, em Portugal, através das tecnologias de co-gasificação e co-pirólise. Considerou-se que o gás de síntese, gerado na co-gasificação, é utilizado para produzir energia elétrica, e que o bio-óleo, gerado na co-pirólise, é utilizado para produzir energia elétrica ou para ser vendido a uma refinaria. A avaliação foi realizada com base no capital total de investimento, nos custos de operação e na renda gerada pela venda (i) de energia elétrica ou (ii) do bio-óleo. Com os indicadores económicos analisados, conclui-se que em Portugal nenhuma das duas tecnologias é viável, principalmente devido (i) às reduzidas quantidades de resíduos originados pela cultura de arroz neste país e (ii) aos elevados custos de transporte da matéria-prima. Caso fosse feito o aproveitamento da quantidade total de plásticos provenientes do fluxo agrícola português (4 782 t.ano-1), a construção duma central de co-pirólise seria rentável, obtendo-se uma taxa interna de rentabilidade de 69% para a venda de energia elétrica e 23,5% para venda de bio-óleo.

Rely-guarantee protocols for safe interference over shared memory

Mutable state can be useful in certain algorithms, to structure programs, or for efficiency purposes. However, when shared mutable state is used in non-local or nonobvious ways, the interactions that can occur via aliases to that shared memory can be a source of program errors. Undisciplined uses of shared state may unsafely interfere with local reasoning as other aliases may interleave their changes to the shared state in unexpected ways. We propose a novel technique, rely-guarantee protocols, that structures the interactions between aliases and ensures that only safe interference is possible. We present a linear type system outfitted with our novel sharing mechanism that enables controlled interference over shared mutable resources. Each alias is assigned separate, local roles encoded in a protocol abstraction that constrains how an alias can legally use that shared state. By following the spirit of rely-guarantee reasoning, our rely-guarantee protocols ensure that only safe interference can occur but still allow many interesting uses of shared state, such as going beyond invariant and monotonic usages. This thesis describes the three core mechanisms that enable our type-based technique to work: 1) we show how a protocol models an alias’s perspective on how the shared state evolves and constrains that alias’s interactions with the shared state; 2) we show how protocols can be used while enforcing the agreed interference contract; and finally, 3) we show how to check that all local protocols to some shared state can be safely composed to ensure globally safe interference over that shared memory. The interference caused by shared state is rooted at how the uses of di↵erent aliases to that state may be interleaved (perhaps even in non-deterministic ways) at run-time. Therefore, our technique is mostly agnostic as to whether this interference was the result of alias interleaving caused by sequential or concurrent semantics. We show implementations of our technique in both settings, and highlight their di↵erences. Because sharing is “first-class” (and not tied to a module), we show a polymorphic procedure that enables abstract compositions of protocols. Thus, protocols can be specialized or extended without requiring specific knowledge of the interference produce by other protocols to that state. We show that protocol composition can ensure safety even when considering abstracted protocols. We show that this core composition mechanism is sound, decidable (without the need for manual intervention), and provide an algorithm implementation.

Bias in returns to tenure when firm wages and employment comove: A quantitative assessment and solution

It is well known that, unless worker-firm match quality is controlled for, returns to firm tenure (RTT) estimated directly via reduced form wage (Mincer) equations will be biased. In this paper we show that even if match quality is properly controlled for there is a further pervasive source of bias, namely the co-movement of firm employment and firm wages. In a simple mechanical model where human capital is absent and separation is exogenous we show that positively covarying shocks (either aggregate or firm level) to firms employment and wages cause downward bias in OLS regression estimates of RTT. We show that the long established procedures for dealing with "traditional" RTT bias do not circumvent the additional problem we have identified. We argue that if a reduced form estimation of RTT is undertaken, firm-year fixed effects must be added in order to eliminate this bias. Estimates from two large panel datasets from Portugal and Germany show that the bias is empirically important. Adding firm-year fixed effects to the regression increases estimates of RTT in the two respective countries by between 3.5% and 4.5% of wages at 20 years of tenure over 80% (50%) of the estimated RTT level itself. The results extend to tenure correlates used in macroeconomics such as the minimum unemployment rate since joining the firm. Adding firm-year fixed effects changes estimates of these effects also.