Monografias em Ciência da Computação

2003

ABSTRACTS

Departmento de Informática 
Pontifícia Universidade Católica do Rio de Janeiro - PUC-Rio
Rio de Janeiro - Brazil

This file contains a list of the technical reports of the Departmento de Informática, Pontífícia Universidade Católica do Janeiro - PUC-Rio, Brazil, which are published in our series Monografias em Ciência da Computação (ISSN 0103-9741), edited by Prof. Carlos Lucena. Please note that the reports not available for download are available in their print format and can be obtained via the e-mail below.

For any questions, requests or suggestions, please contact:
Rosane Castilho bib-di@inf.puc-rio.br

Last update: 18/DECEMBER/2003

INDEX 

[MCC01/03]
PIMENTEL, M.G.; FUKS, H.; LUCENA, C.J.P. Perdas de co-texto em sistemas de bate papo textual. 12 p. Port. E-mail: hugo@inf.puc-rio.br

Abstract: The research presented in this article investigates a problem related to the lack of understanding of messages exchanged during chat sessions. There is confusion in the majority of the textual chat tools when various people converse at the same time. Sometimes a participant does not identify the relationship of a new message with a previous one, and is unable to establish a thread with the conversation - within this research this phenomenon is denominated "co-text loss". The causes, consequences and frequency of this phenomenon are discussed in this article. Two textual chat tools that have been developed to try to reduce the occurrence of co-text loss are presented in this article, together with the results obtained through the use of these tools during synchronous debates among undergraduate and postgraduate students in distance learning courses.


[MCC02/03]
FERREIRA, F.; LUCENA, J.C.P.; SCHWABE, D. Peer-to-peer architectures using asynchronous Web services. 14 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: In this paper, we describe Everyware, a platform for peer-to-peer aplications based on Web services standards. It is conceived to support personal information sharing among peers using different devices and hardware infrastructure. Using open standards and a completely distributed approach, everyware allows end users to deploy personal Web services easily without requiring configuration or administration efforts. A comparison with similar initiatives is made, centered on major issues of peer-to-peer architectures and Web services orchestration. A real application based on Everyware is presented and related implementation issues are discussed.


[MCC03/03]
COELHO, T.A.S.; BARBOSA, S.D.J. Usando um modelo de interação para análise de aplicações WIMP: um estudo de caso. 35 p. Port. E-mail: simone@inf.puc-rio.br

Abstract: This work presents a study about a WIMP application, with respect to the user-system interation model. The interaction model proposed and is evaluated as an alternative to other modeling techniques and is found to be simple and helpful for interface designers. An extension to this model is proposed, aiming to aggregate the dynamic interaction behavior, making it possible to represent in this model the fact that an action within a specific scene can affect other scenes, as occurs in applications in which the user can interact with more than one panel, such as many WIMP applications.


[MCC04/03]
LEMOS, M.; SEIBEL, L.F.B.; CASANOVA, M.A. Sistemas de anotações em biossequências. 75 p. Port. E-mail: casanova@inf.puc-rio.br

Abstract: The human genome project is a program to map and sequence the entire human genome. A number of model organisms were selected for complete sequencing, partly in order to develop new technology for mapping, sequencing and sequence analysis. In addition, the sequences from these genomes were expected to facilitate the elucidation of the functions of genes and sequences in the human genome. One of the most important tasks of genome projects is the interpretation of the experimental data in order to obtain biological knowledge of this data. The researchers execute this task searching external data sources, executing analysis programs on its sequences and generating manual annotations in accordance with its interpretation of the data. This monograph makes a survey of the existing annotation systems and presents the project and the implementation of 'BioNotes', which is a new system proposal that aims at bringing advantages to the researchers in this area.


[MCC05/03]
LEMOS, M.; BASILIO, A.; CASANOVA, M.A. Um estudo dos algoritmos de montagem de fragmentos de DNA. 42 p. Port. E-mail: casanova@inf.puc-rio.br

Abstract: The human genome project is a program to map and sequence the entire human genome. A number of model organisms were selected for complete sequencing, partly in order to develop new technology for mapping, sequencing and sequence analysis. In addition, the sequences from these genomes were expected to facilitate the elucidation of the functions of genes and sequences in the human genome. One of the main problems of DNA sequencing on a large scale is that its methods only obtain a small part of the DNA. After breaking a sequence into many fragments, cloning them and sequencing them, there is a set of fragments which needs to be merged for the reconstruction of the original DNA sequence. This monograph presents the biological and computational context of DNA sequence assembly.


[MCC06/03]
GARCIA, A.F.; SANT'ANNA, C.N.; CHAVEZ, C.v.F.G.; SILVA, V.T.; LUCENA, C.J.P.; STAA, A.v. Agents and objects: an empirical study on Software Engineering. 44 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: With multi-agent systems (MASs) growing in size and complexity, the separation of their concerns throughout the different development phases is a main need for MAS engineers. Separation of concerns is a well-known principle in software engineering to achieve improved reusability and maintainability of complex software. Hence it is necessary to investigate systematically whether established and evolving abstractions from Software Engineering are able to support the explicit separation of MAS concerns. This paper presents an empirical study that compares the maintenance and reuse support provided by abstractions associated with two OO techniques for MAS development: aspect-oriented development and pattern-oriented development. The gathered results have shown that the abstractions from the aspect-oriented approach allowed the construction of a MAS with improved separation of MAS concerns. Also, the use of this approach resulted in: (i) less lines of code, (ii) less components, (iii) lower component cohesion, and (iv) lower coupling between the components. An additional importance finding of this empirical study is that the aspect-oriented approach also supported a better alignment with higher-level abstractions from agent-oriented models.


[MCC07/03]
MILIDIÚ, R.L.; RENTERIA, R.P. MKPLS: a multi-kernel based partial least-squares regression. 14 p. Eng. E-mail: milidiu@inf.puc-rio.br

Abstract: MKPLS, a non-linear version of the Partial Least-Squares regression is presented. The non-linearity is introduced in the classical algorithm through the use of multiple kernel functions, thus providing an straightforward non-linear adaption. MKPLS provides a multi-kernel based version for the PLS algorithm with a competitive modeling error. Experimental results show that the use of different kernels for the regression model enhances the predictive power when compared to a PLS regression based on only one function kernel.


[MCC08/03]
SILVA, J.C.T.; FEIJÓ, B. Uma máquina de estados finitos para avaliação de desempenho em um grupo de discussão on-line. 15 p. Port. E-mail: bruno@inf.puc-rio.br

Abstract: This paper presents a finite state machine model to follow-up and to evaluate the student's performance in a web-based live debate. We use a variation of the Pichon-Rivière's Vinculum Theory to establish the mechanism that monitors each participant automatically and evaluates his/her progress as the debate is going on. We choose the finite state machine model because it is fast and has low computational complexity. This model satisfies the step-by-step evolution requirements and uses agent technology to perform the evaluation computing issues and to update the information to be used by the machine. This approach reduces the need for discourse structuring of the participants to a minimum. The state transitions use heuristics on the input data.


[MCC09/03]
STAA, A.v. Arcabouço para automação de testes de programas redigidos em C. 29 p. Port. E-mail: arndt@inf.puc-rio.br

Abstract: A test automation framework is presented. This framework is specifically geared towards modules written in C. Initially an abridged description of the key testing concepts is presented. Two test automation approaches are described. The first one uses a specific test module containing functions that exercise the module being tested. In this approach, the test suite corresponds to the source code of the test control module. The second approach is based on a framework that can be instantiated to test a specific module. The instantiated test control module implements a test script interpreter. In this approach the test suite is define by a test script specifically geared to sufficiently test the given module. The article also emphasizes incremental development of programs as well as of modules.


[MCC10/03]
PEREIRA, L.A.M.; PORTO, F.A.M.; MELO, R.N. Objetos de aprendizado reutilizáveis (RLOs): conceitos, padronização, uso e armazenamento. 42 p. Port. E-mail: rubens@inf.puc-rio.br

Abstract: In this work we list and discuss the concepts and characteristics of Reusable Learning Objects (or simply Learning Objects - RLO or LO) that are being considered by the literature as an efficient solution to cost-effective instructional content development for e-learning. In order to establish a common structure to describe these learning objects, the IEEE Learning Technology Standards Committee (IEEE-LTSC) is developing the Learning Object Metadata standard (LOM) that is being referenced by other important standards such as IMS and SCORM. In this work we propose a LO data model and discuss aspects related to the storage, search and retrieval of LOs from databases. In order to put into perspective the use of LOs by applications, we also propose a four-level database architecture as a reference model. Finally we discuss the automated and semi-automated construction of learning contents.


[MCC11/03]
PEREIRA, L.A.M.; CASANOVA, M.A. Sistemas de gerência de workflows: características, distribuição e exceções. 33 p. Port. E-mail: casanova@inf.puc-rio.br

Abstract: Workflows can be defined as any set of tasks that have to be executed in a coordinated way, in sequence and/or in parallel, by two or more individuals or teams sharing a common goal. Workflow Management Systems - WfMS - are pieces of software designed to automate, at least, the administrative/coordination tasks associated to workflows execution. In this work we will present the main concepts and characteristics of workflow systems considering, as a first step, centralized environments. Further on in the text, due to the typical necessity of workflows to cross departmental borders within an enterprise and between enterprises, we discuss extensions of WfMS required to allow cooperative work of individuals or teams that are geographically dispersed. In this work we also discuss issues related to possible failures during workflow executions.


[MCC12/03]
PEREIRA, L.A.M.; MELO, R.N. Um ambiente de banco de dados para ensino a distância baseado em workflow e objetos de aprendizado. 47 p. Port. E-mail: rubens@inf.puc-rio.br

Abstract: Effective e-learning environments should promote high cooperation. Workflow techniques can certainly contribute to such effectiveness because, in these environments, the creation and delivery of learning contents are typically accomplished by individuals through the execution of specific and predefined sequences of activities. Literature in this area has stressed the importance of workflow techniques in e-learning. However, it is also important to consider new methods that may reduce development costs such as reusability and standardization. In this work we propose the application of learning objects (LOs) and their standards. We define the architecture of a web-based heterogeneous and distributed database environment that permits partners to create and share a pool of learning objects. Such LOs may be primitive or recursively composed by aggregation. This environment is being proposed as a database solution for PGL (Partnership in Global Learning) which is an international e-learning project sharing a network of learning objects repositories.


[MCC13/03]
STAA, A.v. Acompanhamento de projetos. 17 p. Port. E-mail: arndt@inf.puc-rio.br

Abstract: In this article we examine some of the more relevant features of project tracking tools. It is not our intention to design the best possible tool, if such a thing exists. Rather we aim at providing a set of guidelines that may help a software development manager to choose among available tools. Of course the sketches may also be used as the starting point of a tool development project. Following, three tools will be outlined: time sheet; problem recording and tracking; and configuration item registering and tracking. The three tools can be integrated. If integrated, they help to reduce the effort to acquire tracking data. In this way we expect that more reliable project tracking data could be gained. An interesting side effect is the possibility to gather data that helps finding the true causes of quality and productivity problems.


[MCC14/03]
IERUSALIMSCHY, R.; FIGUEIREDO, L.H.; CELES, W. Lua 5.0 reference manual. 65 p. Eng. E-mail: roberto@inf.puc-rio.br

Abstract: Lua is a powerfull, light-weight programming language designed for extending applications. Lua is also frequently used as a general-purpose, stand-alone language. Lua combines simple procedural syntax (similar to Pascal) with powerful data description constructs based on associative arrays and extensible semantics. Lua is dynamically typed, interpreted from opcodes, and has automatic memory management with garbage collection, making it ideal for configuration, scripting, and rapid prototyping. This document describes version 5.0 of the Lua programming language and the Application Program Interface (API) that allows interaction between Lua programs and their host C programs.


[MCC15/03]
SILVA, V.T.; LUCENA, C.J.P. Extending the UML sequence diagram to model the dynamic aspects of multi-agent systems. 38 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: In this paper we present the dynamic aspects of multi-agent systems (MASs) based on the definition of their elements and relationships as proposed in the TAO metamodel. TAO is a conceptual framework based on agent and object abstractions that elicits an ontology connecting distinct abstractions such as objects, agents, organizations, roles and environments, and their relationships. The dynamic aspects of a MAS are particularly different from the dynamic aspects of an object-oriented system, since a MAS involves different entities and relationships between those entities. The dynamic aspects characterize interactions between the elements of multi-agent systems that are related. In order to model the dynamic aspects of MAS we propose extending the UML sequence diagram, introducing new features.


[MCC16/03]
SIQUEIRA, S.W.M.; BRAZ, M.H.L.B.; MELO, R.N. Developing learning objects through concepts and context. 11 p. Eng. E-mail: rubens@inf.puc-rio.br 

Abstract: The Internet has promoted several changes in the world, including on education. People have been more interested in learning, which makes developing higher quality content material even more important. In addition, people want to satisfy their learning needs according to their personal characteristics such as knowledge background and learning style. Therefore, nowadays there is a great interest on reusable learning content material and adaptive systems. Learning metadata standards contribute to achieve such reusability through the idea of learning objects. However, there is no guidance on how to develop learning objects, but only on how to describe them. The work presented in this paper proposes a model for structuring knowledge (concepts, demonstrations and interactions) in learning objects according to their context, representation and composition. This approach enables increased reusability and adaptability while providing better structured material.


[MCC17/03]
LEMOS, M.; ARAGÃO, M.V.S.P.; CASANOVA, M.A. Padrões em biossêquencias. 72 p. Port. E-mail: casanova@inf.puc-rio.br

Abstract: The goal of this work is to study known algorithms for automatic discovery of patterns in a set of biosequences. Patterns we want to find usually correspond to functionally or structurally important elements in proteins or DNA sequences. There is an assumption that these important regions are better conserved in evolution because they are important to the structure or function of the molecule. The discovery of such patterns can help in the understanding of relationships between biosequence, structure, and function of proteins and in a bigger context, help to interpret the working of living organisms. The pattern discovery is one of the fundamental problems in bioinformatics. It can be used in multiple biosequence alignment, protein structure and function prediction, characterization of protein families, promoter signal detection, and other areas.


[MCC18/03]
PAULA, M.G.; BARBOSA, S.D.J.; LUCENA, C.J.P. Relating human-computer interaction and Software Engineering concerns: towards extending UML through an interaction modeling language. 9 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: The UML suite of modeling languages fails to properly model the human-computer interaction. On the other hand, newly conceived HCI modeling languages need to foresee their role as members of the family of languages that constitute the UML representations for software design, due to their wide acceptance by both researchers and practitioners. MoLIC, our proposed HCI modeling language, seems to be a natural family member since many consistency checks seem to be possible between MoLIC and other software design notations used in UML. MoLIC is based on Semiotic Engineering and represents interaction as threads of conversation users may have with the system.


[MCC19/03]
MILIDIÚ, R.L.; LUCENA, C.J.P.; MELLO, C.G. Introducing security into prefix-free encoding schemes. 10 p. Eng. E-mail: milidiu@inf.puc-rio.br

Abstract: Minimum redundancy prefix-free codes are widely used to obtain high performance compression schemes. Given a prefix-free encoding for the symbols of a plain text, we propose a security enhancement by adding a multiple substitution algorithm with a key: the HSPC2 - Homophonic Substitution Prefix-free Codes with 2 homophones. Breaking the key when we are given a ciphertex, the dictionary, frequencies and codeword lengths, is a NP-Complete problem. In order to introduce security, some compression loss is generated. The compression loss is analysed and the data expansion per character is asymptotically smaller than 5% under usual parsing and coding assumptions. We also present some analytical results on the security impact of adding simple strategies to protect prefix-free encoded data.


[MCC20/03]
GERHARDT, A.; MACHADO, M.; SILVA, P.M.C.; GATTASS, M. Two-dimensional opacity functions for improved volume rendering of seismic data. 4 p. Eng. E-mail: mgattass@inf.puc-rio.br

Abstract: Although Volume Rendering has gained reputation as a powerful tool for visualizing complex structural and stratigraphic features embedded in 3-D seismic data, the complexity of the parameters involved still requires a lot of work in order to produce an informative image. One of such parameters assigns opacity levels to data-amplitude values to highlight the features of interest. The design of the opacity function usually follows a non-intuitive trial-an-error approach. The strong dependence of the rendered image on other optical parameters also contributes to make it a time-consumming task. Furthermore, some particularities of seismic data contribute to make such approach more suitable for the visualization of high-amplitude anomalies. This work describes a method for generating two-valued (amplitude and gradient) opacity functions that is able to better discrimininate mid-amplitude events
without obscuring them with other seismic features. Preliminary results using synthetic data are presented. Examples using real datasets will be presented at the 17th. International Congress of the Brazilian Geophysical Society.


[MCC21/03]
SILVA, P.M.C.; MACHADO, M.; GATTASS, M. 3D seismic volume rendering. 4 p. Eng. E-mail: mgattass@inf.puc-rio.br

Abstract: Volume Visualization has become a very useful tool for modern seismic interpretation. The main purpose of this technique is to obtain an overview of structural and stratigraphic features. Most of the currently available software for 3D seismic visualization employs the same rendering equations used in traditional medical imaging. However, the nature of seismic data demands a specialized implementation of the rendering pipeline. Traditional medical methods are designed to visualize isovalue contours that represent boundary surfaces within three-dimensional sampled scalar fields. In this context, the use of local gradient information to estimate surface normal at each voxel, during shading calculations, is a reasonable approach. This technique yields excellent results for mathematical fuctions and medical data. In 3D seismic data, however, the illumination of structural and stratigraphic features cannot be obtained with simple isovalue contour and gradient estimations. In this paper, we discuss the necessary modifications to the shading and classification steps of traditional algorithms. Our method combines 3D seismic data with a derived seismic attribute to better adapt the display of seismic events. The paper also presents results for both synthetic and real seismic data to validate our proposal.


[MCC22/03]
HAENDCHEN FILHO, A.; STAA, A.v.; LUCENA, C.J.P. A framework-based approach for building reliable multi-agent systems. 16 p. Eng. E-mail: arndt@inf.puc-rio.br 

Abstract: In this article we present a framework-based approach for rapid and large-scale development of reliable and reusable multi-agent systems (MAS). The agents are instanced through a specification framework and the reuse is achieved by the structural model propagation for multiples agents. Flexibility and agent adaptation capacity is ensured through the use of design patterns foundations, such as encapsulation, high-cohesion, low-coupling - and extensible structures. Quality control is based on three fundamentals: (i) formal specification; (ii) inspections; and (iii) testing. Formal systems specification leads to codes with less errors, and rigorous processes of verification and validation replace the mathematical proofs. The system reliability is assured by the testing tools and facilities provided to perform semi-automated inspections and test cases generation, applied together with an incremental testing strategy. The purpose is to reduce time, effort and costs associated with the design and development of MAS with high requirements of quality and reliability.


[MCC23/03]
PESSOA, A.A.; LABER, E.S.; SOUZA, C.P. On the worst case search in trees with hotlinks. 13 p. Eng. E-mail: laber@inf.puc-rio.br

Abstract: Let T be a rooted directed tree where nodes represent Web pages of a Web site and arcs represent hyperlinks. In this case, when a user searches for an information i, it traverses a directed path in T, from the root node to the node that contains i. In this context, we define hotlinks as additional hyperlinks added to web pages in order to reduce the number of accessed pages per search. In this work, we address the problem of inserting at most one hotlink in each Web page, minimizing the number of accesses in a worst case search. For this problem, we present an exact algorithm that runs in O(n(nm)2.284) time and uses O(n(nm)1.441) space, where n and m are the number of nodes (internal and external) and the number of leaves in T, respectively. We also introduce a (14/3)-approximate algorithm for the same problem, that runs in a O(n log m) time and requires a linear space.


[MCC24/03]
SILVA, V.T.; NOYA, R.C. Using the MAS-ML to model a multi-agent system. 14 p. Eng. E-mail: bib-di@inf.puc-rio.br

Abstract: The current object-oriented development practice system analysis is documented through UML artifacts such as Class and Sequence diagrams. Since UML is a widely accepted modeling language, it also would be desirable to offer a UML support for the representation of agent-based system analysis artifacts. Although some central UML constructs are suitably matched for agent-based modeling, several improvements must be made to the UML metamodel to achieve this new goal. This paper presents MAS-ML, a UML extension for agent-based system modeling. The use of MAS-ML for modeling agent-based systems is presented with simple illustrating application.


[MCC25/03]
LABER, E.S. A randomized competitive algorithm for evaluating priced. 14 p. Eng. E-mail: laber@inf.puc-rio.br

Abstract: Recently, the problem of evaluating AND/OR trees was investigated, with non uniform costs on its leaves, under the perspective of the competitive analysis. For an AND-OR tree T they presented a max{k(T),l(T)}-competitive deterministic polynomial time algorithm, where k(T) and l(T) are functions of the T's topology. Furthermore, they prove that max{k(T),l(T)} is a lower bound on the deterministic competitiveness, which assures the optimality of their algorithm. The power of randomization in this context has remained as an open question. Here, we give a step towards solving this problem by presenting a 0.792max{k(T(,l(T)}-competitive randomized polynomial time algorithm.


[MCC26/03]
SANTANNA, C.N.; GARCIA, A.F.; CHAVEZ, C.V.F.G.; LUCENA, C.J.P.; STAA, A.v. On the reuse and maintenance of aspect-oriented software: an assessment framework. 16 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Aspect-oriented software development (AOSD) is gaining wide attention both in research environments and in industry. Aspect-oriented systems encompass new software engineering abstractions and different complexity dimensions. As a consequence, AOSD poses new problems to empirical Software Engineering. It requires new assessment frameworks specifically tailored to measure the reusability and maintainability degrees of aspect-oriented systems. This paper presents an assessment framework for AOSD, which is composed of two components; a suite of metrics and a quality model. These components are based on well-known principles and existing metrics in order to avoid the reinvention of well-tested solutions. The proposed framework has been evaluated in the context of two different empirical studies with different characteristics, diverse domains, varying control levels and different complexity degrees. Based on empirical and quantitative analysis, the advantages and drawbacks of the framework components are discussed.


[MCC27/03]
GONZALEZ CLUA, E.W.; FEIJÓ, B.; CELES FILHO, W. Refração e reflexo para sistemas de visualização em tempo real utilizando portais. 14 p. Port. E-mail: bruno@inf.puc-rio.br

Abstract: This work presents an efficient method for simulating refraction and reflection phenomena for flat surfaces in real time, using portals and texture mapping. The method is easily extended to encompass more complex objects. This paper also claims that the combination of the proposed method with multi-texturing leads to a complete lighting framework for real-time rendering.


[MCC28/03]
GONZALEZ CLUA, E.W.; DREUX, M.; FEIJÓ, B. Utilização de nailboards para otimização em visualização distribuída entre CPU/GPU utilizando relief texture mapping. 15 p. Port. E-mail: bruno@inf.puc-rio.br

Abstract: With the increase power of graphics hardware, and in particular with the growing up techniques of programmable pipeline, a graphic application leaves the CPU with a big amount of idle time. In the sense of utilize this time, this work presents a technique that parallelize the rendering between CPU and GPU, using a thread of the CPU and the algorithm of Relief Texture Mapping in order to forward the results into the hardware pipeline. This propose lets many effects naturally inapropriate or difficult to be reached with hardware resources to be treated by the CPU without any crack in the total real time performance of the application.


[MCC29/03]
GONZALEZ CLUA, E.W.; FEIJO, B.; DREUX, M. Um método de avaliação genérico para sistemas de visualização baseados em imagens. 10 p. Port. E-mail: bruno@inf.puc-rio.br

Abstract: Much progress had been obtained in image-based rendering techniques and many others ideas are been developed and implemented in this area. Although, there isn't an ideal system that implements the plenoptic function in its totality in a viable aspect in relation to memory, CPU process and authory. The known and developed systems try to create a sub-set of the domain and image of the function, bringing in each implementation restrictions and limitations. These work is at the same time a survey of the main developed works and a tentative to create a set of criteria that allows a critic and comparative evaluation of these systems.


[MCC30/03]
MELE, A.; ENDLER, M. Um framework para a simulação de redes móveis ad-hoc. 11 p. Port. E-mail: endler@inf.puc-rio.br

Abstract: In this document we present MobiCS2, a flexible framework for prototyping and simulation of protocols for mobile ad hoc networks. After describing its structure and main hot spots, we present an instantiation of this framework for a simplified version of the DSR routing protocol using IEEE 802.11. 

[MCC31/03]
GARCIA, A.; SARDINHA, J.; LUCENA, C.; LEITE, J.; MILIDIÚ, R.; CASTRO, J.; ROMANOVSKY, A.; GRISS, M.; LEMOS, R.; PERINI, A. Software Engineering for Large-scale Multi-agent systems - SELMAS 2003: workshop report. 24 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: This paper is intended to sum the results of the Second International Workshop on Software Engineering for Large-Scale Multi-Agent Systems (SELMAS'03) held in Portland, Oregon, USA, May 3-4, 2003, as part of the International Conference on Software Engineering (ICSE'03). The main purpose of this workshop was to share and pool the collective experience of people, both academics and practitioners, who are actively working on software engineering for large-scale multi-agent systems. The call for papers elicited some 26 submissions, of which 19 papers were accepted for presentation. A selected set of the workshop papers and invited papers are to appear in the 2nd. edition of the book Software Engineering for Large-Scale Multi-Agent Systems (LNCS, Springer, 2003). The workshop consisted of an opening presentation, several paper presentations organized into five sessions, and three panels. During the workshop we informally reviewed ongoing and previous work and debated a number of important issues. The SELMAS'03 Web page, including the papers and the electronic version of this report, can be found at <www.teccomm.les.inf.puc-rio.br/selmas2003>. We begin by presenting an overview of our goals and the workshop structure, and then focus on the workshop technical program.


[MCC32/03]
CUNHA, L.M.; BRANDÃO, A.A.F.; ORLEAN, D.; ALBARELLO, A.B.; SCHROEDER, B.; LUCENA, C.J.P. Following up a case study for the semantic Web. 7 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: The Semantic Web has been proposed as an infrastructure for handling the complexity associated with the problem of information overload on the Web. The use of semantic markup languages such as DAML to describe web documents enables the application of a variety of agent related technologies. They allow, for instance, intelligent, automated, and more efficient (Web) services for searching, mining and maintaining information. These technologies leverage applications from e-commerce to knowledge management. This paper describes a case study based on the design and development of a Semantic Knowledge Portal for research projects to support R&D Knowledge Management for the TecComm Group, based on ontologies, Web services and other features of the Semantic Web.


[MCC33/03]
LEITE, J.C.S.P.; DOORN, J.H.; HADDAD, G.D.S.; KAPLAN, G.N. Using scenario inspections on different scenarios representations. 27 p. Eng. E-mail: julio@inf.puc-rio.br

Abstract: Scenarios heve been increasingly used as a strategy to help practioners to a better understanding of the requirements of a software system as well as its interface with the environment.  Despite its widespread use by either object-oriented development teams or by human computer interface designers, most of its use is still done in a very ad-hoc way. Departing from the requirements engineering viewpoint, this article aims to show how an inspection process helps software developers to better manage the production of scenarios independently of the representaion used.  We use Fagan inspection as the main paradigm to design the scenario inspection method.


[MCC34/03]
KOZOVITS, L.E.; DREUX, M.; FEIJÓ, B. Um estudo para visualização de objetos com geometria dinâmica em jogos multi-jogador. 20 p. Port. E-mail: bruno@inf.puc-rio.br

Abstract: In the last years, many techniques have been developed to improve the quality, in terms of graphical effects, of multiplayer games, a specialized field in networked virtual environments (Net-VE). Although new techniques have been developed to provide, also, efficient network use in those games, some challenges in this area still remain. A new technique to distribute objects among game players during a session, based on its geometric representation, is proposed in this work in order to overcome the Internet bandwidth limitations.


[MCC35/03]
KOZOVITS, L.E.; MELO, R.N.; FEIJÓ, B. Um estudo do uso de SGBDs relacionais em arquiteturas de jogos multi-jogador. 24 p. Port. E-mail: bruno@inf.puc-rio.br

Abstract: Massively Multiplayer game technology is both a growing and profitable business and a rich field, nowadays, of research due to its multidisciplinary nature. Although being a specialized field in networked virtual environments (Net-VE), multiplayer games have some unique requisites and demand some technologies not common to all Net-VE applications. Therefore, an analysis of the use of RDBMSs in those game architectures, became interesting in order to investigate the possibilities of new uses or improvements. A new technique to obtain game session balance, a feature often desired in those architectures, is proposed based on the use of RDBMSs.


[MCC36/03]
KOZOVITS, L.E.; FEIJÓ, B. Arquiteturas para jogos massive multiplayer. 17 p. Port. E-mail: bruno@inf.puc-rio.br

Abstract: Multiplayer game technology is a specialized field in networked virtual environments (Net-VE). With the increasing popularity of Internet games, an analysis of the related problems and solutions of these environments became interesting in order to adapt them to the specific needs of these games. A hybrid architecture using both client-server and peer-to-peer aproach is proposed and implemented in this work for a certain class of multiplayer games.


[MCC37/03]
MELO, F.; CHOREN, R.; CERQUEIRA, R.; LUCENA, C.J.P.; BLOIS, M. An agent deployment model based on components. 14 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: In the past few years, the Multi-agent systems (MAS) area has presented an accelerated growth. New techniques and tools are constantly being proposed and several methodologies have been published to support the development of MAS. Most of these methodologies concentrate on the system analysis phase, giving almost no support for MAS implementation. Since agents can be seen as sort of specialized distributed components, in this paper we propose an agent deployment model based on the CORBA Component Model. We also describe a case study to show the potential of an agent-based application development using this model.


[MCC38/03]
POZZER, C.T.; FEIJÓ, B.; CIARLINI, A.E.M. Proposição de um novo paradigma de conteúdo para TV interativa. 38 p. Port. E-mail: bruno@inf.puc-rio.br

Abstract: In this work, we initially present a general survey on hardware and software technologies for Interactive TV. We then propose methods for generating and presenting interactive stories, which could be seen as a new paradigm for interactive content. The story generation process is accomplished by a simulating process resulting in a set of operations that define the plot of the story. The generated story should then be graphically represented, using Artificial Intelligence techniques, by the animation of the virtual characters. The user interaction during the generation and presentation processes is also widely discussed.


[MCC39/03]
POZZER, C.T.; FURTADO, A.L.; CIARLINI, A.E.M. Agentes e emoções em histórias interativas. 30 p. Port. E-mail: furtado@inf.puc-rio.br

Abstract: This work presents a general survey on agent and multi-agent technologies, with special attention to autonomous characters, frequently used in intelligent electronic games. All characters should encapsulate resources that allow them to represent graphically typical events of stories dynamically created by means of a simulation process. The agents can interact with each other and with the scene to which they belong. They should also reflect users' interactions. The resources are implemented over an architecture that integrates modules for generation, representation and exhibition of interactive stories.


[MCC40/03]
POZZER, C.T.; DREUX, M.; FEIJO, B. Representação gráfica de histórias interativas. 28 p. Port. E-mail: bruno@inf.puc-rio.br

Abstract: This work presents a general architecture to represent dynamic interactive stories which encapsulates the generation, execution and visualization of those stories, given a special attention to the visualization process, by means of Computer Graphics techniques. It has been used cinematographic techniques to capture the essence of the scene, which are composed by a virtual 3D environment. Characters, implemented as reactive agents, interact among each other and with the scene to accomplish the plot of the narrative.


[MCC41/03]
PESSOA, A.A.; LABER, E.S.; SOUZA, C.P. Efficient implementation of a hotlink assignment algorithm for Web sites. 12 p. Eng. E-mail: laber@inf.puc-rio.br

Abstract: Let T be a rooted directed tree where nodes represent Web pages of a Web site and arcs represent hyperlinks. In this case, when a user searches for an information i, it traverses a directed path in T, from the root node to the node that contains i. In this context, we define hotlinks as additional hyperlinks added to web pages in order to reduce the number of accessed pages per search. Given a search probability for Web page, we address the problem of inserting at most one hotlink per page, minimizing the expected number of accesses in a search. In a previous work, we proposed a dynamic programming polynomial time algorithm for this problem, assuming that the height of T is logarithmic. In this paper, we present an efficient implementation for the previous algorithm that leads to optimal or quasi-optimal hotlinks assignments. We also describe experiments with 1,914 trees extracted from 21 actual Web sites and randomly generated access probabilities. Our implementation has found optimal solutions to all but two generated instances in up to five minutes each, using a standard computer. The largest solved instance has 57,877 nodes.


[MCC42/03]
GOMES, A.T.A.; COULSON, G.; BLAIR, G.S.; SOARES, L.F.G. A component-based approach to the creation and deployment of network services in the programmable Internet. 23 p. Eng. E-mail: lfgs@inf.puc-rio.br

Abstract: Dynamism and simplicity in service creation and service deployment are recurring preoccupations to service designers. Although significant research has been carried out in both areas, we belive there remains a need for a better integration of them. The present work is an effort to apply component-based software concepts 'anywhere', from high-level service specifications to low-level software implementation in programmable network devices. This paper presents LindaX, an architecture description language that aims at guiding designers through the use of these concepts in a principled way.

[MCC43/03]
BARUQUE, L.B.; PORTO, F.; MELO, R.N. Towards an instructional design methodology based on learning objects. 7 p. Eng. E-mail: rubens@inf.puc-rio.br

Abstract: Instructional System Development (ISD) is a set of procedures for systematically designing and developing instruction. The development of contents for e-learning can well benefit from the ISD approach. However, we need to revisit the traditional ISD in order to incorporate the Learning Object (LO) paradigm. LOs are self-contained chunks of online content, which can be reusable and interoperable. In this work, we propose a methodology to design e-learning contents based on the ISD and LO technologies. We also suggest the use of learning theories principles in the chunking and sequencing of LOs in e-learning modules. The methodology is currently being tested by K-12 teachers from public schools as well as instructional designers from private companies in Brazil.


[MCC44/03]
CORTÉS, M.I.; FONTOURA, M.F.M.C.; LUCENA, C.J.P. A rule-based approach to framework evolution. 22 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Framework development is very expensive, not only because of the intrinsic difficulty related to capturing the domain knowledge, but also because of the lack of appropriate methods and techniques to support the evolution of the framework architecture. In this paper, we introduce the concept of evolution rules and describe its role in the context of framework development. Evolution rules allow the restructure and the addition of new features into the framework design, making sure that these changes are consistent with the applications previously instantiated. There are two kinds of evolution rules: refactorings and extensions. We describe both of them, showing how they can be combined to provide a useful support to framework evolution. In addition, we propose a methodology to prove the correctness of evolution processes. This methodology is based on CCS formalism and model checking techniques. The evolution approach is illustrated through Avestruz, a framework for web searching.


[MCC45/03]
STAA, A.v. Extensão do arcabouço para a automação dos testes de programas redigidos em C. 27 p. Port. E-mail: arndt@inf.puc-rio.br

Abstract: A module test automation framework is presented. This framework is specifically geared towards modules written in C. This paper extends chapter Instrumentação in tehe book by Staa, A.v.; Programação Modular. Rio de Janeiro: Campus, 2000 and also Arcabouco para Automacao de Testes de Programas Redigidos em C by the same author. The extensions described here comprise a module designed to perform passage counting. This instrument may be used to control the quality of the test suite. Another extension involves the control of data spaces accessed by means of pointers. Using this instrument the programmer is able to verify the type correctness of dynamic data spaces and may also observe the occurrence of buffer overflows and memory leaks.


[MCC46/03]
PIMENTEL, M.G.; FUKS, H.; LUCENA, C.J.P. Embutindo mecanismos de coordenação em ferramentas de bate-papo. 16 p. Port. E-mail: hugo@inf.puc-rio.br

Abstract: This research project investigates the coordination of debates using chat tools. In order to evaluate the Mediated Chat 2.0 tool, which implements coordination mechanisms to facilitate the application of group conversation techniques, debates were held during a distance education course using the AulaNet learningware. The logs were analyzed to evaluate how appropriately the proposed mechanisms helped during the coordination of the chat.


[MCC47/03]
SAYÃO, M.; STAA, A.v.; LEITE, J.C.S.P. Qualidade em requisitos. 31 p. Port. E-mail: arndt@inf.puc-rio.br

Abstract: In this article we tackle different quality measurement and improvement techniques that can be applied over requirements documentation generated using a classical software approach. Recent literature points to the fact that over 50% of faults detected during test can be traced down to problems in the requirements documentation. In particular, defective requiremens are pointed as the main cause of faults in software projects. Requirements artifacts quality can be measured using approapriate metrics, indicators and tests. A critical analysis of these artifacts can be obtained by the use of inspections. Software metrics provide substancial information to project managent and can be applied during different development stages. Inspections help the early detection of faults. At the core of the inspection process is identifying the information to be inspected and the techniques that will be used to uncover defects. In this paper we present metrics and techniques that can be used in the inspection of requirement documentation generated using a classical software approach.


[MCC48/03]
ALBUQUERQUE, A.L.P.; VELHO, L. Togetherness through virtual worlds: how real can be that presence? 14 p. Eng. E-mail: bib-di@inf.puc-rio.br

Abstract: Virtual worlds aim to give users a sense of being present in these environments by sharing that space and experiences with others. We analyse physical presence and togetherness for social interactions in virtual worlds, based on the users' report of two different platforms available on the Internet and discuss how real this presence can be by adding new technologies to existing ones.


[MCC49/03]
ALBUQUERQUE, A.L.P.; MELO, R.; VELHO, L. Connecting the presence's factors for guiding measurements. 10 p. Eng. E-mail: rubens@inf.puc-rio.br

Abstract: This work presents a model as a first insight to discuss the relationships among parameters that affect presence. It is a step in the direction of delimiting the range of causal relationships for the presence phenomenon, as part of an ongoing research towards a framework for measuring presence.


[MCC50/03]
BRAUNER, D.; BRANDÃO, A.A.F.; CUNHA, L.M.; LUCENA, C.J.P. Um estudo de caso para avaliação do Knowledge Unified Process para o desenvolvimento de ontologias. 72 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: Knowledge Unified Process (KUP) is an ontology development process that brings together activities from other ontology development methodologies and some software development best practices. This process has been applied to a case study, the ontology development process of an information security alert ontology, to evaluate its usage. The evaluation was based in an instance of an evaluation framework for methodologies and methods. As a result, we believe that KUP's iterative and controlled approach contributes to the ontology development process although there are still some deficiencies that should be tackled so that the process can become more comprehensive.


[MCC51/03]
SILVA, V.T.; NOYA, R.C.; LUCENA, C.J.P. An UML based approach for modeling and implementing multi-agent systems. 10 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: In this paper we present an agent-oriented modeling language called MAS-ML and an approach for mapping MAS-ML diagrams into Java implementations. MAS-ML extends the UML meta-model describing new meta-classes and stereotypes, extending the class and sequence diagrams and proposing two new diagrams: organization and role diagram. The paper also relates MAS-ML to other modeling languages that also extend the UML for modeling multi-agent systems.


[MCC52/03]
CUNHA, L.M.; FUKS, H.; LUCENA, C.J.P. Supporting groups and group formation through software agents in a Web based learning environment. 23 p. Eng. E-mail: hugo@inf.puc-rio.br

Abstract: In this work, it is presented how an environment for distance learning, AulaNet, was prepared to support groups. Besides that, software agents were used to help teachers in setting groups of learners. The complexity of work and the dissemination of the information and communication technologies value and make group work a potential allied for the educational or commercial organizations. The AulaNet supports learning in groups and can also be used to support group work, so it is a groupware system that is based on the research from Computer Supported Cooperative Work. In Software Engineering, multi-agent systems provide a properly level of abstraction for the treatment of complex and distributed problems as those characterized by distributed environments such as AulaNet.


[MCC53/03]
CUNHA, L.M.; FUKS, H.; LUCENA, C.J.P. Setting groups of learners using matchmaking agents. 6 p. Eng. E-mail: hugo@inf.puc-rio.br

Abstract: Nowadays, the complexity of work and the dissemination of the information and communication technologies value and make group work a potential allied for the organizations. The computer support offered under the umbrella of groupware systems is based on the research from Computer Supported Cooperative Work (CSCW). The support for the workers should be given since the group formation until its dissolution, going through the group work itself. In Software Engineering, multi-agent systems provide a property level of abstraction for the treatment of complex and distributed problems. One of these problems is characterized by environments for group work and/or learning in groups. In this paper it is presented the study and how a multi-agent system was implemented in the AulaNet environment, which is a groupware for Web-based teaching and learning, to help group formation.


[MCC54/03]
GEROSA, M.A.; FUKS, H.; LUCENA, C.J.P. Analysis and design of awareness elements in collaborative digital environments: a case study in the AulaNet learning environment. 18 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: In this paper an analysis is made about how awareness in digital learning environments relates to communication, coordination and cooperation and, consequently, collaboration. A collaboration model, where awareness occupies a central position, is presented. The awareness elements of the AulaNet environment are also analyzed, seeking to identify what awareness information is relevant, how it is generated, how the awareness elements were defined and how individuals control them. This analysis seeks to provide information regarding a project about awareness elements in collaborative digital learning environments.


[MCC55/03]
SANT'ANNA, C.N.; GARCIA, A.F.; LUCENA, C.J.P. Evolução de um sistema multi-agentes: implementando mobilidade em agentes de informação. 12 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: Development of software agents involves multiple concerns (properties), such as autonomy, adaptation, interaction, learning, and mobility. As software engineering for multi-agent systems (MASs) evolves, there is a need for better understanding of the relationships between its concerns and abstractions from object-oriented (OO) software engineering. Hence it is necessary to investigates sytematically whether OO techniques and abstractions support explicit modularization of these concerns and consequently the development of software agents that are easier to understand, evolve and reuse. This paper presents a study about the evolution of the design and code of a particular multi-agent system. We used two distinct OO techniques to introduce the mobility property in information agents of this MAS: design patterns and aspects. In this study, we assessed the two techniques in order to verify which approach demands less effort during the realization of this scenario. The assessment was based on a suite of metrics.


[MCC56/03]
MILIDIÚ, R.L.; LIPORACE, F.S. Planning of pipeline oil transportation with interface restrictions is a difficult problem. 9 p. Eng. E-mail: milidiu@inf.puc-rio.br

Abstract: An important constraint when developing a schedule for the operation of an oil pipeline is the interface between adjacent products. Due to the resulting quality loss, some products are not allowed to be adjacent inside the pipeline. The S-PPI decision problem asks about the existence of a feasible pipeline operations sequence that takes into account this additional restriction. We show that S-PPI is NP-complete. An immediate implication from this finding is that the planning of pipeline transportation with interface restrictions for general topology pipeline networks is also difficult.

[MCC57/03]
SANTOS, I.H.F.; RAPOSO, A.B.; GATTASS, M. Finding solutions for effective collaboration in a heterogeneous industrial scenario. 11 p. Eng. E-mail: mgatass@inf.puc-rio.br

Abstract: This work introduces a model that categorizes computer-supported collaboration in different levels, according to its support for communication, coordination, cooperation and interoperability. This model is useful for defining the level of collaboration needed in real scenarios or the level that is possible to achieve with the available technology, resources and working culture. These ideas are illustrated by collaborative tools in the field of Computer Graphics being developed for a large oil & gas company.