Semi-dynamic breadth-first search in digraphs

In this paper we propose dynamic algorithms for maintaining a breadth-first search tree from a given source vertex of a directed graph G in either an incremental or a decremental setting. During a sequence of q edge insertions or a sequence of q edge deletions the total time required is O(m·min{q,n}), where n is the number of vertices of G, and m is the final number of edges of G in the case of insertions or the initial number of edges of G in the case of deletions. This gives O(n) amortized time for each operation if the sequence has length Ω(m). Our algorithms require O(n+m) space. These are the first results in the literature concerning the dynamic maintenance of a breadth-first search tree for directed graphs. As a straightforward application of such algorithms we can maintain a shortest path tree for a directed graph in the case of unit edge weights within the same time bounds. In this case distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path.     

A Constraint-based Approach for Annotating Music Scores with Gestural Information

The physical gestures that operate music instruments are responsible for the qualities of the sound being produced in a performance. Gestural information is thereby crucial for a model of music performance, paired with a model of sound synthesis where this information is applied. The highly constrained nature of performers gestures makes this task suitable to be modeled via a constraint-based approach, coupled with a strategy aimed at maximizing the gestural comfort of performers. We illustrate the problem representation, the search strategy and a validation of the model against human performance.     

An application of kernel methods to gene cluster temporal meta-analysis

The application of various clustering techniques for large-scale gene-expression measurement experiments is a well-established method in bioinformatics. Clustering is also usually accompanied by functional characterization of gene sets by assessing statistical enrichments of structured vocabularies, such as the gene ontology (GO) [Gene Ontology Consortium. The gene ontology (GO) project in 2006. Nucleic Acids Research (Database issue), vol. 34; 2006. p. D322–6]. If different clusters are generated for correlated experiments, a machine learning step termed cluster meta-analysis may be performed, in order to discover relations among the components of such sets. Several approaches have been proposed: in particular, kernel methods may be used to exploit the graphical structure of typical ontologies such as GO. Following up the formulation of such approach [Merico D, Zoppis I, Antoniotti M, Mauri G. Evaluating graph kernel methods for relation discovery in GO-annotated clusters. In: KES-2007/WIRN-2007, Part IV, Lecture notes in artificial intelligence, vol. 4694. Berlin: Springer; 2007. p. 892–900; Zoppis I, Merico D, Antoniotti M, Mishra B, Mauri G. Discovering relations among GO-annotated clusters by graph kernel methods. In: Proceedings of the 2007 international symposium on bioinformatics research and applications. Lecture notes in computer science, vol. 4463. Berlin: Springer; 2007], in this paper we discuss, from an information-theoretic point of view, further results about its applicability and its performance.     

Visual extraction of information from web pages

In this paper we present a graphical software system that provides an automatic support to the extraction of information from web pages. The underlying extraction technique exploits the visual appearance of the information in the document, and is driven by the spatial relations occurring among the elements in the page. However, the usual information extraction modalities based on the web page structure can be used in our framework, too. The technique has been integrated within the Spatial Relation Query (SRQ) tool. The tool is provided with a graphical front-end which allows one to define and manage a library of spatial relations, and to use a SQL-like language for composing queries driven by these relations and by further semantic and graphical attributes.     

Texture Mapping Real‐World Objects with Hydrographics

In the digital world, assigning arbitrary colors to an object is a simple operation thanks to texture mapping. However, in the real world, the same basic function of applying colors onto an object is far from trivial. One can specify colors during the fabrication process using a color 3D printer, but this does not apply to already existing objects. Paint and decals can be used during post‐fabrication, but they are challenging to apply on complex shapes. In this paper, we develop a method to enable texture mapping of physical objects, that is, we allow one to map an arbitrary color image onto a three‐dimensional object. Our approach builds upon hydrographics, a technique to transfer pigments printed on a sheet of polymer onto curved surfaces. We first describe a setup that makes the traditional water transfer printing process more accurate and consistent across prints. We then simulate the transfer process using a specialized parameterization to estimate the mapping between the planar color map and the object surface. We demonstrate that our approach enables the application of detailed color maps onto complex shapes such as 3D models of faces and anatomical casts.     

Robust linear parameter‐varying control of induction motors

The paper deals with the motion control of an induction motor. Because the nonlinear state equations describing the dynamics of such a machine can be embedded into a linear model with the rotor speed ω as a varying parameter, advantage is taken of some recent results on the control of linear parameter‐varying systems, thus ensuring stability independently of how the varying parameter changes in time within a compact set. The adopted control structure consists of a fast inner electric loop that controls the stator currents and an outer mechanical loop that generates the torque acting on the motor shaft. Of crucial importance is the design of the internal model controller for the current loop. In particular, it is proved that an algebraically equivalent electric motor model admits a Lyapunov function that, together with its Lyapunov derivative, is independent of ω and of all motor parameters. This result allows us to find an upper bound on the norm of the Youla–Kucera parameter that ensures robust stability against speed measurement errors. Simulations carried out on a benchmark motor model show that the adopted control strategy performs well. Copyright © 2014 John Wiley & Sons, Ltd.     

A P2P strategy for QoS discovery and SLA negotiation in Grid environment

In recent years, Grid systems and Peer to Peer networks are the most commonly-used solutions to achieve the same goal: the sharing of resources and services in heterogeneous, dynamic, distributed environments. Many studies have proposed hybrid approaches that try to conjugate the advantages of the two models. This paper proposes an architecture that integrates the P2P interaction model in Grid environments, so as to build an open cooperative model wherein Grid entities are composed in a decentralized way. In particular, this paper focuses on a QoS aware discovery algorithm for P2P Grid systems, analyzing protocol and explaining techniques used to improve its performance.     

Reasoning about reasoning in a meta-level architecture

In this paper we discuss reasoning about reasoning in a multiple agent scenario. We consider agents that are perfect reasoners, loyal, and that can take advantage of both the knowledge and ignorance of other agents. The knowledge representation formalism we use is (full) first order predicate calculus, where different agents are represented by different theories, and reasoning about reasoning is realized via a meta-level representation of knowledge and reasoning. The framework we provide is pretty general: we illustrate it by showing a machine checked solution to the three wisemen puzzle. The agents' knowledge is organized into units: the agent's own knowledge about the world and its knowledge about other agents are units containing object-level knowledge; a unit containing meta-level knowledge embodies the reasoning about reasoning and realizes the link among units. In the paper we illustrate the meta-level architecture we propose for problem solving in a multi-agent scenario; we discuss our approach in relation to the modal one and we compare it with other meta-level architectures based on logic. Finally, we look at a class of applications that can be effectively modeled by exploiting the meta-level approach to reasoning about knowledge and reasoning.