### List of technical reports of year 2001

Scutellà, Maria Grazia
We show how the color-coding method by Alon, Yuster and Zwick, in its version specialized to compute simple paths of a specified cardinality k, can be extended to address the presence of arc lengths (the existence of such an extension was outlined by the authors for a more general color-coding algorithm, but it was not explicitely described, and its time complexity was not discussed). The extension is then used to derive approximation results for the general longest path problem. |

Ambrosino, D. and Scutellà, Maria Grazia
We study some complex distribution network design problems, which involve facility location, warehousing, transportation and inventory decisions. Several realistic scenarios are investigated. Two kinds of mathematical programming formulations are proposed for all the introduced problems, together with a proof of their correctness. Some formulations extend models proposed by Perl and Daskin (1985) for some warehouse location-routing problems; other formulations are based on flow variables and constraints. |

Bellia, Marco and Occhiuto, Maria Eugena
MGU(k-depth) is the family of problems, which contains, for each natural k, MGU restricted to inputs with depth no greater than k. MGU(k-breadth) is the family which, for each natural k, contains MGU restricted to inputs with breadth no greater than k. We prove that, for each k>1, MGUK(k-depth) equivalent (in LogSpace reduction) to MGU, and also MGU(k-breadth) equivalent (in LogSpace reduction) to MGU. This shows that bounds either on the depth or on the breadth of the input do not significantly speed up the computation of unification on PRAM machines. The paper concludes with a look at the design of parallel unification algorithms, and at unification on flat inputs. As a final contribution, we introduce a new algorithm which improves the performance of known algorithms for parallel unification and also computes in polylog PRAM Time on flat inputs. |

Giacobazzi, Roberto and Ranzato, Francesco and Scozzari, Francesca
Completeness is important in approximated semantics design by abstract interpretation, ensuring that abstract computations are as precise as possible wrt concrete ones. The authors recently proved that any abstract domain can be systematically refined or simplified in order to provide its closest possible complete domain. The key problem here remains is to find efficient and appropriate representations for objects in complete abstract domains. In this paper we show that these domain trensformations, when applied on abstract interpretations of quantales, can all be explicitly characterized by elegant linear logic-based formulations. We apply our results to logic program analysis, where unification can be interpreted as multiplicative conjunction in a quantale of idempotent substitutions. We characterize the objects in optimal semantics for logic program analysis, viz. the most abstract concrete semantics for any static program analysis property, and the structure of condensing domains in logic program analysis. |

Corradini, Andrea and Heckel, Reiko and Montanari, Ugo
In this paper we address the issue of providing a structured coalgebra presentation of transition systems with algebraic structure on states determined by an equational specification $\Gamma$. More precisely, we aim at representing such systems as coalgebras for an endofunctor on the category of $\Gamma$-algebras. The systems we consider are specified by using |

Pallottino, Stefano and Scutellà, Maria Grazia
We propose an algorithm which reoptimizes shortest paths in a very general situation, that is when any subset of arcs of the input graph is affected by a change of the arc costs, which can be either lower or higher than the old ones. This situation is more general than the ones addressed in the literature so far. |

Cappanera, Paola and Trubian, Marco
We consider an extension of the 0-1 multidimensional knapsack problem in which there are greater-than-equal inequalities, called demand constraints, besides the standard less-than-equal constraints. Moreover the objective function coefficients are not constrained in sign. This problem is worth considering because it is embedded in the models of practical applications, because it has an intriguing combinatorial structure and because it appears to be a challenging problem for commercial ILP solvers. Our approach is based on a nested tabu search algorithm in which neighbourhoods of different structure are exploited. A first higher level tabu search is carried on in which both feasible and unfeasible regions are explored. In this diversification phase an oscillation method proceeds alternating between constructive and destructive steps. Occasionally, a lower level tabu search which implements an intensification strategy is applied. In this second phase only feasible solutions are analysed. The algorithm has been tested on a wide set of instances. Computational results are discussed. |

Bigi, Giancarlo and Pappalardo, Massimo
Since a vector program has not just an optimal value but a set of optimal ones, the analysis of duality gaps requires at least the comparison between two sets of vector optimal values. Relying only on a weak duality property, the situations that can occur are analysed in detail and some concepts of duality gap are proposed. |

Dell'Olmo, P. and Hansen, P. and Pallottino, Stefano and Storchi, G.
In this work we study various uniform $k$-partition problems which consist in partitioning a collection of $m$ sets, each of them of cardinality $k$, into $k$ sets of cardinality $m$ such that each of these sets contains exactly one element coming from every original set. The problems differ according to the particular measure of ``set uniformity'' to be optimized. Most of the studied problems are polynomial and the 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. |

Coppola, Massimo and Vanneschi, Marco
We show how to apply a Structured Parallel Programming methodology based on skeletons to Data Mining problems, reporting several results about three commonly used mining techniques, namely association rules, decision tree induction and spatial clustering. We analyze the structural patterns common to these applications, looking at application performance and software engineering efficiency. Our aim is to clearly state what features a Structured Parallel Programming Environment should have to be useful for parallel Data Mining. Within the skeleton-based PPE SkIE that we have developed, we study the different patterns of data access of parallel implementations of Apriori, C4.5 and DBSCAN. We need to address large partitions reads, frequent and sparse access to small blocks, as well as an irregular mix of small and large transfers, to allow efficient development of applications on huge databases. We examine the addition of an object/component interface to the skeleton structured model, to simplify the development of environment-integrated, parallel Data Mining applications. |

Cappanera, Paola and Gallo, Giorgio
The problem of finding a work assignment for crew members of an airline in a given time horizon, is addressed. In the literature such a problem is usually referred to as the Airline Crew Rostering problem and consists of constructing monthly schedules for crew members by assigning them pairings, rest periods, leaves, training periods, union activities, and so forth, so as to satisfy the collective agreements and security rules. We formulate the Airline Crew Rostering problem as a 0-1 Multicommodity Flow problem where each employee corresponds to a commodity; determining a monthly schedule for an employee is the same as computing a path on a suitably defined graph while satisfying the clauses of the union conventions and distributing the workload evenly among the employees. Each path on the graph alternates between activity arcs which represent the activities to be covered in the programming period, and compatibility arcs linking together pairs of activities which can be assigned consecutively to the same employee. A preprocessing phase is performed which reduces the dimension of the graph. In order to tighten the linear programming formulation of our model we propose some families of valid inequalities which have proven to be computationally very effective; some of them have the characteristic that can be treated implicitly in the construction of the graph. Computational results obtained with a commercial integer programming solver (CPLEX) are analyzed. Finally, some decomposition techniques are identified which exploit the particular structure of the problem, as an alternative solution approach. |

Gervasi, Vincenzo and Prencipe, Giuseppe
Control and coordination of a set of autonomous vehicles that can freely move on a plane is a widely studied topic in robotics. The focus on this kind of problem has grown in recent years because of the increased interest in studying systems populated by many, simple units, instead of few, powerful ones. In particular, these units simply observe the environment by using their sensors, and react following simple rules: the reaction to the environmental stimuli is called the {\em behavior} of the unit. In this paper we study the {\em flocking problem}: a set of mobile units are required to follow a leader unit while keeping a predetermined formation (i.e., they are required to move in flock, like a group of soldiers). Moreover, the units in the flock do not know beforehand the path the leader will take: their task is just to follow him wherever he goes, and to keep the formation while moving. |

Pisanti, Nadia and Marangoni, Roberto and Ferragina, Paolo and Frangioni, Antonio and Luccio, Fabrizio and Savona, Antonio
Genes belonging to the same organism are called paralogs when they show a significant similarity in the sequences, even if they have a different biological function. It is an emergent biological paradigm that the families of paralogs in a genome derive from a mechanism of iterated gene duplication-with-modification. In order to investigate the evolution of organisms, it can be useful to infer the duplications that have taken place starting from an hypothetical original gene, and that have led to the current paralog genes family. This information can naturally be represented in a paralogy tree. Here we present a method, called PaTre, to generate a paralogy tree from a family of paralog genes. PaTre uses new techniques motivated by the specific application. The reliability of the inferential process is tested by means of a simulator that implements different hypotheses on the duplication-with-modification paradigm, and checked on real data. |

Franceschini, Gianni
Let k be a positive integer. A k-cycle is a connected graph in which each vertex has degree greater than k. A k-dense forest is a graph for which no subgraph is a k-cycle; if a k-dense forest is connected, then it is k-dense tree. A k-leaf is a vertex of a k-dense forest with degree less than or equal to k. Any k-dense forest has at least one k-leaf. If a k-leaf is removed, the resulting graph is still a k-dense forest. This fact is on the basis of another characterization of k-dense forests which make use of the concept of k-elimination, a particular ordering of removal for the vertices of a k-dense forest. In this paper, we study some new properties of the complete k-dense trees, a subclass of the one of k-dense trees. Such properties reveal some interesting relations between the class of complete k-dense trees and the widely studied class of k-trees. |

Scaparra, Maria Paola and Scutellà, Maria Grazia
As evidenced by the remarkable diversity of real world applications which have been modeled and solved as location problems, the field studying the optimal location of facilities is a very interdisciplinary and broad research area. The purpose of this paper is to fit the large variety of location models within a general unified framework, which arises from the description of the three buildings blocks of location problems, namely: facilities, customers, and locations. We provide evidences of how a particular problem specification can be stated mathematically as an optimization problem by opportunely combining into a compact and workable model the main features that characterize and relate these three elements. |

Accettella, Carlo J. and Del Corso, Gianna M. and Manzini, Giovanni
We consider the problem of inverting block circulant with circulant blocks BCCB matrices with entries over the field Z_p. This problem arises in the study of of two-dimensional linear cellular automata. Since the standard reduction to diagonal form by means of FFT has some drawbacks when working over Z_p, we solve this problem by transforming it into the equivalent problem of inverting a circulant matrix with entries over a suitable ring R. We show that a BCCB matrix of size mn can be inverted in O(m n c(m,n)) operations in Z_p, where c is a low degree polynomial in log m and log n. |

Franceschini, Gianni
Let k be a positive integer. A k-cycle is a connected graph in which each vertex has degree greater than k. A k-dense forest is a graph for which no subgraph is a k-cycle; if a k-dense forest is connected, then it is k-dense tree. A k-leaf is a vertex of a k-dense forest with degree less than or equal to k. Any k-dense forest has at least one k-leaf. If a k-leaf is removed, the resulting graph is still a k-dense forest. This fact is on the basis of another characterization of k-dense forests which make use of the concept of k-elimination, a particular ordering of removal for the vertices of a k-dense forest. In this paper, we consider some NP-complete problems in the area of Graph Theory. For each of these problems we study the restriction to the class of complete k-dense trees, for a generic integer k, and we try to establish whether there are some values of k for which the restriction of the original problem is in P and some other values of k for which this restriction still remains in the class of NP-complete problems. |

Bevilacqua, Roberto and Bozzo, Enrico and Menchi, Ornella
The reconstruction of diagnostic images obtained from SPECT (Single Photon Emission Computed Tomography) requires numerical models which involve structured matrices: Toeplitz and block circulant. In this note an algorithm is proposed, with the aim of exploiting the computational properties enjoyed by these structures. |

Bigi, Giancarlo and Castellani, Marco
Exploiting different tangent cones, many derivatives for set-valued functions have been introduced and considered to study optimality. The main goal of the paper is to address a general concept of K-epiderivative and to employ it to develop a quite general scheme for necesary optimality conditions in set-valued problems. |

Luccio, Fabrizio and Mesa Enriquez, Antonio and Olivares Rieumont, P. and Pagli, Linda
The problem of exact subtree matching is the one of deciding if a pattern tree P of m vertices is a subtree of a text tree T of n vertices, m<= n, and, in the affirmative case, finding all the occurrences of P in T. We consider ordered and non-ordered rooted trees with labeled vertices (the case of unlabeled vertices is a special case of this), and show how the problem can be solved in Theta(m + log n) time once a proper data structure is built for T in a preprocessing phase which requires Theta(n) time and space. Regarding T as an immutable text on which several queries are made, P as the contents of one such query, and assuming m=o(n), we can speak of search time sublinear in the size m+n of the overall structure. The number of occurrences of P in T does not appear in the search time because all such occurrences can be directly reconstructed from a constant output information. |

Baldan, Paolo and Mancarella, Paolo and Raffaetà, Alessandra and Turini, Franco
In this paper we introduce MuTACLP, a knowledge representation language which provides facilities for modeling and handling temporal information, together with some basic operators for combining different temporal knowledge bases. The proposed approach stems from two separate lines of research: the general studies on meta-level operators on logic programs introduced by Brogi et al. and Temporal Annotated Constraint Logic Programming (TACLP) defined by Fruehwirth. In MuTACLP atoms are annotated with temporal information which are managed via a constraint theory, as in TACLP. Mechanisms for structuring programs and combining separate knowledge bases are provided through meta-level operators. The language is given two different and equivalent semantics, a top-down semantics which exploits meta-logic, and a bottom-up semantics based on an immediate consequence operator. |

Baldan, Paolo and Corradini, Andrea and Ehrig, H. and Heckel, Reiko
In order to model the behaviour of open concurrent systems by means of Petri nets, we introduce open Petri nets, a generalization of the ordinary model where some places, designated as open, represent an interface of the system towards the environment. Besides generalizing the token game to reflect this extension, we define a truly concurrent semantics for open nets by extending the Goltz-Reisig process semantics of Petri nets. We introduce a composition operation over open nets, characterized as a pushout in the corresponding category, suitable to model both interaction through open places and synchronization of transitions. The deterministic process semantics is shown to be compositional with respect to such composition operation. If a net Z3 results as the composition of two nets Z1 and Z2, having a common subnet Z0, then any two deterministic processes of Z1 and Z2 which ``agree'' on the common part, can be ``amalgamated'' to produce a deterministic process of Z3. Vice versa, any deterministic process of Z3 can be decomposed into processes of the component nets. The amalgamation and decomposition operations are shown to be inverse to each other, leading to a bijective correspondence between the deterministic processes of Z3 and pair of deterministic processes of Z1 and Z2 which agree on the common subnet Z0. Technically, our result is similar to the amalgamation theorem for data-types in the framework of algebraic specification. A possible application field of the proposed constructions and results is the modeling of interorganizational workflows, recently studied in the literature. This is illustrated by a running example. |

Bernasconi, Anna and Ciriani, Valentina and Luccio, Fabrizio and Pagli, Linda
In the framework of SPP minimization, a three level logic synthesis technique developed in recent years, we exploit the ``regularity'' of Boolean functions to decrease minimization time. Our main results are: 1) the regularity of a Boolean function $f$ of $n$ variables is expressed by its \emph{autosymmetry degree} $k$ (with $0 \le k\le n$), where $k=0$ means no regularity (that is, we are not able to provide any advantage over standard synthesis); 2) for $k\geq 1$ the function is {\em autosymmetric}, and a new function $f_k$ is identified in polynomial time; $f_k$ is ``equivalent'' to, but smaller than $f$, and depends on $n-k$ variables only; 3) given a minimal SPP form for $f_k$, a minimal SPP form for $f$ is built in linear time; 4) experimental results show that 61\% of the functions in the classical \textsc{Espresso} benchmark suite are autosymmetric, and the SPP minimization time for them is critically reduced; we can also solve cases otherwise practically intractable. We finally discuss the role and meaning of autosymmetry. |

Ciriani, Valentina and Ferragina, Paolo and Luccio, Fabrizio and Muthukrishnan, S.
Data warehouses are increasingly storing and managing large scale string data, and dealing with large volume of transactions that update and search string databases. Motivated by this context, we initiate the study of {\em self-adjusting} data structures for string dictionary operations, that is, data structures that are designed to be efficient on an entire sequence of operations rather than individual string operations. Furthermore, we study this problem in the external memory model where string data is too massive to be stored in main memory and has to reside in disks; each access to a disk page fetches $B$ items, and the cost of the operations is the number of pages accessed. We show that given $n$ strings $S_{1},\ldots,S_{n}$ of total length $\sum_i |S_i|=N$, a sequence of $m$ string searches $S_{i_{1}},S_{i_{2}},\ldots,S_{i_{m}}$ takes $ O(\sum_{j=1}^{m}(\frac{|S_{i_{j}}|}{B})+\sum _{i=1}^{n}(n_{i}\log_{B}\frac{m}{n_{i}}))$ amortized expected I/Os, where $n_{i}$ is the number of times $S_{i}$ is queried. Inserting or deleting a string $S$ takes $O(\frac{|S|}{B}+\log_{B}n)$ amortized expected I/Os. This result is the analog of what is known as the Static Optimality Theorem~\cite{Sleator-Tarjan} proved by Sleator and Tarjan in their classic splay trees paper for a dictionary of numerical values; here, it has been generalized, for the first time to string data, to string operations, and to the external memory model. This performance is achieved not by traditional ``splay'' operations on search trees as in~\cite{Sleator-Tarjan}, but by designing a novel self-adjusting data structure based on the well-known skip lists. In addition, we introduce the paradigm of using the main memory (or a part thereof) persistently across operations, in the manner of a cache, to further improve the performance of our self-adjusting skip list. This is quite reasonable in applications where string operations are large in volume. |

Gervasi, Vincenzo
Domain-based parsing is a shallow parsing technique that exploits knowledge about domain-specific properties of terms in order to determine "optimal" parse trees for natural language sentences. Cico is a simple parser using domain-based parsing. It is particularly well suited for parsing natural language sentences of technical nature (e.g., requirements documents for software systems), as in this case several simplifying assumptions hold, and has been used successfully in several experiments in the requirement engineering field. In the first part of this report, we describe formally the parsing algorithm implemented by Cico, and give some experimental data on its performance. In the second part, we provide a complete user manual for cico3, an implementation of the Cico algorithm, and for a number of associated tools. Finally, in the third part, we present some illustrative example taken from real applications. |

Ahuja, Ravindra K. and Orlin, James B. and Pallottino, Stefano and Scutellà, Maria Grazia
In this paper, we study dynamic shortest path problems, which is to determine a shortest path from a specified source node to every other node in the network where arc travel times change dynamically. We consider two problems: the minimum time walk problem (which is to find a walk with the minimum travel time) and the minimum cost walk problem (which is to find a walk with the minimum travel cost). The minimum time walk problem is known to be polynomially solvable for a class of networks called FIFO networks. This paper makes the following contributions: (i) we show that the minimum cost walk problem is an NP-complete problem; (ii) we develop a pseudopolynomial-time algorithm to solve the minimum cost walk problem (for integer travel times); and (iii) we develop a polynomial-time algorithm for the minimum time walk problem arising in road networks with traffic lights. |

**NOTE. **Starting January 2015 Technical reports can be inserted in the Open Access repository UnipiEprints.

Once published, they will be visible also in these pages. The importing of data from UnipiEprints is still experimental. The old TR service is no longer maintained.

Data imported from UnipiEprints