Search

The twenty-ninth edition of the SEBD (Italian Symposium on Advanced Database Systems), held on 5-9 September 2021 in Pizzo (Calabria Region, Italy), included a joint seminar on “Reminiscence of TIDB 1981” with invited talks given by some of the participants to the Advanced Seminar on Theoretical Issues in Databases (TIDB), which took place in the same region exactly forty years earlier. The joint seminar was concluded by a Panel on “The Past and the Future of Computer Science Theory” with the participation of four distinguished computer science theorists (Ronald Fagin, Georg Gottlob, Christos Papadimitriou and Moshe Vardi), who were interviewed by Giorgio Ausiello, Maurizio Lenzerini, Luigi Palopoli, Domenico Saccà and Francesco Scarcello. This paper reports the summaries of the four interviews.

This research aims to highlight, starting from a historical analysis of the Pompeian Road network, the use of the technological solution of the beaten earth. Particular attention is paid to this pavement’s solution because various stratifications study that followed one another in the years preceding the most famous Plinian eruption that buried Pompeii. The reading of the vertical strati-fications of beaten, shows high compactness and hardness, which preludes to characteristics of good resistance to stress. In addition, the tests document traces of wear induced by the passage of the wagons and offer the possibility of relating the number of layers overlapped with the time between the laying of the first beaten on the ground of the paleosoil and 79 AD.

Construction is always very open to the possibility of recycling, but papercrete, experimented with first in America in the 1930s and repurposed in the early 2000s, has not yet fully expressed its innovative power and has developed all the potential that is intrinsically linked to paper recycling. Papercrete is a particular lightened concrete, whose mechanical performances are very conditioned by the preparation of the paper pulp and by the operations that mark the mixture design. Attention is paid in particular to the definition of two mixtures of papercrete, the first one intended for brick construction as a light building material, the second intended for the creation of a mortar to lay bricks and prefigure the creation of a complete wall.

In several practical circumstances we have to solve a problem whose instance is not a priori completely known. Situations of this kind occur in computer systems and networks management, in financial decision making, in robotics etc. Problems that have to be solved without a complete knowledge of the instance are called on−line problems. The analysis of properties of on-line problems and the design of algorithmic techniques for their solution (on−line algorithms) have been the subject of intense study since the 70-ies, when classical algorithms for scheduling tasks in an on-line fashion [22] and for handling paging in virtual storage systems [11] have been first devised. In the 80-ies formal concepts for analyzing and measuring the quality of on-line algorithms have been introduced [40] and the notion of competitive analysis has been defined as the ratio between the value of the solution that is obtained by an on-line algorithm and the value of the best solution that can be achieved by an optimum off-line algorithm that has full knowledge of the problem instance. Since then a very broad variety of on-line problems have been addressed in the literature [14, 19]: memory allocation and paging, bin packing, load balancing in multiprocessor systems, updating and searching a data structure (e.g. a list), scheduling, financial investment, etc.

In this tutorial, we give an overview of several on-line optimization problems which involve some sort of exploration or chasing. We show how all the considered problems are part of the broad family of metrical service systems and discuss the known competitive analysis results and the mutual relationships between the problems.

This paper presents a general technique for obtaining new results pertaining to the non-finite axiomatizability of behavioral semantics over process algebras from old ones. The proposed technique is based on a variation on the classic idea of reduction mappings. In this setting, such reductions are translations between languages that preserve sound (in)equations and (in)equational proofs over the source language, and reflect families of (in)equations responsible for the non-finite axiomatizability of the target language. The proposed technique is applied to obtain a number of new non-finite axiomatizability theorems in process algebra via reduction to Moller’s celebrated non-finite axiomatizability result for CCS. The limitations of the reduction technique are also studied. This paper presents a general technique for obtaining new results pertaining to the non-finite axiomatizability of behavioral semantics over process algebras from old ones. The proposed technique is based on a variation on the classic idea of reduction mappings. In this setting, such reductions are translations between languages that preserve sound (in)equations and (in)equational proofs over the source language, and reflect families of (in)equations responsible for the non-finite axiomatizability of the target language. The proposed technique is applied to obtain a number of new non-finite axiomatizability theorems in process algebra via reduction to Moller’s celebrated non-finite axiomatizability result for CCS. The limitations of the reduction technique are also studied.

We present a probabilistic leader election algorithm for anonymous, bidirectional, asynchronous rings. It is based on an algorithm from Franklin, augmented with random identity selection, hop counters to detect identity clashes, and round numbers modulo 2. As a result, the algorithm is finite-state, so that various model checking techniques can be employed to verify its correctness, that is, eventually a unique leader is elected with probability one. We also sketch a formal correctness proof of the algorithm for rings with arbitrary size.

In this paper the problem of efficiently serving a sequence of requests presented in an on-line fashion located at points of a metric space is considered. We call this problem the On-Line Travelling Salesman Problem (OLTSP). It has a variety of relevant applications in logistics and robotics. We consider two versions of the problem. In the first one the server is not required to return to the departure point after all presented requests have been served. For this problem we derive a lower bound on the competitive ratio of 2 on the real line. Besides, a 2.5-competitive algorithm for a wide class of metric spaces, and a 7/3-competitive algorithm for the real line are provided. For the other version of the problem, in which returning to the departure point is required, we present an optimal 2-competitive algorithm for the above mentioned general class of metric spaces. If in this case the metric space is the real line we present a 1.75-competitive algorithm that compares with a \approx 1.64 lower bound.