nSPARQL: A navigational language for RDF

Navigational features have been largely recognized as fundamental for graph database query languages. This fact has motivated several authors to propose RDF query languages with navigational capabilities. In this paper, we propose the query language nSPARQL that uses nested regular expressions to navigate RDF data. We study some of the fundamental properties of nSPARQL and nested regular expressions concerning expressiveness and complexity of evaluation. Regarding expressiveness, we show that nSPARQL is expressive enough to answer queries considering the semantics of the RDFS vocabulary by directly traversing the input graph. We also show that nesting is necessary in nSPARQL to obtain this last result, and we study the expressiveness of the combination of nested regular expressions and SPARQL operators. Regarding complexity of evaluation, we prove that given an RDF graph G and a nested regular expression E, this problem can be solved in time O(|G||E|).     

An Evaluation of an OS-Based Coherence Scheme for Tiled CMPs

The interconnect mechanisms (shared bus or crossbar) used in current chip-multiprocessors (CMPs) are expected to become a bottleneck that prevents these architectures from scaling to a larger number of cores. Tiled CMPs offer better scalability by integrating relatively simple cores with a lightweight point-to-point interconnect. However, such interconnects make snooping impractical and, thus, require alternative solutions to cache coherence. In this article, we investigate a novel, cost-effective mechanism to support shared-memory parallel applications that forgoes hardware maintained cache coherence. This mechanism is based on the key ideas that mapping of lines to physical caches is done at the page level with OS support and that hardware supports remote cache accesses. We extend our previous work by investigating in detail the impact of system design parameters and extending the system to support multi-level cache hierarchies. Results show that the choice of implementation of multi-level cache hierarchies can have a significant impact on performance.     

Singularity robust algorithm in serial manipulators

Singularity is a fundamental problem with robotic manipulators. Various methods of singularity handling have been published in the past. In this paper, a singularity robust method is presented and its implementation issues discussed. It focuses on the discontinuity problem inherent in the singularity robust techniques with removal of degenerate components. Sources of the discontinuity are discussed and the null motion is proposed as the means of providing a continuous control of the end-effector over the boundary of the singular region. The presentation of this paper covers a complete treatment of singularities, starting from identifications of the singular configurations and the associated singular directions, the handling algorithm and the discontinuity issues. The algorithm was implemented on PUMA 560. The experimental results are presented and discussed.     

A new robust algorithmic for multi-camera calibration with a 1D object under general motions without prior knowledge of any camera intrinsic parameter

In computer vision, camera calibration is a necessary process when the retrieval of information such as angles and distances is required. This paper addresses the multi-camera calibration problem with a single dimension calibration pattern under general motions. Currently, the known algorithms for solving this problem are based on the estimation of vanishing points. However, this estimate is very susceptible to noise, making the methods unsuitable for practical applications. Instead, this paper presents a new calibration algorithm, where the cameras are divided into binocular sets. The fundamental matrix of each binocular set is then estimated, allowing to perform a projective calibration of each camera. Then, the calibration is updated for the Euclidean space, ending the process. The calibration is possible without imposing any restrictions on the movement of the pattern and without any prior information about the cameras or motion. Experiments on synthetic and real images validate the new method and show that its accuracy makes it suitable also for practical applications.     

GMAC: An overlay multicast network for mobile agent platforms

The lack of proper support for multicast services in the Internet has hindered the widespread use of applications that rely on group communication services such as mobile software agents. Although they do not require high bandwidth or heavy traffic, these types of applications need to cooperate in a scalable, fair and decentralized way. This paper presents GMAC, an overlay network that implements all multicast related functionality–including membership management and packet forwarding–in the end systems. GMAC introduces a new approach for providing multicast services for mobile agent platforms in a decentralized way, where group members cooperate in a fair way, minimize the protocol overhead, thus achieving great scalability. Simulations comparing GMAC with other approaches, in aspects such as end-to-end group propagation delay, group latency, group bandwidth, protocol overhead, resource utilization and failure recovery, show that GMAC is a scalable and robust solution to provide multicast services in a decentralized way to mobile software agent platforms with requirements similar to MoviLog.     

EDT Method for Multiple Labelled Objects Subject to Tied Distances

Machine Intelligence Research - The success of new scientific areas can be assessed by their potential for contributing to new theoretical approaches aligned with real-world applications. The...     

Distinguishing video quality through differential matrices

Multicast multi-layered communications must implement efficient control algorithms to address undesirable network behaviors. This paper proposes two multi-metric algorithms for computing the rates of the video layers and improve the global video quality of a multicast session. In fact, we show that a single-metric approach may degrade some network parameters without obtaining any substantial improvements. Our first algorithm combines three metrics and a set of weights in such a way that one metric can be prioritized. This leads to an improved quality of multicast sessions, as we show through a number of experiments. In networks where the available resources are highly variable, however, the stability of the video quality is compromised if absolute values of the metrics are adopted. We then propose a second algorithm that uses the relative values of the metrics on a per-entry basis. Computation of the global quality of the multicast session is based on a differential matrix that stores the metrics for each receiver. This scheme takes into account the dynamics of the available resources and the heterogeneity of receivers. The great benefit of this approach is that the global video quality is always improved for every loop of the algorithm.     

A Mechanized Proof Environment for the Convenient Computations Proof Method

A mechanized verification environment made up of theories over the deductive mechanized theorem prover PVS is presented, which allows taking advantage of the convenient computations method. This method reduces the conceptual difficulty of proving a given property for all the possible computations of a system by separating two different concerns: (1) proving that special convenient computations satisfy the property, and (2) proving that every computation is related to a convenient one by a relation which preserves the property. The approach is especially appropriate for applications in which the first concern is trivial once the second has been shown, e.g., where the specification itself is that every computation reduces to a convenient one. Two examples are the serializability of transactions in distributed databases, and sequential consistency of distributed shared memories. To reduce the repetition of effort, a clear separation is made between infrastructural theories to be supplied as a proof environment PVS library to users, and the specification and proof of particular examples. The provided infrastructure formally defines the method in its most general way. It also defines a computation model and a reduction relation—the equivalence of computations that differ only in the order of finitely many independent operations. One way to prove that this relation holds between every computation and some convenient one involves the definition of a measure function from computations into a well-founded set. Two possible default measures, which can be applied in many cases, are also defined in the infrastructure, along with useful lemmas that assist in their usage. We show how the proof environment can be used, by a step-by-step explanation of an application example.     

Template-based quadrilateral mesh generation from imaging data

This paper describes a novel template-based meshing approach for generating good quality quadrilateral meshes from 2D digital images. This approach builds upon an existing image-based mesh generation technique called Imeshp, which enables us to create a segmented triangle mesh from an image without the need for an image segmentation step. Our approach generates a quadrilateral mesh using an indirect scheme, which converts the segmented triangle mesh created by the initial steps of the Imesh technique into a quadrilateral one. The triangle-to-quadrilateral conversion makes use of template meshes of triangles. To ensure good element quality, the conversion step is followed by a smoothing step, which is based on a new optimization-based procedure. We show several examples of meshes generated by our approach, and present a thorough experimental evaluation of the quality of the meshes given as examples.     

Maximal versus strong solution to algebraic Riccati equations arising in infinite Markov jump linear systems

We deal with a perturbed algebraic Riccati equation in an infinite dimensional Banach space which appears, for instance, in the optimal control problem for infinite Markov jump linear systems (from now on iMJLS). Infinite or finite here has to do with the state space of the Markov chain being infinite countable or finite (see, e.g., [M.D. Fragoso, J. Baczynski, Optimal control for continuous time LQ—problems with infinite Markov jump parameters, SIAM J. Control Optim. 40(1) (2001) 270–297]). By using a certain concept of stochastic stability (a sort of L₂-stability), we have proved in [J. Baczynski, M.D. Fragoso, Maximal solution to algebraic Riccati equations linked to infinite Markov jump linear systems, Internal Report LNCC, no. 6, 2006] existence (and uniqueness) of maximal solution for this class of equations. As it is noticed in this paper, unlike the finite case (including the linear case), we cannot guarantee anymore that maximal solution is a strong solution in this setting. Via a discussion on the main mathematical hindrance behind this issue, we devise some mild conditions for this implication to hold. Specifically, our main result here is that, under stochastic stability, along with a condition related with convergence in the infinite dimensional scenario, and another one related to spectrum—weaker than spectral continuity—we ensure the maximal solution to be also a strong solution. These conditions hold trivially in the finite case, allowing us to recover the result of strong solution of [C.E. de Souza, M.D. Fragoso, On the existence of maximal solution for generalized algebraic Riccati equations arising in stochastic control, Systems Control Lett. 14 (1990) 233–239] set for MJLS. The issue of whether the convergence condition is restrictive or not is brought to light and, together with some counterexamples, unveil further differences between the finite and the infinite countable case.