Rapporti tecnici

In this paper we present a scenario analysis approach for water system planning and management under conditions of climatic and hydrological uncertainty. The scenario analysis approach examines a set of statistically independent hydrological scenarios, and exploits the inner structure of their temporal evolution in order to obtain a "robust" decision policy, so that that the risk of wrong decisions is minimised. In this approach, uncertainty is modelled by a scenario-tree in a multistage environment, which includes different possible configurations of inflows in a wide time-horizon. In this paper we propose a Decision Support System (DSS) that performs scenario analysis by identifying trends and essential features on which to base a robust decision policy. The DSS prevents obsolescence of optimiser codes, exploiting standard data format, and a graphical interface provides easy data-input and results analysis for the user. Results show that scenario analysis could be an alternative approach to stochastic optimisation when no probabilistic rules can be adopted and deterministic models are inadequate to represent uncertainty. Moreover, experimentation for a real water resources system in Sardinia, Italy, shows that practitioners and end-users can adopt the DSS with ease.

We study decidability of a logic for describing processes with restricted names. We choose a minimal fragment of the Ambient Logic, but the techniques we present should apply to every logic which uses Cardelli and Gordon revelation and hiding operators, and Gabbay and Pitts freshness quantifier. We start from the static fragment of ambient logic that Calcagno Cardelli and Gordon proved to be decidable. We prove that the addition of a hiding quantifier makes the logic undecidable. Hiding can be decomposed as freshness plus revelation. Quite surprisingly, freshness alone is decidable, but revelation alone is not.

Passengers on a transit network with common lines are often faced with the problem of choosing between either to board the arriving bus or to wait for a faster one. Many existing assignment models are based on the classical assumption that at a given stop passengers board the first arriving carrier of a certain subset of available lines. It has been shown that, in this case, an {\it optimal subset} of lines that minimizes the passenger travel times exists and is easily determined if the headway distributions are exponential. However, when on-line information on future arrivals of buses are posted at various stops, it is unlikely that the above classical assumption holds. Passengers may choose in this case to board a line that offers the best combination of waiting time and expected remaining time. We propose in this paper a general framework for determining the probability of boarding each available line at a stop when on-line information on bus arrivals is provided to passengers. We will also show that the classical case without on-line information may be interpreted as a particular instance of the proposed framework, and thus extend the results obtained with exponential distributions to generaldistributions. Numerical examples, based on various headway distributions proposed in the literature, will be used to illustrate the combined impacts of the regularity of transit lines and of the availability of information regarding bus arrivals at stops on the line loads and on the passenger travel times.

Behavioural equivalences on open systems are usually defined by comparing system behaviour in all environments. Here, we introduce a hierarchy of behavioural equivalences for open systems in the setting of process calculi, building on a symbolic approach proposed in a previous paper. The hierarchy comprises both branching, bisimulation-based, and non-branching, trace-based, equivalences. Symbolic equivalences are amenable to effective analysis techniques (e.g., the symbolic transition system is finitely branching under mild assumptions), which result to be correct, but often not complete due to redundant information. Two kinds of redundancy, syntactic and semantic, are discussed and one class of symbolic equivalences is identified that deals satisfactorily with syntactic redundant transitions, which are a primary source of incompleteness.

This paper concerns the study of a unitary transformation from a generic symmetric matrix $A$ into a semiseparable matrix. The problem is studied both theoretically and from an algorithmic point of view. In particular, we first give a proof of the existence of such a transformation and then we discuss the uniqueness of such transformation proving an Implicit-$Q$ Theorem for semiseparable matrices. Finally, we study structural properties of the factors of the $QR$-decomposition of a semiseparable matrix. These properties allows us to design a method based on the $QR$ iterations applied to a semiseparable matrix for reducing a symmetric matrix to semiseparable form. This method has the same asymptotic cost of the reduction of a symmetric matrix to tridiagonal form. Once the transformation has been accomplished, if one is interested in computing the eigenvalues each further $QR$ iteration can be done in linear time.

In this paper we give a positive answer to the long-standing problem of finding an in-place sorting algorithm performing $O(n\log n)$ comparisons and $O(n)$ data moves in the worst case. So far, the better in-place sorting algorithm with $O(n)$ moves was proposed by Munro and V. Raman. Their algorithm requires $O(n^{1+\epsilon})$ comparisons in the worst case, for any $\epsilon > 0$. Later, Katajainen and Pasanen discovered the first in-place algorithm with $O(n\log n)$ comparisons and $o(n\log n)$ moves, namely $O(n\log n/\log\log n)$ moves. Our algorithm achieves the same number of comparisons but with $O(n)$ moves, which is asymtotically optimal.

MAJA is a package for MAtrix computation in JAva. The package allows defining various kinds of structured matrices operating in an unified way; General, Symmetric, Sparse, Band, Toeplitz, Circulant matrices are implemented among the others. It is possible also to operate on Block matrices, Additive Structures, Tensor Products, Implicit Inverses and so on. The package organization is similar to the Java Collections API. It is easy to exploit the presence of more than one processor without affecting the final user code. The source code is platform independent and has been tested on Linux, Windows, and Macintosh computers; test benchmarks are presented, both on single and double-processor computers. Also examples of implementation of involved linear algebra algorithms are presented.

In this paper we provide the first compression booster that turns a zeroth order compressor into a more effective $k$-th order compressor without any loss in the time and space efficiency. More precisely, let $\alg$ be an algorithm that compresses a string~$s$ within $\lambda |s| \hlk{0}(s) + \mu$ bits of storage in $\Ob{T(|s|)}$ time, where $\hlk{0}(s)$ is the zeroth order entropy of the string $s$. Our booster improves $\alg$ by compressing~$s$ within $\lambda |s| \hlk{k}(s) + \log_2 |s| + g_k$ bits still using $O(T(|s|))$ time, where $\hlk{k}(s)$ is the $k$-th order entropy of~$s$. The idea of a ``compression booster'' has been very recently introduced by Giancarlo and Sciortino in [CPM 2003]. They combined the Burrows-Wheeler Transform with dynamic programming and achieved our same compression bound but with running time $O(T(|s|)) + \Omega(|s|^2)$. We start from the same premises of Giancarlo and Sciortino, but instead of using dynamic programming we design a linear time optimization algorithm based on novel structural properties of the Burrows-Wheeler Transform.

In questo lavoro viene analizzato in dettaglio il fenomeno dell'attesa a una fermata di un servizio di trasporto collettivo urbano, tenendo conto anche della regolarità del passaggio dei veicoli di una stessa linea alla fermata. Viene proposto un modello, detto "dinamico" , che permette di eliminare le contraddizioni insite nel modello usualmente utilizzato. Viene mostrato anche un approccio algoritmico che permette di evitare la propagazione degli errori di approssimazione. Viene anche mostrato un adattamento del modello per quei servizi di trasporto collettivo in cui vi sia informazione all'utenza alle fermate, mediante le "paline intelligenti".

We introduce a high level declarative model for mobile and ad hoc computing. The model takes the form of a logical theory in a Unity-like linear time temporal logic and is specifically designed to deal with Network Awareness, Mobility, and Coordination. A companion design methodology based on formal refinements is also introduced in this paper. The model and its design methodology are validated through an illustrative case study, namely a system that coordinates the activities of mobile components over an ad hoc network.

Self-organization constitutes an important paradigm in machine learning with successful applications e.g. for data- and web-mining. However, so far most approaches have been proposed for data contained in a fixed and finite dimensional vector space. We will focus on extensions for more general data structures like sequences and tree structures in this article. Various extensions of the standard self-organizing map (SOM) to sequences or tree structures have been proposed in the literature: the temporal Kohonen map, the recursive SOM, and SOM for structured data (SOMSD), for example. These methods enhance the standard SOM by recursive connections. We define in this article a general recursive dynamic which enables the recursive processing of complex data structures based on recursively computed internal representations of the respective context. The above mechanisms of SOMs for structures are special cases of the proposed general dynamic, furthermore, the dynamic covers the supervised case of recurrent and recursive networks, too. The general framework offers a uniform notation for training mechanisms such as Hebbian learning and the transfer of alternatives such as vector quantization or the neural gas algorithm to structure processing networks. The formal definition of the recursive dynamic for structure processing unsupervised networks allows the transfer of theoretical issues from the SOM literature to the structure processing case. One can formulate general cost functions corresponding to vector quantization, neural gas, and a modification of SOM for the case of structures. The cost functions can be compared to Hebbian learning which can be interpreted as an approximation of a stochastic gradient descent. We derive as an alternative the exact gradients for general cost functions which can be computed in several ways similar to well-known learning algorithms for supervised recurrent and recursive networks. We afterwards discuss general design issues which should be taken into account when choosing internal representations and which limit the applicability of specific choices in concrete situations: We investigate the necessary cardinality of the set of internal representations, the tolerance with respect to noise, and the necessary of globality of processing. Finally, we discuss the issue of topology preservation of structure processing self-organizing maps and derive an explicit metric for a specific situation for SOMSD.

We study various uniform $k$-partition problems which consist in partitioning $m$ sets, each of cardinality $k$, into $k$ sets of cardinality $m$ such that each of these sets contains exactly one element from every original set. The problems differ according to the particular measure of "set uniformity" to be optimized. Most problems are polynomial and corresponding solution algorithms are provided. A few of them are proved to be NP-hard. Examples of applications to scheduling and routing problems are also discussed.

This paper presents Circe, an environment for the analysis of natural language requirements. Circe is presented in terms of its architecture, based on a transformational paradigm. Details are given for the various transformation steps, including (i) a novel technique for parsing natural language requirements, and (ii) an expert system based on modular agents, embodying intensional knowledge about software systems in general. Some of the features of the environment are shown by means of an example. Various stages of requirements analysis are covered, from initial sketches to pseudo-code and UML models.

In the last two decades, a number of algorithms for the linear single-commodity Min Cost Flow problem (MCF) have been proposed, and several efficient codes are available that implement different variants of the algorithms. The practical significance of the algorithms has been tested by comparing the time required by their implementations for solving ``from scratch'' instances of (MCF), of different classes, as the size of the problem (number of nodes and arcs) increases. However, in many applications several closely related instances of (MCF) have to be sequentially solved, so that reoptimization techniques can be used to speed up computations, and the most attractive algorithm is the one which minimizes the total time required to solve all the instances in the sequence. In this paper we compare the performances of four different efficient implementations of algorithms for (MCF) under cost reoptimization in the context of decomposition algorithms for the Multicommodity Min Cost Flow problem (MMCF), showing that for some classes of instances the relative performances of the codes doing ``from scratch'' optimization do not accurately predict the relative performances when reoptimization is used. Since the best solver depends both on the class and on the size of the instance, this work also shows the usefulness of a standard interface for (MCF) problem solvers that we have proposed and implemented.

The Weber point of a given point set $P$ is a point in the plane that minimizes the sum of all distances to the points in $P$. In general, the Weber point cannot be computed. However, if the points are in specific geometric patterns, then finding the Weber point is possible. We investigate the case of {\em biangular configurations}, where there is a center and two angles $\alpha$ and $\beta$ such that the angles w.r.t. the center between each two adjacent points is either $\alpha$ or $\beta$, and these angles alternate. We show that in this case the center of biangularity is the Weber point of the points, and that it can be found in time linear in the number of points.

We investigate the problem of determining the basis of repeated motifs with don't cares in an input string. We give new upper and lower bounds on the problem, introducing a new notion of basis that is provably smaller than (and contained in) previously defined ones. Our basis can be computed in less time and space, and is still able to generate the same set of motifs. We also prove that the number of motifs in all these bases grows exponentially with the quorum, the minimal number of times a motif must appear, which was unnoticed in previous work. We show that a polynomial-time algorithm exists only for fixed quorum.

In the classical dictionary problem, a set of $n$ distinct keys over an unbounded and ordered universe is maintained under insertions and deletions of individual keys while supporting search operations. An implicit dictionary has the additional constraint of occupying the space merely required by storing the~$n$~keys, that is, exactly $n$ contiguous words of space in total. All what is known is the starting position of the memory segment hosting the keys, as the rest of the information is implicitly encoded by a suitable permutation of the keys. This paper describes the flat implicit tree, which is the first implicit dictionary requiring $O(\log n)$ time per search and update operation.