Monografias em Ciência da Computação

2004

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, Pontifí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: 27/DECEMBER/2004

INDEX

[MCC01/04]
FUKS, H.; RAPOSO, A.B.; GEROSA, M.A.; LUCENA, C.J.P. Applying the 3C model to groupware engineering.  33 p. Eng. E-mail:  hugo@inf.puc-rio.br

Abstract: This paper introduces an approach based on the 3C collaboration model (communication, coordination and cooperation) to the development of collaborative systems. This approach is denominated Groupware Engineering, which is based on Software Engineering, enhanced by concepts originated from the field of Computer Supported Cooperative Work - CSCW and related areas. The 3C model is studied by means of a detailed analysis of each one of its three elements, accompanied by a case study of a learningware together with the methodology of a web-based course, both designed based on the model. Moreover, the paper describes a component based system architecture following this 3C approach.

[MCC02/04]
PESSOA, A.A. Planning the transportation of multiple commodities in bidirectional pipeline networks.  20 p. Eng. E-mail: bib-di@inf.puc-rio.br

Abstract: PTP is a combinatorial model for oil pipeline transportation. It uses a directed graph G and a set of product batches, where each batch has a corresponding destination node. The graph G has an associated initial state where each arc contains a non-empty sequence of batches and each node contains a (possibly empty) set of batches. A valid movement is to shift the batches of a given arc  a=(i,j) in such a way that one batch from the node i is inserted in the beginning of the arc a and another batch, removed from the end of the arc a, is inserted in j.  The goal is to reach a state where all batches from a given subset are stored at their destinations. For the general PTP, deciding whether or not a feasible plan exists is proved to be NP-hard. In this paper, we propose the CBPTP, a new variation of PTP. In this variation, arc contents may be shifted in both directions. Moreover, product batches have no destination nodes assigned. Instead, we assign a commodity to each batch. In this case, the node demands that may be satisfied by any batches of the corresponding commodities. For the general CBPTP, we reduce the instance feasibility to the problem of finding a perfect matching in a bipartite graph. Moreover, we give a polynomial algorithm for constructing feasible plans for the CBPTP, when they exist.

[MCC03/04]
LEMOS, M.; SEIBEL, L.F.B.; CASANOVA, M.A. Functional requirements of biosequence annotation systems.  21 p. Eng. E-mail: casanova@inf.puc-rio.br

Abstract: One of the most important tasks of genome projects is the interpretation of experimental data in order to derive biological knowledge from the data. To achieve this goal, researchers typically search external data source, execute analysis programs on the biosequences, analyze existing annotations and add new annotations to register their interpretation of the data. This paper first summarizes selected tools and techniques used in Bioinformatics. Then, it lists functional requirements for biosequence annotation systems. It proceeds to describe the functionality and the data model of BioNotes, a tool that meets these requirements. Next, it outlines how the tool will support workflow-like composition of analysis programs. Finally, it compares BioNotes with other annotation systems. BioNotes is under development at the Catholic  University of Rio de Janeiro and in use at Oswaldo Cruz Institute and at RioGene.

[MCC04/04]
MOURA, A.L.; RODRIGUEZ, N.; IERUSALIMSCHY, R. Coroutines in Lua. 13 p. Eng. E-mail: noemi@inf.puc-rio.br

Abstract: After a period of oblivion, a renewal of interest in coroutines is being observed. However, most current implementations of coroutine mechanisms are restricted, and motivated by particular uses. The convenience of providing true coroutines as a general control abstraction is disregarded. This paper presents and discusses the coroutine facilities provided by the language Lua, a full implementation of the concept of asymmetric coroutines. It also shows that this simple but powerful construct supports easy and succint implementations of useful control behaviors such as generators, backtracking and cooperative multitasking.

[MCC05/04]
ROSSETTO, S.; RODRIGUEZ, N.; IERUSALIMSCHY, R. Abstrações para o desenvolvimento de aplicações distribuídas em ambientes com mobilidade. 14 p. Port. E-mail: noemi@inf.puc-rio.br

Abstract: In this paper, we discuss adequate abstractions and mechanisms for developing distributed applications in mobile environments. We argue that coordination and event orientation are important technologies for these environments. To show that these technologies can be used in conjunction with well-known, conventional programming models, we describe a system with synchronous and asynchronous remote procedure call that we implemented over an event-oriented tuple space. To implement synchronous calls in an asynchronous environment, we used the coroutine provided by the Lua programming language.

[MCC06/04]
SILVA, V.T.; LUCENA, C.J.P. Modeling multi-agent systems.  11 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Different methodologies, languages and platforms for multi-agent systems propose very distinct and varied sets of abstraction. In this context, there is a need for creating a conceptual framework that defines the frequently used multi-agent system abstractions, their relationships and their behavior. As it is the case with any new software engineering paradigm, the successful and widespread deployment of multi-agent systems require modeling languages, among other agent-based software technologies, that explore the use of agent-related abstractions and promote the traceability from the design models to code. This paper contemplates the definition of a multi-agent system conceptual framework called TAO and of a multi-agent system modeling language called MAS-ML. Our goals are to describe the structural and dynamic aspects of the abstractions commonly used in multi-agent systems by defining a conceptual framework, to propose a modeling language that describes structural and dynamic diagrams to model such aspects and to present the traceability from the structural models into code.

[MCC07/04]
SARDINHA, J.A.R.P.; GARCIA, A.F.; LUCENA, C.J.P.; MILIDIU, R.L. On the incorporation of learning in open multi-agent systems: a systematic approach.  17 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: The development of large scale multi-agent systems (MASs) requires the introduction and structuring of the learning property throughout the design and implementation stages. In open systems and complex environments, agents have to reason and adapt through machine learning techniques in order to perform their goals. In this paper, we present a methodology to introduce learning techniques into software agents. To assist the design phase, we present a design pattern that guides the design of the learning property. The methodology and pattern are used in     the construction of an open MAS for the Trading Agent Competition environment in order to illustrate the suitability of our approach.

[MCC08/04]
SILVA, V.T.; LUCENA, C.J.P. Extending UML to model multi-agent systems. 12 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Multi-agent systems (MASs) and object-oriented systems (OOSs) differ in many respects. Traditionally, OOSs are composed of objects whose properties are attributes and methods and interact through method calling. MASs are composed not only of objects but of different elements (such as agents, organizations and others) that have different properties and interact in different ways. MASs require modeling languages, among other agent-based software technologies, that are able to explore the use of agent-related abstractions. Modeling languages should represent the structural (or static) and dynamic aspects of MASs by expressing the characteristics of all its essential entities. Structural aspects comprise the definition of the entities, their properties and their relationships. The   dynamic aspects are characterized by the internal execution of the entities and by the interactions between the entities. In this paper we propose to extend the UML modeling language in order to model the structural and dynamic
aspects of MASs.

[MCC09/04]
PAES, R.B.; ALMEIDA, H.O.; LUCENA, C.J.P.; ALENCAR, P.S.C. Enforcing interaction protocols in multi-agent systems.  16 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Numerous multi-agent approaches have been used to develop large and complex systems in many application areas. Interactions among agents, which are commonly ruled by interaction protocols that ensure the correct system execution, constitute one of the main features of these approaches. However, in open, dynamic, and heterogeneous systems, where there are no guarantees about the trustfulness of the agents, mechanisms should be provided to ensure protocol fulfillment. In this paper we propose a conceptual framework and its implementation to enforce secure interaction protocols in multi-agent systems. We use the organization law abstraction as a generalization of other concepts found in the literature, such as constraints, policies, norms and protocols. Finally, the proposed conceptual framework allows laws to be defined as declarative specifications.

[MCC10/04]
LONGO, H.; ARAGÃO, M.V.P.; UCHOA, E. Solving capacitated arc routing problems using a transformation to the CVRP.  12 p. Eng. E-mail: poggi@inf.puc-rio.br

Abstract: A well known transformation by Pearn, Assad and Golden reduces a Capacitated Arc Routing Problem (CARP) into an equivalent Capacitated Vehicle Routing Problem (CVRP). However, that transformation is regarded as     unpractical, since an original instance with r required edges is turned into a CVRP over a complete graph with 3r + 1 vertices. We propose a similar transformation that reduces this graph to 2r + 1 vertices, with the additional restriction that r edges are already fixed to 1. Using a recent branch-and-cut-and-price algorithm for the CVRP, we observed that it yields an effective way of attacking the CARP, being significantly better than the exact methods created specifically for that problem. Computational experiments obtained improved lower bounds for almost all open instances from the literature. Several such instances could be solved to optimality.

[MCC11/04]
SILVA, R.J.M.; RAPOSO, A.B.; GATTASS, M. Grafo de cena e realidade virtual.  52 p. Port. E-mail: mgattass@tecgraf.puc-rio.br

Abstract: Several applications in the field of Virtual Reality (VR) are using scene graphs to represent the virtual environment, since the optimizations offered by these libraries increase the frame rates of the visualization. The increase in the frame rates enhances the immersion sensation, a fundamental characteristic of a VR environment. This text presents a study about the scene graph concept, higlighting the OpenGL Performer and the OpenSceneGraph. Some of the main concepts and tools of VR are also described, as well as their relations with scene graphs.

[MCC12/04]
SARDINHA, J.A.R.P.; CHOREN, R.; MILIDIÚ, R.L.; LUCENA, J.C.P. Engineering machine learning techniques into multi-agent systems. 28 p. Eng. E-mail: milidiu@inf.puc-rio.br

Abstract: Agent technology is a Distributed Artificial Intelligence (DAI) approach to implement autonomous entities driven by beliefs, goals, capabilities, plans and agency properties: adaptation, interaction, learning, etc. Software agents are the focus of considerable research by the artificial intelligence community, but there is still much to be done in the field of Software Engineering in order to systematically create large scale multi-agent systems. In this paper, we present an object-oriented framework for building a distributed multi-agent system. We explore in this framework the intersection of DAI with machine learning techniques, and propose a methodology for introducing intelligence in a multi-agent system. A multi-agent system created for the Trading Agent Competition is presented as a case study. Our engineering approach provides a performance gain of 97,3% due to the introduction of machine learning techniques.

[MCC13/04]
SANTOS, A.C.; LUCENA, A.; RIBEIRO, C.C. Solving diameter constrained minimum spanning tree problems in dense graphs.  10 p. Eng. E-mail: celso@inf.puc-rio.br

Abstract: In this study, a lifting procedure is applied to some existing formulations of the Diameter Constrained Minimum Spanning Tree Problem. This problem typically models network design applications where all vertices must communicate with each other at minimum cost, while meeting or surpassing a given quality requirement. An    alternative formulation is also proposed for instances of the problem where the diameter of feasible spanning trees can not exceed given odd numbers. This formulation dominated their counterparts in this study, in terms of the computation time required to obtain proven optimal solutions. First ever computational results are presented here for complete graph instances of the problem. Sparse graph instances as large as those found in the literature were solved to proven optimality for the case where diameters can not exceed given odd numbers. For these applications, the corresponding computation times are competitive with those found in the literature.

[MCC14/04]
RIBEIRO, C.C.; URRUTIA, S.A. An application of integer programming to playoff elimination in football championships.  11 p. Eng. E-mail: celso@inf.puc-rio.br

Abstract: Football is the most followed and practiced sport in Brazil, with a major economic importance. Thousands of jobs depend directly from the activity of the football teams. The Brazilian national football championship is followed by millions of people, who attend the games in the stades, follow radio and TV transmissions, and check newspapers, radio, TV, and, more recently, the Internet in search of  information about the performance and chances of their favorite teams. Teams which are not qualified to the playoffs loose a lot of money and are even forced to dismantle their structure. We comment and compare the complexity of playoff elimination in football and baseball championships. We present two integer programming models which are able to detect in advance when a team is already qualified to or eliminated from the playoffs. Results from these models can be used not only to guide teams and fans, but are also very useful to identify and correct wrong statements made by the press and team administrators. The application and the use of both models in the context of the 2002 edition of the Brazilian national football championship are discussed.

[MCC15/04]
MOURA, A.L.; IERUSALIMSCHY, R. Revisiting coroutines.  31 p. Eng. E-mail: roberto@inf.puc-rio.br

Abstract: This paper defends the revival of coroutines as a general control abstraction. After proposing a new classification of coroutines, we introduce the concept of full asymmetric coroutines and provide a precise definition for it through an operational semantics. We then demonstrate that full coroutines have an expressive power equivalent to one-shot continuations and one-shot partial continuations. We also show that full asymmetric coroutines and one-shot partial continuations have many similarities, and therefore present comparable benefits. Nevertheless, coroutines are easier implemented and understood, specially in the realm of procedural languages. Finally, we provide a collection of programming examples that illustrate the use of full asymmetric coroutines to support direct and concise implementation of several useful control behaviors, including cooperative multitasking.

[MCC16/04]
VIEIRA, C.E.C.; SOUZA, R.C.; RIBEIRO, C.C. Um estudo comparativo entre três geradores de números aleatórios.  33 p. Port. E-mail: celso@inf.puc-rio.br

Abstract: The objective of this work is to compare three random number generators used by the research group on Heuristic and Parallelism for Optimizatiom/Bioinformatics Problems of the Informatics' Department of PUC-Rio. The random number generators are used in probabilistic algorithms, such that Simulated Annealing, Genetics Algorithms and GRASP. Therefore, the use of a consistent random number generator method is highly recommended. Firstly, the three random number generators are presented. Secondly, theoretical and statistical tests used to analyze generators are discussed. Practical questions, such as algorithm efficiency, portability, facility of implementation are also used to analyze generators. Based on the tests results and many criteria used in the analysis, the best generator for the research group is pointed out.

[MCC17/04]
SANT'ANNA, C.N.; GARCIA, A.F.; KULESZA, U.; LUCENA, C.J.P.; STAA, A.v. Design patterns as aspects: a quantitative assessment.  17 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Design patterns offer flexible solutions to common problems in software development. Recent studies have shown that several design patterns involve crosscutting concerns. Unfortunately, object-oriented (OO) abstractions are often not able to modularize those crosscutting concerns, which in turn decrease the system reusability and maintainability. Hence, it is important verifying whether aspect-oriented approaches support improved modularization of crosscutting concerns relative to design patterns. Ideally, quantitative studies should be performed to compare object-oriented and aspect-oriented implementations of classical patterns with respect to important software engineering attributes, such as coupling and cohesion. This paper presents a quantitative study that compares aspect-based and OO solutions for a representative set of design patterns. We have used stringent software engineering attributes as the assessment criteria. We have found that most aspect-oriented solutions improve separation of pattern-related concerns, although some aspect-oriented implementations of specific patterns resulted in higher coupling and more lines of code.

[MCC18/04]
RENTERIA, R.P.; MILIDIÚ, R.L. PLS based regression algorithms and their use in multi-agent systems.  11 p. Eng. E-mail: milidiu@inf.puc-rio.br

Abstract: We present new algorithms aimed at prediction, based on traditional techniques such as partial least-squares and principal component analysis regression. Along, some experiments are reported showing the possible use of these techniques as an AI engine in a multi-agent system.

[MCC19/04]
BARUQUE, L.B.; MELO, R.N. Towards a reference model for e-learning governance.  12 p. Eng. E-mail: rubens@inf.puc-rio.br

Abstract: It is increasingly recognized that e-learning is crucial to the success of organizations. In an era where the intellectual capital is considered to be the most valuable asset of a company, surprisingly not too much attention is given to the risks and threatens faced by e-learning endeavours. The ultimate goal of e-learning is to enable the business by delivering the knowledge, skills and attitudes (SKA) that the business needs in a cost-effective way. The critical role that e-learning is playing calls for a specific focus on governing it. To this end, we are launching the term e-Learning Governance (a new concept). e-Learning Governance can be defined as the responsibilities and practices carried out with a view to providing strategic direction to an institution's e-learning initiatives, ensuring that established objectives are achieved and risks managed properly, as well as that resources allocated are used responsibly. We need to go beyond methodologies for developing e-learning modules and extend the governance principles to all stages of e-learning. What we need is a Reference Model, independent of technical platforms, organizational structures and pedagogical frameworks, which is proposed in this paper.  Our Reference Model conceptual framework encompasses an e-learning information architecture, processes and sub-processes and governance rules and metrics. We exemplify how the governance rules and metrics can be used to control and secure e-learning systems. Further research is being carried out in the Database Lab at PUC-Rio to specify the Reference Model in detail.

[MCC20/04]
BARUQUE, L.B.; MELO, R.N. Applying learning theory in the design of learning objects.  16 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. A solid foundation in learning theory is an essential element in the application of ISD. One question that one might ask is if there is one best learning theory for instructional design using learning objects (LOs). Depending on the learners and situation, different learning theories may apply. We do not recommend one particular theory for the design of instruction based on LOs. We, rather, suggest the adoption of an ecletic approach to learning theory in the design of LOs. In this work, we give an overview of the ISDMELO methodology, which incorporates principles from different learning schools and give an example of its application. The proposed methodology is currently being experimented by K-12 teachers from public schools as well as instructional designers from private companies in Brazil.

[MCC21/04]
BRANDÃO, A.A.F.; ALENCAR, P.; LUCENA, C.J.P. Extending object-Z for multi-agent systems specification.  15 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Agent-orientation has gained increased importance in recent years with the emergence and growth of the World Wide Web, both as an area of study in itself, and as a component of other disciplines such as software engineering. As a result, this has led to an increased amount of research developing new informal and formal software engineering techniques to support agent-oriented system specification, design, validation and development. In this paper, we present a formal  notation called AgentZ that combines the model concepts and structure proposed by TAO (Taming Agents Objects), a conceptual framework that provides conceptual foundations for agents and objects, with the well known Z and Object-Z formal representation languages. AgentZ was built to provide a formal notation that allows the verification of design models, a key issue within the emerging agent-oriented Software Engineering research and, as a result, it can help to improve the quality of MAS.

[MCC22/04]
VIEIRA, C.E.C.; RIBEIRO, C.C.; SOUZA, R.C. Geradores de números aleatórios.  12 p. Port. E-mail: celso@inf.puc-rio.br

Abstract: This  works presents a short introduction to random numbers generators which are based upon specific mathematical algorithms, sequential and deterministic. These algorithms are crucial for a whole range of applications. First, we discuss the mathematical definition of random number generators and the common techniques for producing  the random sequence. Next, the desirable properties of good generators are discussed. Final remarks are made in the last Section.

[MCC23/04]
VIEIRA, C.E.C.; SEIBEL, L.F.B. Técnicas de paralelismo aplicadas a execução de fluxos de programas de bioinformática.  39 p. Port. E-mail: bib-di@inf.puc-rio.br

Abstract: One of the most important task of the genome projects is called process of annotation, which consists in the analysis and interpretation of experimental of data in order to derive biological knowledge from the data. Many systems were created to aid the researchers in the annotation process, such as BioNotes. This tool is currently used to annotate the genome of bacteria Gluconacetobacter Diazotrophicus and supports three types of annotation: imported, originating from external data source; automatics, generated by execution of biological analysis programs, and manual, created by the biologists. This paper refers to the automatic annotations, that is essential for the researchers but which spend a lot of time to  be available in the BioNotes system. This time can be reduced if parallel computing methods were used in the execution of the workflow which generates automatic annotations. The objective of this papers is to discuss these parallel computing methods and to demonstrate the viability and importance of the parallelism methods in the bioinformatics area.

[MCC24/04]
RUSSO, E.E.R.; FERNANDO, T.; RAPOSO, A.B.; GATTASS, M. Workspaces' challenges for the oil & gas exploration and production industry.  15 p. Eng. E-mail: mgattass@tecgraf.puc-rio.br

Abstract: The objective of this paper is to prospect and analyse the main challenges faced when defining and building virtual reality workspaces for Exploration & Production oil and gas activities.  Initially, we classify and describe the different challenges. Then, we present the main activities in the oil & gas industry that use this technology.

[MCC25/04]
SILVA, L.F.; LEITE, J.C.S.P.; BREITMAN, K.K. C&L: uma ferramenta de apoio a engenharia de requisitos.  24 p. Port. E-mail: julio@inf.puc-rio.br

Abstract: This paper presents an experimental tool to support requirements engineering activities. This tool, called C&L, is based on two techniques to model software requirements, scenarios and the extend lexicon of the language. C&L supports a cooperative process to edit scenarios and the lexicon. It aims to maintain the traceability between requirements and code. C&L is one of the Requirements Engineering Group's research projects at PUC-Rio.

[MCC26/04]
PONTES, A.M.; LEITÃO, C.F.; SOUZA, C.S.; BARBOSA, S.D.J.; QUENTAL, V.S.T.D.B. Estudo do impacto do design e das formas de uso sobre a recuperação de informações em foruns de discussão online.  13 p. Port. E-mail: clarisse@inf.puc-rio.br

Abstract: This paper presents the results of a case of study in which we verified that consistent information retrieval on discussion forum systems is strongly influenced by certain design decisions (made by the designer), as well as by the various ways how users use the tools. We verified that design features included specifically in view of information retrieval can be declined by some users, which may certainly influence the desired retrieval  consistency in a negative way. The foundation of our study relies on Semiotic Engineering concepts, as well as methods and concepts from Linguistic, like as Conversation Analysis.

[MCC27/04]
PAOLIELLO, C.M.; FURTADO, A.L. Sistemas de informação para comércio eletrônico.  45 p. Port. E-mail: furtado@inf.puc-rio.br

Abstract: The purpose of the present work is to survey the main features of information systems oriented to the area of e-commerce. The main business requirements are analyzed, and also how e-commerce technologies can contribute to successful comercial sites. Processes related to product sales are examined from a technological viewpoint. In addition, technologies used for the infra-structure of an e-commerce site are reviewed (servers, network architecture, communication links, databases, security, etc). The final part of the work gives a case study, concerning sites for selling books via Internet (Amazon.com), highlighting the experience gained in various business areas, the main problems encountered and the solutions adopted in practice.

[MCC28/04]
BARUQUE, C.B.; MELO, R.N. Developing digital libraries using data warehousing and data mining techniques.  11 p. Eng. E-mail: rubens@inf.puc-rio.br

Abstract: We propose a manner to the development of Digital Libraries (DL), using Data Warehousing (DWing) and Data Mining (Dmining) Techniques. This DL will be a component of an e-learning environment and will assist the students in a specified course. This will help them in their studies and researches, once the Web will be already filtered by the data mining techniques on the subject they need to study. We propose components of the data warehousing architecture on which data mining techniques can be applied. The Data Warehouse will be like a Central Library and the Data Marts (portions of the Data Warehouse separated by a certain criteria - the course, for example) like Departament Libraries. The retrieval of the DL documents by students will be made through OLAP (On-Line Analytical Processing) techniques based on the DL catalog, which is modeled multidimensionally and based on the Dublin Core metadata elements. A discussion of the DL automatic refreshing based on information collected on the students' interactions is also presented.

[MCC29/04]
CHOREN, R.; GARCIA, A.; LUCENA, C.J.P. Software Engineering for Large-scale Multi-agent Systems - SELMAS 2004: workshop report.  18 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: This paper is intended to sum up the results of the Third International Workshop on Software Engineering for Large-Scale Multi-Agent Systems (SELMAS 2004) held in Edinburgh, Scotland, May 24-25, 2004, as part of the International Conference on Software Engineering (ICSE 2004). 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 24 submissions, of which 14 papers were accepted for presentation. A set of selected workshop and invited papers are to appear in a Lecture Notes in Computer Science (LNCS, Springer) volume. The workshop consisted of an opening presentation, two keynote talks, four technical sessions of paper presentations, and two panels. During the workshop we informally reviewed ongoing and previous work and debated a number of important issues. The SELMAS 2004 website can be found at <http://www.teccomm.les.inf.puc-rio.br/memas2004>. We begin by presenting an overview of our goals and the workshop structure, and then focus on the workshop technical program.

[MCC30/04]
LEAL, M.A.; IERUSALIMSCHY, R. The weak-reference interface. 15 p. Eng. E-mail: roberto@inf.puc-rio.br

Abstract: Weak references are a powerful programming language abstraction. Among other uses, they can be employed as a finalization with the advantage of circunventing several difficulties associated with regular finalizers.  Nevertheless, weak references are still modestly known by programmers in general, and have received erratic support by garbage-collected language implementations.  In the paper, we examine weak references' most common and relevant applications, present a survey on how the abstraction is supported by actual programming languages, and discuss weak reference semantics and implementation alternatives.

[MCC31/04]
ALBARELLO, A.B.; LUCENA, C.J.P. fGrin: um framework baseado em sistemas multiagentes para formação de grupos de interesse a partir de uma base semântica. 9 p. Port. E-mail: lucena@inf.puc-rio.br 

Abstract: The current growing use of technology exercises great influence on the behavior of the society. That is partially due to the application of new organizational strategies which assist people and institutions on the development of their activities. A tendency which can be currently observable is associated with the benefits that occur when people with the same interest are joined together for the accomplishment of a common task. This article presents fGrin, an application instantiated from a framework based as multi-agents systems whose purpose is forming groups of interest based on a semantic database.

[MCC32/04]
SILVA, V.T. ; CORTÉS, M.I. ; LUCENA, C.J.P An object-oriented framework for implementing agent societies. 37 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: The goal of multi-agent system architectures and frameworks is to provide reusable agent-oriented classes that can be extended and customized in order to implement domain specific systems. This paper proposes an object-oriented framework for implementing agent societies. Agent societies are multi-agent systems in which it is required or important to represent agent playing roles in organizations. By using the framework, it is possible to implement several agents; each playing different roles in different organizations. The framework contemplates agents, roles, organizations and environments as first-order entities. For each entity, a detailed lifecycle is prescribed by describing the execution states and the events that cause the (allowed) transition of the entity from one state to another. Based on graphic representations of the lifecycle models, the computational models of each entity could be explored. The computational models define the behavior of the entities associated with each state described in the lifecycle models. As a consequence, both the structural and the dynamic aspects of the ASF (Agents Society Framework) framework are presented in the paper.

[MCC33/04]
BARBOSA, C.M.A. ; LEITÃO, C.F. ; de SOUZA, C.S. ; PREECE, J. An online community framework-based analysis of an existing online community. 35 p. Eng. E-mail: clarisse@inf.puc-rio.br

Abstract: An important requirement for developing successful online communities is to understand the impacts of software design on their evolution. This requirement motivated the development of the Online Community Framework (OCF), a theoretically-based analytic tool for helping designers understand and produce computer technology to support social activity online. This paper reports the first extensive use of OCF to analyse in detail a long-standing and successful Brazilian online health support community, the Multiple Sclerosis Sufferers Society. The paper discusses OCF's performance as an epistemic tool and proposes a number of issues for future research.

[MCC34/04]
RUBINSZTEJN, H. ; ENDLER, M. ; SACRAMENTO, V. ; GONÇALVES, K. ; NASCIMENTO, F. Support for contex-aware collaboration. 11 p. Eng. E-mail: endler@inf.puc-rio.br

Abstract:This paper describes a middleware architecture with its location inference service (LIS), and an application for contex-aware mobile collaboration which is based on this architecture. The architecture, named Mobile Collaboration Architecture - MoCA comprises client server APIs, a set of core services for registering applications, monitoring and inferring the execution context of mobile devices, in particular their location. This architecture is suited for the development of new kinds of collaborative applications in which the context information (connectivity, location) plays a central role in defining both the group of collaborators, and the communication mode.

[MCC35/04]
LIFSCHITZ, S. ; MILANÉS, A.Y.; SALLES, M.A.V. Estado da arte em auto-sintonia de SGBD relacionais. 52 p. Port. E-mail: sergio@inf.puc-rio.br

Abstract: Database tuning is the activity of adjusting parameters, configurations and data structures of a database system to the needs of a given workload. In general, most performance adjustments are done on DBMSs by specialized DBAs. This situation motivates the development of self-tuning database systems, that is, systems that adjust themselves without human intervention in order to obtain more performance to their applications. This report presents a study of database systems self-tuning. We classify the existing proposals in two major research fronts: local self-tuning and global self-tuning. The goal of local self-tuning work is to enhance system performance taking into consideration a specific aspect of the system, such as physical design or memory use. Global self-tuning work, on the other hand, tries to consider the trade-offs involved in tuning different aspects of the system. This report also presents an overview of commercial systems that bring self-tuning features.

[MCC36/04]
SARDINHA, J.A.R.P. ; MILIDIÚ, R.L. ; LUCENA, C.J.P. ; PARANHOS, P.M. A methodology for building trading agents in electronic markets. 11 p. Eng. E-mail: milidiu@inf.puc-rio.br

Abstract: In this paper we present a methodology that guides the development of a multi-agent system for trading in electronic markets. Our approach uses a strategy of decomposing a complex trading problem into sub-problems, and defines agent roles that tackle these sub-problems. We also present an incremental development process for building asynchronous and distributed agents, which enable effortlessly the combination of intelligent agent strategies. This creates a highly adaptable system for unknown situations that is easy to scale up. We use the Trading Agent Competition (TAC) environment as a case study to illustrate the suitability of our approach.

[MCC37/04]
SARDINHA, J.A.R.P. ; MILIDIÚ, R.L. ; LUCENA, C.J.P. ; PARANHOS, P.M. ; CUNHA, P.M. An agent based architecture for highly competitive electronic markets. 13 p. Eng. E-mail: milidiu@inf.puc-rio.br

Abstract: In this paper we present a multi-agent architecture for trading in electronic markets with asynchronous and related auctions. This architecture enables the development of a multi-agent system for a highly competitive environment, where all participants are competing for a limited number of goods. We define intelligent agent roles that tackle sub problems of trading, and present a solution for combining these results in a distributed environment. The agents' typical tasks are price prediction, bid planning, good allocations, negotiation, among others. We use the Trading Agent Competition (TAC) environment as a case study to illustrate the suitability of our approach. We also present LearnAgents, a multi-agent system based on our architecture that achieved the third place in the 2004 TAC Classic competition.

[MCC38/04]
LEITE, M. ; LUCENA, C.J.P. ; RODRIGUES, L.F. ; MAGALHÃES, J. Applying a circuit-based component model to a distributed OO application. 18 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: In this paper, we motivate and propose a novel component- oriented model, called Object Circuits (OCs), by applying it to a typical Web application: Webclipper. The former aims to take component-orientation to another level, by incorporating ideas from a field that is component-oriented by excellence: electronic circuits. The latter is an application for clipping news, i.e. the process of gathering, formatting and distributing content matching the interest of a group of users. Webclipper has been originally modeled and developed using traditional OO design. It is a real world, distributed OO application with enough complexity and generality to be useful for evaluating our approach. Furthermore, we have chosen an application that is not intuitively associable to OCs to illustrate its true generality. We have ported the application to our paradigm and the results are presented in the paper.

[MCC39/04]
DE MARIA, B.A.; SILVA, V.T.; LUCENA, C.J.P. Usando MDA no desenvolvimento de sistemas multi-agentes. 15 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: A great number of methodologies, frameworks and languages are being proposed to support the development of multi-agents systems (MAS). In this paper, we propose the use of MDA in the development of this kind of systems. MDA specifies a structured software development process in modeling stages. In PIM stage, where platform independent models are specified, we propose the use of MAS-ML modeling language for MAS. In PSM stage, where platform specific models are specified, we propose the use of UML modeling language. The MAS-ML models defined on PIM stage are transformed in UML models at PSM stage, based on a framework to implement MAS using object orientation. In the last development stage, the application code is generated from UML models. In this work, we will detail PIM and PSM stages on the development process of MAS and the transformations to generate source code.

[MCC40/04]
MACÊDO, J.A.F.; PICOUET, P. A performance analysis framework for database management systems. 21 p. Eng. E-mail: bib-di@inf.puc-rio.br

Abstract: Performance evaluation of DBMS is a major issue since it is generally difficult to model experimental and performance analysis results. In this paper, we propose an application framework that provides a model, a methodology and a common platform to implement database evaluation analysis tools. Inspired on a conceptual UML model, this application framework provides a much more detailed model that allows capturing the complex structure of DBMS modern software. We use a recent work about the implementation of a new data page layout to illustrate the instantiation of our framework.

[MCC41/04]
KULESZA, U.; GARCIA, A.F.; LUCENA, C.J.P.; STAA, A.v. Integrating generative and aspect-oriented technologies. 15 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Over the last years, two new software engineering approaches have been proposed: generative programming and aspect-oriented software development. Generative programming addresses the study and definition of methods and tools that enable the automatic production of system families from a high-level specification. Aspect-oriented software development has been proposed as a technique for improving separation of concerns in the construction of OO software and suporting improved reusability and ease of evolution. The use of aspect-oriented techniques in a definition of a generative approach can bring benefits to the modeling and generation of crosscutting features since early development stages. This paper presents our experience in the definition of an aspect-oriented generative approach. The proposed approach explores the multi-agent systems domain to enable the code generation of agent architectures.

[MCC42/04]
FURTADO, A.L. Uma introdução ao uso de programação em lógica para modelagem conceitual. 15 p. Port. E-mail: furtado@inf.puc-rio.br

Abstract: Information systems with a database component should be modelled at three levels, at least, which we denominate static, dynamic and behavioural. The static level refers to the classes of facts to be represented in the database. The dynamic level deals with the repertoire of operations, which are provided in order to achieve state transitions, by adding and/or removing facts. Taken together, these first two levels cover the object-oriented aspects of the information system being specified. The behavioural level indicates how the various agents are expected to use the system, so as to reach their goals, through the execution of authorized operations. This third level extends the especification to cover agent-oriented aspects. This work describes a method, supported by a simple tool written in Prolog, for the three-level specification of information systems. The specifications are executable, which allows the designers to run experiments before implementation. The tool includes a version of the WARPLAN plan-generation algorithm.

[MCC43/04]
GARCIA, A.F.; FIGUEIREDO, E.M.; LUCENA, C.J.P.; SANT'ANNA, C.N.; KULESZA, U.; STAA, A.v. Aspectizing design patterns: rewards and pitfalls. 21 p. Eng. Email: arndt@inf.puc-rio.br

Abstract: Design patterns offer flexible solutions to common problems in software development. Recent studies have shown that several design patterns involve crosscutting concerns. Unfortunately, object- oriented (OO) abstractions are often not able to modularize those crosscutting concerns, which in turn decrease the system reusability and maintainability. Hence, it is important verifying whether aspect-oriented approaches support improved modularization of crosscutting concerns relative to design patterns. Ideally, quantitative studies should be performed to compare object-oriented and aspect-oriented implementations of classical patterns with respect to important software engineering attributes for reusability and maintainability, such as coupling, cohesion. This paper presents a quantitative study that compares aspect-based and OO solutions for the 23 Gang-of-Four patterns. We have used stringent software engineering attributes as the assessment criteria. We have found that most aspect-oriented solutions improve separation of pattern-related concerns, although some aspect-oriented implementations of specific patterns result in higher coupling or lower cohesion.

[MCC44/04]
SACRAMENTO, V. ; ENDLER, M. ; RUBINSZTEJN, H.K. ; LIMA, L. ; GONCALVES, K. ; NASCIMENTO, F. ; BUENO, G.A. MoCA: a middleware for developing collaborative applications for mobile users. 7 p. Eng. E-mail: endler@inf.puc-rio.br 

Abstract: This article presents a middleware architecture for the development and deployment of context-aware collaborative applications for mobile users. The architecture, named Mobile Collaboration Architecture - MoCA comprises client and server APIs, a set of core services for registering applications, monitoring and inferring the execution context of mobile devices, and an object-oriented framework for instantiating and customizing server proxies according to the specific adaptation and context-processing requirements of the applications. MoCA facilitates the development of distributed programs which require access to individual and group context in order to adapt its behavior. The design focused on simplicity, extensibility, scalability, protocol heterogeneity and application customization.

[MCC45/04]
ASSIS, P.S.; SCHWABE, D.; BARBOSA, S.D.J. Meta-modelos para aplicações de hipermídia adaptativa e meta-adaptação.  31 p. Port. E-mail: dschwabe@inf.puc-rio.br

Abstract: The emergence of meta-adaptative systems seems to be a natural evolution process in adaptive systems. Meta-adaptive systems are able to vary the adaptation technique based on various factors. This work analyzes the main aspects related to adaptivity by proposing a reference meta-model for AH Systems. This model is a first step towards the development of a general meta-model intended to be the basis for a meta-adaptive system.

[MCC46/04]
CONDACK, J.F.S.; SCHWABE, D. AgileOOHDM.  78 p. Eng. E-mail: dschwabe@inf.puc-rio.br

Abstract: This technical report describes an initial proposal of AgileOOHDM. It is an adaptation of a traditional software engineering based method, OOHDM, considering the Agile approach, more specifically its reflexes in Extreme Programming. This initial proposal was born from a study involving conceptual models of development process, commented in this work too. It is also intended to contribute with the debate between lightweight versus heavyweight methods as the proposal matures. 

[MCC47/04]
VASCONCELOS, D.R.; HAEUSLER, H.E.; POGGI, M.; BENEVIDES, M.F. Reasoning about games via temporal logic:a model checking approach. 13 p. Eng. E-mail: hermann@inf.puc-rio.br

Abstract: This article shows how to use a subset of ¯rst-order CTL, namely Game Analysis Logic (GAL), in order to reason about games. A model checking algorithm for GAL is presented. Standard games and solution concepts of Game Theory are described in this context. Taking into account the strong relationship between games and Multi-Agent systems(MAS),the approach described here seems to be completely suitable for MAS formal analysis. Strategic and Coalition games are modelled and formally analyzed as case studies in order to demonstrate this approach.

[MCC48/04]
SILVA, V.T.; NOYA, R.C.; LUCENA, C.J.P. Using the UML 2.0 activity diagram to model agent plans and actions. 10 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: The behavior of an agent is defined through the specification of plans and actions. Agents have a set of plans that are selected to be executed according to their goals (and other mental state information). In this paper, we propose the use of UML 2.0 activity diagrams to model agent plans and actions. We consider a plan to be an activity. Both plans and activities are composed of actions and define the execution sequence. By using some features available in the UML 2.0 activity diagrams and defining some new ones, we demonstrate how these diagrams can be applied to model agent plans and actions.

[MCC49/04]
MILIDIÚ, R.L.; MELLO, C.G. Ramdomized Huffman codes. 9 p. Eng. E-mail: milidiu@inf.puc-rio.br

Abstract: Huffman codes have widespread use in information retrieval systems. Besides its compressing power, it also enables the implementation of both indexing and searching schema in the compressed file. In this work, we propose a randomized variant of the Huffman data compression algorithm. The algorithm results in a small loss in coding, decoding and compression performances. It uses homophonic substitution and canonical Huffman codes.

[MCC50/04]
MILIDIÚ, R.L.; MELLO, C.G. Adding security to prefix codes. 18 p. Eng. E-mail: milidiu@inf.puc-rio.br

Abstract: Data compression and ciphering are essential features when digital data is stored or transmitted over insecure channels. Prefix codes are widely used to obtain high performance data compression algorithms. Given any prefix code for the symbols of a plaintext, we propose to add security using a multiple substitution function and a key. We show that breaking the code when we are given the ciphertext, dictionary, frequencies and code lengths is a NP-Complete problem.

[MCC51/04]
COSTA, V.G.; LABER, E.S.; HAEUSLER, E.H. Some remarks on the size of boolean functions. 7 p. Eng. E-mail: laber@inf.puc-rio.br

Abstract: This report discusses some aspects regarding the size of boolean functions, their minterm and maxterm concepts and some graph properties associated to boolean functions and circuits.