Abstract: The interoperability of information systems has been pursued for a long time and is even more demanded in the Internet era. This paper reviews the literature in this area, from the database perspective. It covers work on interconnection of databases, classification of data integration problems, major standards and architectures, and the most recent developments in the fields of semantic Web, Web services and scientific workflows.

Abstract: In this paper, we propose a method that enables operating system calls from inside architecture simulators. The proposed framework provides support to file I/O and dynamic memory systems, and can be incorporated into any ISA simulator, at the instruction or cycle-accurate levels. It enables calls to POSIX-compatible system routines in a simulated application, without requiring any change to the application code. Since file I/O is performed transparently, the input and output data for the application program is read/written directly from/to the host filesystem, and all console operations are redirected to the host console. This framework was tested in ISA simulators synthesized from models written in the ArchC Architecture Description Language, but it can be incorporated into any ADL or hand-coded simulator. Instruction and cycle-accurate models, for both MIPS I and SPARC V8 architectures have been thoroughly evaluated by successfully running programs from the Mibench and MediaBench benchmarks.

Resumo: Este trabalho lida com um problema de otimização muito conhecido no ramo da Pesquisa Operacional, o agendamento escolar (timetabling). A instância tratada deste problema reflete uma situação baseada na realidade brasileira. Para a resolução deste problema propomos o emprego de heurísticas de busca local, tais como: hill climbing, simulated annealing e, em especial, a Busca Tabu. Tais heurísticas vêm demonstrando grande potencial na solução de problemas NP-Difíceis. Paralelamente à construção do resolvedor heurístico, foi construída uma interface gráfica amigável que permite o uso do sistema por usuários leigos.

Resumo: Este trabalho trata da utilização de heurísticas evolutivas na resolução do problema de agendamento de salas, professores e alunos, conhecido na literatura como Agendamento Acadêmico (School Timetabling). O projeto é embasado no uso de Algoritmos Genéticos, uma classe de heurísticas que vêm demonstrando grande eficácia no tratamento de problemas NP-Difícies. A abordagem é testada sobre uma instância do problema derivada da realidade brasileira, típica das escolas de ensino fundamental e médio, públicas ou particulares. A alta carga de restrições do problema levou à elaboração e implementação de técnicas alternativas no algoritmo, o que resultou em soluções de nível bastante satisfatório. O trabalho visa também, através da criação de uma interface amigável para usuários leigos, prover uma ferramenta útil para instituições de ensino brasileiras, que atualmente dispõem de poucas ferramentas para lidar com o problema e dispendem grande quantidade de tempo para a montagem manual de seus horários.

Abstract: In 1976, Booth and Leuker invented the PQ trees as a compact way of storing and manipulating all the permutations on elements that keep consecutive the elements in certain given sets . This problem finds applications in DNA physical mapping, interval graph recognition, logic circuit optimization and data retrieval, for instance. In 1995, Meidanis and Munuera created the PQR trees, a natural generalization of PQ trees. The difference between them is that PQR trees exist for every set collection, even when there are no valid permutations. The R nodes encapsulate subsets where the consecutive ones property fails. In this note we present an almost-linear time algorithm to build a PQR tree for an arbitrary set collection.

Resumo: Este artigo propõe uma alternativa ao tradicional esquema de divulgação de informações de revogação "on-line" de certificados, chamado OCSP (Online Certificate Status Protocol), que utiliza apenas operações de hash e criptografia simétrica, mantendo o mesmo nível de segurança. As operações assimétricas, ou de chaves públicas, utilizadas nos OCSP-responders são muito custosas, em tempo e memória, a ponto de tornar a divulgação de informações de revogação a maior consumidora de recursos na manutenção de uma Infra-estrutura de Chaves Públicas (ICP, ou PKI-Public Key Infrastructure). Nosso esquema permite grande economia em processamento, transmissão e armazenamento, beneficiando principalmente os dispositivos móveis, sem exclusão de demais tipos de clientes.

Abstract: This article proposes an alternative to the traditional OCSP (Online Certificate Status Protocol) scheme of broadcasting certificates' revocation information, which uses only hash and symmetric cryptography operations, while keeping the same security level. Asymmetric, or public-key operations, used in OCSP-responders are very costly, both in time and memory requirements, which makes certificate revocation management the largest resource-consuming activity in a Public-Key Infrastructure (PKI). Our proposed scheme provides a substantial reduction in processing, bandwidth and storage requirements, making it especially suitable for mobile clients.

Resumo: Este relatório descreve um Algoritmo Genético (AG) desenvolvido para resolver um problema de projeto de rede telefônica. O problema consiste em particionar uma grande área de projeto urbana em pequenas seções de serviço, as quais podem ser controladas por um único dispositivo de telecomunicação padrão. O AG incorpora informações geométricas e topológicas da área de projeto operando diretamente com uma matriz de pontos de demanda geográficos. Os resultados computacionais mostraram que esta é uma técnica promissora para particionar a área de projeto em seções de serviço e para posicionar o dispositivo de controle dentro de cada seção. Os testes foram realizados com instâncias reais tomadas de grandes áreas da cidade de São Paulo.

Abstract: This paper describes a Genetic Algorithm (GA) developed to solve a problem in telecommunications network design. The problem is to partition a large urban project area into smaller service sections, which can be controlled by a single standard telecommunications switch. The GA incorporates geometric and topological information from the project area by operating directly with a matrix of geographical demand points. Computational results show this to be a promising technique for both partitioning the project area into services sections and for positioning the control switch within each section. Tests were realized with real instance cases taken from large areas in the city of São Paulo.

Abstract: Code compression has been shown to be an effective technique to reduce code size in memory constrained embedded systems. It has also been used as a way to increase cache hits, thus reducing power consumption and improving performance. This report proposes a simple dictionary-based technique for code compression. It describes an approach to mix static/dynamic instruction profiling so as to trade-off compression ratio for performance. Compressed instructions are stored as variable-size indices into fixed-size codewords, thus reducing dictionary entry superpositions and compressed code misalignments simultaneously. Moreover, a decompressor buffering scheme is proposed that considerably decreases cache lookups. Experimental results, using the LEON SparcV8 processor and a program mix from MiBench and Mediabench, show that our approach halves the number of cache accesses while produce compression ratios as low as 56%.

Abstract: This paper introduces the computation of an expression for the time at which the length of a queue fed by several multifractal flows reaches its maximum. Expressions for the equivalent bandwidth of an aggregate of multifractal flows is also presented. Moreover, it is shown that modelling based on monofractal process rather than based on multifractal processes leads to overprovisioning of resources.

Abstract: In this paper, a novel envelope process for multifractal traffic modeling is introduced. The envelope process is an upperbound for the amount of work arrived in a multifractal Brownian motion process. The time scale of interest of a queueing system fed by a multifractal stream is computed. Simulation experiments using both real and synthetic data show that the proposed model is accurate.

Abstract: The perfect matching polytope of a graph is the convex hull of the set of incidence vectors of perfect matchings of the graph. Edmonds showed that a vector belongs to the perfect matching polytope if and only if it satisfies three sets of inequalities: non-negativity, regularity on the vertices, and lower bounds on the odd sets. We are interested in the problem of characterizing graphs whose perfect matching polytopes are determined by non-negativity and regularity. (It is well-known that bipartite graphs have this property.) The appropriate context for studying this problem is the theory of matching covered graphs. An edge of a graph is admissible if there is some perfect matching of the graph containing that edge. A graph is matching covered if it is connected, has at least two vertices, and each of its edges is admissible. A cut of a matching covered graph is tight if each perfect matching of the graph has precisely one edge in the cut. and is separating if each of the two graphs obtained by shrinking a shore of the cut to a single vertex is also matching covered. Every tight cut is a separating cut, but the converse is not true. A non-bipartite matching covered graph is a brick if it has no nontrivial tight cuts and is a solid brick if it has no nontrivial separating cuts. We show that the above-mentioned problem on the perfect matching polytopes characterized by non-negativity and regularity may be reduced to one of recognizing solid bricks. (The complexity status of this problem is unknown.) We include a brief account of how we were led to solid bricks, present some examples and a proof of a recent theorem of Reed and Wakabayashi.

Abstract: The work of Chen et al, on Quality of Service (QoS) of failure detectors, did not explicitly model the possibility of loss bursts. They assumed only mean loss as the system parameter to message losses. This paper deals with the QoS of failure detectors when the probabilistic behavior of messages is extended with the probability distribution of loss burst lengths. The proposed Markov chain model, which treats loss bursts, is presented in this paper. Some simulation results are commented.

Abstract: Reconfigurable systems have been proved to achieve significant performance speedup through architectures that map the most time-consuming application kernel modules or inner-loops to a reconfigurable datapath. As each portion of the application starts to execute, the system reconfigures the datapath so as to perform the corresponding computation. The reconfigurable datapath should have as few and simple hardware blocks and interconnections as possible, in order to reduce its cost, area, power consumption, and reconfiguration overhead. Thus hardware blocks and interconnections should be reused across the application as much as possible. We represent each piece of the application as a control/data-flow graph (CDFG) and merge them together, synthesizing a single reconfigurable datapath. The CDFG merging process enables the reuse of hardware blocks and interconnections by identifying similarities among the CDFGs, and producing a resulting datapath that can be dynamically reconfigured to work for each CDFG and has a minimum area cost, when considering both hardware blocks and interconnections. In this report we formalize the CDFG merge problem and we present a proof that it is NP-complete, by reducing the subgraph isomorphism problem to it.

Resumo: Grafos são estruturas de grande relevância na representação de dados em formato de rede, como troca de mensagens entre pessoas em um ambiente de ensino a distância. Inspirada em representações radiais de grafos, a estrutura proposta neste artigo é baseada na disposição dos vértices de um grafo em dois anéis concêntricos e, ao mesmo tempo, na distorção de suas arestas com relação ao centro desses anéis. Este artigo apresenta ainda um protótipo que implementa essa estrutura, no qual a posição dos vértices e a distorção das arestas são controladas diretamente pelo usuário.

Abstract: Graphs are structures of great relevance to network data representation, such as message exchange between people into an e-learning environment. Inspired by radial graphs representations, this article proposes a structure based on the disposition of the nodes of a graph into two concentric rings, and on the distortion of its edges related to the center of these rings. In addition, this article presents a prototype that implements this structure, in which the nodes' position and the edges' distortion are controlled directly by the user.

Abstract: We approach here the interactive 3D segmentation problem in the context of the image foresting transform (IFT) - a graph-based tool to develop image processing operators - by introducing the IFT- algorithm to compute sequences of IFTs in a differential way. We instantiate the IFT- to be a watershed transform and validate it for segmentation of brain MR-images. The new method reduces by a factor of 8.4 the user's waiting time during segmentation compared to the non-differential watershed approach. It also provides a revertible operator that leads to higher efficiency gains than our previous differential approach, the IFT+.

Abstract: In this report we introduce a new architecture description language (ADL) called ArchC. ArchC is an open-source SystemC-based ADL that is specialized for processor architecture description. Its main goal is to provide enough information, at the right level of abstraction, in order to allow users to explore and verify new architectures, by automatically generating simulators, assemblers and compiler back-ends. ArchC's key feature is a storage-based co-verification mechanism that automatically checks the consistency of refined SystemC RTL models against the behavioral reference model. We have used ArchC to synthesize cycle-based simulators for the MIPS, Intel 8051 and SPARC processors.

Abstract: Minimum Interference Routing is instrumental to MPLS Traffic Engineering under realistic assumptions of unknown traffic demand. This work presents a new algorithm for minimum interference routing, called Light Minimum Interference Routing (LMIR). This algorithm introduces a new approach for critical link identification that reduces the computational complexity. Results, derived via simulation, show that LMIR is precise and has low computational complexity.

Abstract: The video segmentation problem consists in the identification of boundaries between two consecutive shots. These boundaries can be subdivided in cut and gradual transitions. The first one is characterized by a concatenation of two shots and the second one corresponds to the gradual transformation of a shot into another. The simplest gradual transitions are fade and dissolve. The common approach to solve the identification problem of these features in a video is based on dissimilarity measures between frames. The possibility of representing the video transitions by specific patterns in a 2D image, called visual rhythm, and to apply image processing tools on this image is an interesting alternative to cope with this problem. In this work, we consider the morphological multi-scale gradient operators to identify cut and gradual transitions at the same time on the visual rhythm representation. Three different morphological operators are considered: a multi-scale gradient proposed by Soille and two variants of this operation based on ultimate erosion and thinning concepts. Also, the Canny's filter is used to compute the gradient values.

Abstract: We present approximation algorithms for a class-constrained version of the knapsack problem: Given an integer , a set of items , each item with value, size and a class, find a subset of of maximum total value such that items are grouped in compartments. Each compartment must have only items of one class and must be separated by the subsequent compartment by a wall division of size . Moreover, two subsequent wall divisions must stay a distance of at least and at most . The total size used by compartments and by wall divisions must be at most . This problem have practical applications on cutting-stock problems.

Abstract: In this paper we consider an experimental study of approximation algorithms for scheduling problems in parallel machines minimizing the average weighted completion time. We implemented approximation algorithms for the following problems: , , , and . We generated about 900 tests over more than 190 different instances and present some practical aspects of the implemented algorithms. We also made an experimental comparison on two lower bounds based in the formulations used by the algorithms. The first one is a semidefinite formulation for the problem and the other is a linear formulation for the problem . For all tests, the algorithms obtained very good results. We note that algorithms using more refined techniques, when compared to algorithms with simple strategies, does not necessary leads to better results. We also present two heuristics, based in approximation algorithms, that generates solutions with better quality in almost all instances considered.

Abstract: THIS REPORT IS NOW OBSOLETE - SEE IC-TR-03-21

In this paper, a novel envelope process for multifractal traffic modeling is introduced. The envelope process is an upperbound for the amount of work arrived in a multifractal Brownian motion process. The time scale of interest of a queueing system fed by a multifractal stream is computed. Simulation experiments using both real and synthetic data show that the proposed model is accurate. Moreover, a new estimator for the Holder function is presented.

Abstract: This report introduces a novel AQM policy that uses an H2 optimal controller. The synthesis of the controller uses a non-rational approach, in which the stability and performance objectives of the system are completely expressed as Linear Matrix Inequalities (LMIs). The controller stabilizes the system under diverse network conditions.

Abstract: This paper introduces a novel policing mechanism, called, Packet Leaky Bucket which marks all cells of a frame with the same level of priority. Moreover, it discusses the need for having frame discard mechanisms in ATM networks when frame-oriented policing mechanisms are used.

Abstract: Workflow Management Systems (WfMS) have been adopted as a practical solution to automate the execution of business processes in order to use resources efficiently and make organizations more competitive. Workflow activities usually have a very coarse granularity, are long-lived and business process dependent. The semantics of activities, including the semantics of associated invoked applications and resources, are not known by the WfMS. As a result, inconsistencies may arise from the concurrent use of shared applications/resources by the workflow activities. Thus, we propose a workflow activity synchronization mechanism to deal with these inconsistencies using a component-based solution. We present the specification of a software component called Synchronization Manager Component, a prototype implementation and a case study carried out within the context of the WorkToDo environment.

Abstract: This paper presents WorkToDo, a workflow management system compliant with the WfMC Reference Model. It addresses WorkToDo distributed architecture, its prototype implementation based on CORBA, mechanisms for task synchronization and support for operation in wireless environments. In this type of environment, users should be able to perform tasks independently from location and type of connection. To achieve these goals, the proposed workflow system supports task reservation and anticipated transfer of data and applications to the mobile computer. Other issues related with the concurrent execution of tasks are also considered. Synchronization mechanisms are included to avoid inconsistencies that may arise from the interleaved execution of tasks. Moreover, WorkToDo distributed architecture includes features to achieve a great level of reliability and scalability.

Abstract: Efficient address code optimization is a central problem in code generation for processors with restricted addressing modes, like Digital Signal Processors (DSPs). This paper proposes a new heuristic to solve the Simple Offset Assignment (SOA) problem, the problem of allocating scalar variables to memory so as to minimize addressing code. This new approach, called Coalescing SOA (CSOA), performs variable memory slot coalescing simultaneously to offset assignment computation. Experimental results, based on the MediaBench benchmark, reveal a very significant improvement over all known solutions to SOA. In fact, CSOA produces, on average, 66.5% fewer update instructions, and reduces by 71.3% the stack space for local variables, when comparing with the best known solution to SOA.

Abstract: The image foresting transform (IFT) is a graph-based approach to the design of image processing operators based on connectivity. It naturally leads to correct and efficient implementations, and to a better understanding of how different operators relate to each other. We give here a precise definition of the IFT, and a procedure to compute it--a generalization of Dijkstra's algorithm--with a proof of correctness. We also discuss implementation issues and illustrate the use of the IFT in a few applications.

Abstract: This paper presents the advantages of computing two recently proposed shape descriptors, multiscale fractal dimension and contour saliences, using the image foresting transform--a graph-based approach to the design of image processing operators. It introduces a robust approach to estimate contour saliences (peaks of high curvature) by exploiting the relation between contour and skeleton. The paper also compares both shape descriptors to fractal dimension, Fourier descriptors, and moment invariants with respect to their invariance to object characteristics that belong to a same class (compact-ability) and to their discriminatory ability to separate objects that belong to distinct classes (separability).

Resumo: Desenvolvendo pesquisa em Sistemas de Informação podemos nos deparar, muitas vezes, com a necessidade de se analisar como certas teorias, ferramentas ou métodos são assimilados por comunidades, tanto de especialistas quanto de usuários e que, mais que dados quantitativos, números, estatísticas e probabilidades, o pesquisador deverá estar observando o que foi percebido e sentido pelas pessoas envolvidas na análise. Além disso, em muitos casos, sua amostragem também será pequena. A pesquisa qualitativa nos parece fornecer instrumentos suficientes para garantir o rigor científico, validade e confiança requeridos do pesquisador para que seu trabalho seja respeitado pela comunidade científica. Este nosso trabalho analisa abordagens de pesquisa e pesquisa qualitativa, métodos e técnicas, sugerindo como poderia ser sua utilização em um projeto de pesquisa envolvendo a área de Sistemas de Informação.

Abstract: An edge of a brick is removable if is matching covered. A removable edge is -invariant if has exactly one brick. A removable edge is thin if, for each barrier of , the graph has precisely isolated vertices, each of which has degree two in . Improving upon a theorem proved in [4] and [5], we show here that every brick different from the three basic bricks , and the Petersen graph has a -invariant edge that is thin. It follows from this result that all bricks can be generated from the three basic bricks by means of four simple operations. A cut of a brick is a separating cut of if each of the two graphs obtained by shrinking a shore of to a single vertex is matching covered. A brick is solid if it does not have any nontrivial separating cuts. Solid bricks have many interesting properties ([4]) and may be thought of as building blocks of bricks themselves. The complexity status of deciding whether a given brick is solid is not known. Here, by using our theorem on the existence of thin edges, we show that every simple planar solid brick is an odd wheel.