Technical reports

This paper addresses special cases of the robust network design problem under the single-source Hose model. We show that, in the case of unitary bounds, the static and the dynamic routing approaches lead to the same optimal solution, and this is true for both the splittable and the unspittable scenarios. As a consequence, in such a special case, the robust network design problem with (splittable) dynamic routing is polynomially solvable, whereas the problem is coNP-Hard under the general single-source Hose model. The results are based on the fact that the single-source Hose polyhedron with unitary bounds is dominated by a polynomial number of demand vectors. A feasible static routing can then be constructed as a convex combination of a set of routing templates which are feasible for the dominant demand vectors. The equivalence between static and dynamic routing is a consequence of those results, and it can also be generalized to some single-source Hose cases with non unitary bounds.

Calculi that feature resource-allocating constructs (e.g. the pi-calculus or the fusion calculus) require special kinds of models. The best-known ones are presheaves and nominal sets. But named sets have the advantage of being finite in a wide range of cases where the other two are in finite. The three models are equivalent. Finiteness of named sets is strictly related to the notion of finite support in nominal sets and the corresponding presheaves. We generalise previous equivalence results by introducing a notion of minimal support in presheaf categories indexed over small categories of monos. We show that nominal sets are generalisd by families, that is, free coproduct completions, indexed by symmetries.

Several complex and time-critical applications require the existence of novel distributed, heterogeneous and dynamic platforms composed of a variety of fixed and mobile processing nodes and networks. Such platforms, that can be called Pervasive Mobile Grids, aim to merge the features of Pervasive Computing and High-performance Grid Computing onto a new emerging paradigm. In this Chapter we study a methodology for designing high-performance distributed computations, able to exploit the heterogeneity and dynamicity of Pervasive Grids, by expressing Adaptivity and Context Awareness directly at the application level. We describe a programming model approach, and we compare it with other existing research works in the field of Pervasive Mobile Computing, discussing the rationales of the requirements and the features of a novel programming model for the target platforms and applications. In order to exemplify the proposed methodology we introduce our evaluation framework ASSISTANT, and we provide some interesting future directions in this research field.

Service composition concerns both integration of heterogeneous distributed applications and dynamic selection of services. QoS-aware selection enables a service requester with certain QoS requirements to classify services according to their QoS guarantees. In this paper we present a method that allows for a fuzzy-valued description of QoS parameters. Fuzzy sets are suited to specify both the QoS preferences raised by a service requester such as `response time must be as lower as possible and cannot be more that 1000ms' and approximate estimates a provider can make on the QoS capabilities of its services like `availability is roughly between 95% and 99%'. We propose a matchmaking procedure based on a fuzzy-valued similarity measure that, given the specifications of QoS parameters of the requester and the providers, selects the most appropriate service among several functionally-equivalent ones, using a fuzzy ordering relation. We also devise a method for dynamical update of service offers by means of runtime monitoring of the actual QoS performance.

Echo State Networks (ESNs) represent an emerging paradigm for modeling Recurrent Neural Networks (RNNs).In this report we try to identify and investigate some of the main aspects that can be accounted for the success and limitations of this class of models.Independently of the architectural design, we first show the effect on ESNs behavior due to the contractivity of the state transition function and the related Markovian bias.The purpose of our study is also to give an insight on how and why a larger reservoir may improve the predictive performance. We identify four key factors which can influence the performance of ESNs: input variability, multiple time-scales dynamics, non-linear interactions among units and regression in a high dimensional state space. Several variants of the basic ESN model are introduced in order to study these main factors. The proposed variants are tested on four datasets: the Mackey-Glass chaotic time series, the 10th order NARMA system, and two predictive tasks on a symbolic sequence domain with Markovian/anti-Markovian flavor. Experimental evidence shows that all the key identified factors have a major role in determining ESN performances.

Complex, hierarchical, multi-scale industrial and natural systems generate increasingly large mathematical models. I-DARE is a structure-aware modeling-reformulating-solving environment based on Declarative Programming, that allows the construction of complex structured models. The main aim of the system is to produce models that can be automatically and algorithmically reformulated to search for the ''best'' formulation, intended as the one for which the most efficient solution approach is available. This requires exploration of a high-dimensional space comprising all (structured) reformulations of a given instance, all available solvers for (each part of) the formulation, and all possible configurations of the relevant algorithmic parameters for each solver. A fundamental pre-requisite for this exploration is the ability to predict the efficiency of a given (set of) algorithm(s), considering their configuration(s), for a given instance; this is, however, a vastly nontrivial task. This article describes how the I-DARE system organizes the information on the instance at hand in order to make the search in the (formulation, solver, configuration) space possible with several different exploration techniques. In particular, we propose a way to combine general machine learning mechanisms and ad-hoc methods, where available, in order to effectively compute the "objective function" of the search, i.e., the prediction of the effectiveness of a point in the space. We also discuss how this mechanism can take upon itself part of the exploration, the one in the sub-space of configurations, thus simplifying the task to the rest of the system by reducing the dimensionality of the search space it has to traverse.

Complex, hierarchical, multi-scale industrial and natural systems generate increasingly large mathematical models. Practitioners are usually able to formulate such models in their ''natural'' form; however, solving them often requires finding an appropriate reformulation to reveal structures in the model which make it possible to apply efficient, specialized approaches. I-DARE is a structure-aware modeling-reformulation-solving environment based on Declarative Programming. It allows the construction of complex structured models, that can be automatically and algorithmically reformulated to search for the best formulation, intended as the one for which the most efficient solution approach is available. In order to accommodate (potentially) all possible specialized solution methods, it defines a general software framework for solvers, that are ''registered'' to specific problem structures. This article describes in details the application of Artificial Intelligence in the modeling and reformulation modules of I-DARE, showing how Declarative Programming can be used to design a structure-aware modeling environment that allows for a new automatic reformulation methodology.

In stencil based parallel applications, communications represent the main overhead, especially when targeting a fine grain parallelization in order to reduce the completion time. Techniques that minimize the number and the impact of communications are clearly relevant. In literature the best optimization reduces the number of communications per step from <span style="font-style: italic;">3</span><sup style="font-style: italic;">dim</sup>, featured by a naive implementation, to <span style="font-style: italic;">2*dim</span>, where <span style="font-style: italic;">dim</span> is the number of the domain dimensions. To break down the previous bound, in the paper we introduce and formally prove <span style="font-style: italic;">Q-transformations</span>, for stencils featuring data dependencies that can be expressed as geometric affine translations. <span style="font-style: italic;">Q-transformations</span>, based on data dependencies orientations though space translations, lowers the number of communications per step to <span style="font-style: italic;">dim</span>.

A tool for extracting sequential patterns with temporal and content constraints from logs is presented. The heart of the tool is a new algorithm capable of handling temporal constraints and itemsets with multiple occurrences of the same item. Applications of the system are discussed in the context of monitoring logs registered by a platform supporting distributed processes, developed within the European project BRITE.

Hermitian plus possibly unhermitian low rank matrices can be efficiently reduced into Hessenberg form. The resulting Hessenberg matrix can still be written as the sum of a Hermitian plus low rank matrix. In this paper we develop a new implicit multishift QR-algorithm for Hessenberg matrices, which are the sum of a Hermitian plus a possibly non-Hermitian low rank correction.The proposed algorithm exploits both the symmetry and low rank structure to obtain a QR-step involving only O(n) floating point operations instead of the standard O(n^2) operations needed for performing a QR-step on a Hessenberg matrix. The algorithm is based on a suitable O(n) representation of the Hessenberg matrix. The low rank parts present in both the Hermitian and low rank part of the sum are compactly stored by a sequence of Givens transformations and few vectors. Due to the new representation, we cannot apply classical deflation techniques for Hessenberg matrices. A new, efficient technique is developed to overcome this problem. Some numerical experiments based on matrices arising in applications are performed.The experiments illustrate effectiveness and accuracy of both the $QR$-algorithm and the newly developed deflation technique.

Many financial optimization problems involve future values of security prices, interest rates and exchange rates which are not known in advance, but can only be forecasted or estimated. Such problems fit perfectly into the framework of Robust Optimization that, given optimization problems with uncertain parameters, looks for solutions that will achieve good objective function values for the realization of these parameters in given uncertainty sets.In finance, Robust Optimization offers vehicles to incorporate the estimation of uncertain parameters into the decision making process.This is true, for example, in portfolio asset allocation. Starting from the robust counterparts of the classical mean-variance portfolio problems, in this paper we review some mathematical models that have been recently proposed in the literature to address uncertainty in portfolio asset allocation problems. For some of these, we focus also on algorithmic approaches and computataional issues. Finally, we analyze the relationship between robustness and risk measures.

Si presentano alcuni semplici teoremi per risolvere le relazioni di ricorrenza lineari, bilanciate e di ordine costante, che rappresentano il tempo di funzionamento dei piu' comuni algoritmi ricorsivi.

In this technical report we describe a certain number of models of auctions barters and propose the associated procedures. In this way we face the problem of the fair sharing of goods, bads and possibly services (also collectively termed as) among a set of players that cannot or do not want to use a common cardinal scale for the evaluation of the items owing to the very qualitative and non economical nature of the items themselves.

Here we report a preliminary analysis of transposons Long Terminal Repeats (LTR) within several yeast strains.

Breast cancer represents a real emergency in many European and North American countries. In order to detect the diseases as soon as it starts developing, many countries have organized screening programs aimed to women monitoring. Traditional imaging modalities, like X-Ray mammography, do not provide certain and reliable results on young women or in women who underwent surgical interventions. Three-dimensional breast MRI has proven to be a valuable tool for disambiguate uncertain mammographic findings and for the pre-operative planning. However, in order for MRI of the breast to be effective, a contrast agent, highlighting areas with a high degree of vascularization, needs to be used. The full breast volume needs to be acquired once before and several times after the contrast agent injection. A contrast-enhance MR examination of the breast contains hundreds of images that must be inspected carefully. Automatic approaches to breast cancer detection can help radiologists in this hard tasks and speed up the inspection process. In this paper we present a survey of automatic approaches to breast cancer detection in MRI. We discuss both registration algorithms needed to align corresponding images acquired at different instants in time and classification algorithms able to label a suspicious area according to features automatically computed from the images.

We propose a methodology for statically predicting the possible interaction patterns of services within a given choreography.We focus on choreographies exploiting the event notification paradigm to manage service interactions. Control Flow Analysis techniques statically approximate which events can be delivered to match the choreography constraints and how the multicast groups can be optimised to handle event notification within the service choreography.

Shared memory multiprocessors come back to popularity thanks to rapid spreading of commodity multi-core architectures. As ever, shared memory programs are fairly easy to write and quite hard to optimise; providing multi-core programmers with optimising tools and programming frameworks is a nowadays challenge. Few efforts have been done to support effective streaming applications on these architectures. In this paper we introduce FastFlow, a low-level programming framework based on lock-free queues explicitly designed to support high-level languages for streaming applications. We compare FastFlow with state-of-the-art programming frameworks such as Cilk, OpenMP, and Intel TBB. We experimentally demonstrate that FastFlow is always more efficient than all of them in a set of micro-benchmarks and on a real world application; the speedup edge of FastFlow over other solutions might be bold for fine grain tasks, as an example +35% on OpenMP, +226% on Cilk, +96% on TBB for the alignment of protein P01111 against UniProt DB using Smith-Waterman algorithm.

This paper presents a bottom up strategy to detect features in genomic sequences.

XML is the standard language for representing semi-structured data. With the spreading of XML sources, mining XML data can be an important objective in the near future. This paper presents a project focussed on designing a general-purpose query language in support of mining XML data. In our framework, raw data, mining models and domain knowledge are represented by way of XML documents and stored inside XML native databases. Data mining tasks are expressed in an extension of XQuery. Special attention is given to the frequent pattern discovery problem, and a way of exploiting domain-dependent optimizations and efficient data structures as deeper as possible in the extraction process is presented. We report the results of a first bunch of experiments, showing that a good trade-off between expressiveness and efficiency in XML data mining is not a chimera.

This note contains the abstracts of the seven posters presented the 7th Conference on Computational Methods in Systems Biology, CMSB 2009, held in Bologna, August 31st - September 1st, 2009.

We introduce and address the problem of concurrent autonomic management of different non-functional concerns in parallel applications build as a hierarchical composition of behavioural skeletons. We first define the problems arising when multiple concerns are dealt with by independent managers, then we propose a methodology supporting coordinated management, and finally we discuss how autonomic management of multiple concerns may be implemented in a typical use case. The paper concludes with an outline of the challenges involved in realizing the proposed methodology on distributed target architectures such as clusters and grids. Being based on the behavioural skeleton concept proposed in the CoreGRID GCM, it is anticipated that the methodology will be readily integrated into the current reference implementation of GCM based on Java ProActive and running on top of major grid middlewares.

The paper adds a mechanism of {\em closure} to Java. We apply to closures the same technique we exploited in extending Java with methods as parameters \cite{bellia2008,bellia2008c} and we obtain a formal definition and a prototype of Java with closures. The formal definition consists of a set of source to source translation rules that state the meaning of the new construct in terms of compositions of well known ordinary Java structures. Two variants of the transformation are discussed to allow recursive defined closures and other mechanisms. The notion of {\em shared variable} as a local variable that is allocated in the heap is also discussed. Eventually, since the resulting transformation is one pass process, it can be implemented through a source to source, one pass, preprocessor \cite{bellia2007,bellia2008b}, easy to write using standard development tools \cite{levine1995,donnely2006}.

In this paper, we first give a quick review of the most used numerical indicators for evaluating research, and then we present an integrated model for ranking scientific publications together with authors and journals. Our model relies on certain adiacency matrices obtained from the relations of citation, authorship and publication. These matrices are first normalized to obtain stochastic matrices and then are combined together by means of weights to form a suitable irreducible stochastic matrix whose dominant eigenvector provides the ranking. We discuss various strategies for choosing the weights and we show on large synthetic datasets how the choice of a weighting criteria rather than another can change the behavior of our ranking algorithm.

PREFACE TERMGRAPH 2009 took place in York (UK) on March 22, 2009, as a one-day satellite event of ETAPS 2009. Previous editions of the TERMGRAPH workshops series took place in Barcelona (2002), in Rome (2004), in Vienna (2006), and in Braga (2007). The advantage of computing with graphs rather than terms (strings or trees) is that common subexpressions can be shared, which improves the efficiency of computations in space and time. Sharing is ubiquitous in implementations of programming languages: many implementations of functional, logic, object-oriented and concurrent calculi are based on term graphs. Term graphs are also used in symbolic computation systems and automated theorem proving. The aim of TERMGRAPH 2009 was to bring together researchers working in these different domains and to foster their interaction, to provide a forum for presenting new ideas and work in progress, and to enable newcomers to learn about current activities in term graph rewriting. Topics of interest for the workshop are all aspects of term graphs and sharing of common subexpressions in rewriting, programming, automated reasoning and symbolic computation. This includes (but is not limited to) term rewriting, graph transformation, programming languages, models of computation, graph-based languages, semantics and implementation of programming languages, compiler construction, pattern recognition, databases, bioinformatics, and system descriptions. This report contains the eight contributions presented during the workshop: they were selected by the Program Committee according to originality, significance, and general interest. In addition to these presentations, the programme included two invited lectures by Helene Kirchner and Fabio Gadducci.