Monografias em Ciência da Computação
1993
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,
Pontifcia 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
1993
[MCC01/93]
MARQUES, M.P.; LANZELOTTE, R.S.G. Banco de dados e hipermídia:
construindo um meta-modelo para o projeto Portinari. 105 p. Port.
Abstract: Data bases constitutes a natural repository for storing
information dealt with by hypermedia applications. Many works have
investigated how to design the database model to support an hypermedia
application. Another viewpoint consists in starting from an existing
database and designing hypermedia front-ends to it. In this paper, we
propose an approach to design hypermedia applications using the data stored in an existing database. The approach is based on a meta-model,
that integrates the two environments through their respective models,
thus enabling the hypermodel evolve with the database. We apply the
the proposed approach to the PORTINARI Project, concerning the most
famous Brazilian painter. The approach is generic and can be used to
build hypermedia interfaces to any existing database.
[MCC02/93]
POTENGY, A.B.; LUCENA, C.J.; COWAN, D.D. A programming approach for
parallel rendering applications. 30 p. Eng. E-mail:
lucena@inf.puc-rio.br
Abstract: Solutions to many problems in scientific computing can be
expressed as parallel computations that can be implemented on multi-processor systems or networks of powerful workstations. Design and
implementation of these parallel programs usually is a complex effort
which requires cooperation among the participating tasks in order to
ensure correct operation and consistency. This paper introduces the the ADV/ROI design approach that combines
Abstract Data Views (ADVs)
and Remote Object Invocation (ROI) and applies this approach to the
implementation of parallel programs using the principles of object-oriented design. The ADV/ROI approach is applied in two steps. First, a "working" sequential version of a program is implemented and then
this program is converted to parallel version using a well-defined procedure involving multiple inheritance. We also demonstrate that
consistency of the views of the computation are maintained as the
program evolves from its sequential to parallel version. The ADV/ROI aproach is then demonstrated by showing the design and implementation
of a parallel volumetric ray tracer.
[MCC03/93]
PORTO, S.C.S.; RIBEIRO, C.C. A tabu-search approach to task scheduling
on heterogeneous processors under precedence constraints. 26 p. Eng.
E-mail: celso@inf.puc-rio.br
Abstract: Parallel programs may be represented as a set of
interrelated sequential tasks. When multiprocessors are used to
execute such programs, the parallel portion of the application can be speeded up by an appropriate allocation of processors to the task of
the application. Given a parallel application defined by a task
precedence graph, the goal of task scheduling (or processor
assignment) is thus the minimization of the makespan of the
application. In a heterogeneous multiprocessor system, task
scheduling consists in determining which tasks will be assigned to
each processor, as well as the execution order of the task assigned to
each processor. In this work, we apply the tabu search metaheuristic
to the solution of the task scheduling problem on a heterogeneous
multiprocessor environment under precedence constraints. The topology
of the Mean Value Analysis solution package for product form queueing networks is used as a framework for performance evaluation. We show
that tabu search obtains much better results, i.e. shorter completion
times, improving from 20 to 30% the makespan obtained by most
appropriate algorithm previously published in the literature.
[MCC04/93]
HAEBERER, A.M.; BAUM, G.A.; SCHMIDT, G. Dealing with non-constructive
specifications involving quantifiers. 37 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: The work presented here has its focus on the formal
construction of programs out of non-constructive specifications
involving quantifiers. This is accomplished by means of an extended
abstract algebra of relations whose expressive power is shown to
encompass that of first-order logic. Our extension is the first
finitary one that solves the classic issue of lack of expressiveness
of abstract relational algebras first stated by Tarski and later
formally treated by Maddux, Nemeti, etc. First we compare our
extension with classic approaches to expressiveness and our axiomatization with modern approaches to products. Then, we introduce
some non-fundamental operations. One of them, the relational
implication, is shown to have heavy heuristic significance both in
the statement of Galois connections for expressing relational
counterparts for universally quantified sentences and for dealing
with them. In the last sections we present two smooth program
derivations based on the theoretical framework introduced previously.
[MCC05/93]
DURAN, J.E.; BAUM, G.A. Construccion formal de programas a partir de
especificaciones en un calculo de relaciones binarias extendido. 94 p. Spa. E-mail: bib-di@inf.puc-rio.br
Abstract: We study the formal program construction from specifications
in a calculus that extends Tarski's calculus of binary relations. This
paper relies on a threefold base, i.e., the language of Structured
Relational Algebras, some properties of these algebras and the Calculus
of Binary Relations of Tarski. Some new constructions for specifying problems and program derivations are defined. By extending Tarski's
calculus with an aditional set of axioms, here presented, we obtain an
abstract representable algebra. After doing a number of derivations,we find new properties
valid within the Structured Algebras. The most
relevant of them are choosed and proved using the axioms. Finally, we undertake the problem of proving properties for relations. The proof
of invariants is analized and a proof strategy is given.
[MCC06/93]
CARVALHO, S.E.R. The object and event oriented language TOOL. 18 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: TOOL is a programming system designed to simplify the task
of building application programs running on graphical user interface
plataforms. The current version runs above Microsoft Windows, version
3.1. This report describes the programming language component of
the system. This is an object and event oriented language, designed
to be easily understood by conventional language programmers. In this
language both synchronous and the asynchronous behavior of objects
are declared in classes.
[MCC07/93]
CARVALHO, S.E.R. On the reuse of applications as components. 17 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Object orientation seems to provide a welcoming framework
for software reuse. This software is typically in the form of
individual classes, and the reuse is typically obtained through
composition and inheritance. In this paper we address the reuse of
stand-alone applications, without modifications, as components in
other applications. We do this in the TOOL programming system, taking
advantage of its handling of asynchronous messages at the class level.
[MCC08/93]
CARVALHO, S.E.R. Sobre o comportamento de objetos. 14 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: The procedural behavior, the only one usually available in
object oriented languages, is necessary in the construction of
programs. However, other well-known behavioral semantics in the
conventional programming world have no counterparts in object
orientation. In this paper we propose the inclusion, in classes, of
operations to handle asynchronous messages, exceptions, and the
production of sequences of values for loop control objects, offering
examples of their uses.
[MCC09/93]
JAUMARD, B.; CARNEIRO, C.C. Implication graph and quadratic 0-1
optimization. 17 p. Eng. E-mail: celso@nf.puc-rio.br
Abstract: A new approach for optimization of a quadratic function in
0-1 variables, based on the solution of a sequence of nested set
covering problems, is presented. Each constraint of the set covering
problems is associated with a circuit in the implication graph derived
from the span of the quadratic function.
[MCC10/93]
CARNEIRO, L.M.F.; COWAN, D.D.; LUCENA, C.J.P. The semantics of nesting
object-oriented design. 20 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: It has been observed that design of complex objects such as
software requires both decomposition by form (atomic objects) and
decomposition by function (nesting) in order to reduce the design to a
set of manageable components. However, the object-oriented design
paradigm mostly supports decomposition by form. This paper uses a
simple example to motivate the need for nesting (decomposition by
function) and illustrates how nesting might be incorporated into a
design language. We then demonstrate how the introduction of nesting
into software specification and design significantly increases
reusability. ADV charts, a new visual formalism, and VDM are used to
provide a semantics for nesting.
[MCC11/93]
GUEDES, L.C.; STAA, A.v. Um processo de re-engenharia econômico e
eficaz. 17 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: In this paper we propose a re-engineering process. Using
this process, a source program is reestructured in order to reduce
maintenance costs and, simultaneously, increase its quality. Several
computer aided activities are performed during this process. Roughly
speaking, this process uses syntax directed reverse engineering to
transport the original source code to a CASE repository. It is a basic
requirement that the CASE tool be capable of generating (linearize)
source code from the content of the repository. Once disponible in
the repository, the CASE tool is used to re-engineer the program. The
process may be adapted to several different source languages, by simply
defining the grammar and lexical analysers of these languages.
[MCC12/93]
DUARTE, C.H.C.; HAEUSLER, E.H. Técnicas formais e informais: um
estudo sobre integração usando "statecharts". 17 p. Port. E-mail:
hermann@inf.puc-rio.br
Abstract: Large effort has been done to find techniques which turn
software development tractable. Statechart is a visual formalism that
has been widely used, intending to eliminate the problems in this
activity. This paper propose a different approach to solve part of
these problems, by integrating this formal technique to other informal
one. Either, formal rationale about the integration is presented,
showing that an integration method can be established, adopting the
same semantic model to assign meaning to the specification languages
used.
[MCC13/93]
LEITE, J.C.S.P. Eliciting requirements using a natural language based
approach: the case of the meeting scheduler problem. 15 p. Eng.
E-mail: julio@inf.puc-rio.br
Abstract: Requirements elicitation is a process in which the software
engineer works toward understanding and discovering what is expected
from a planned software system. Although it is common belief that it
is a hard task, several researchers are attacking the problem using
different frameworks. One of these frameworks is based on the use of
natural language. One strong reason for natural language based
framework is to avoid the introduction of artificial languages at the
beggining of the software development process. We believe that,
although using this framework, it is possible to achieve more
precision. Our group has been investigating one approach, called the Language Extended Lexicon (LEL), that fits in such framework. We have
used the LEL mainly for eliciting application vocabulary directly
from actors in an application universe of discourse. In this study
we report in a variation of our approach. We show how the LEL can help
the elicitation of requirements when one is departing from a written
document. The approach is supported by a hypertext system specially
designed for the LEL.
[MCC14/93]
SANCHEZ, M.L.D.; MAFFEO, B. Ferramentas e técnicas para a modelagem da essência de sistemas de tempo-real para controle e monitoramento de
processos. 25 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This work presents a structure for the conceptual modelling
of the real-time features in process controling systems. It uses tools
and techniques of the Structured Methods area and illustrates the
modelling of the essence of a system for controlling and monitoring,
including exception handling (faults in the external environment), a litography by electron beam process.
[MCC15/93]
GARCIA, A.C.B. Aquisição e recuperação de intensionalidade através de
documentos ativos. 12 p. Port. E-mail: bicharra@inf.puc-rio.br
Abstract: A new approach to design documentation is presented for
increasing the quality of documents without increasing the designers overhead in creating it. The central idea is to create an initial
design model able to generate and explain standard design decisions.
Instead of recording their decisions, designers adjust the initial
design model. The result is no longer a static record of the design,
but an active document containing a design model able to generate
explanations for a design. We have implemented a software prototype
for the active documents approach in the domain of preliminary design
of Heating, Ventilation and Air Conditioning Systems (HVAC). The
prototype test results indicate that the approach is feasible. The
results also indicate that active documents can be used beyound
documentation as a tool for studying design process.
[MCC16/93]
SOARES, L.F.G.; CASANOVA, M.A.; RODRIGUEZ, N.L.R. An open hypermedia system with
nested composte nodes and version control [Title in Portuguese: Um modelo conceitual hipermídia com
nós de composição e controle de versões] 20 p. Eng.
E-mail: lfgs@inf.puc-rio.br
Abstract: This paper describes a model for hypermedia documents which
includes facilities for structured organization of nodes and for
version control. This model is currently being used as a basis in
the implementation of a development tool for local and distributed
hypermedia applications. The layered architecture of this tool grants
the user access to distinct levels of abstaction; it also allows the
system to maintain compatibility with the MHEG proposal for hypermedia
object interchange.
[MCC17/93]
MARTINS, I.H. Uma proposta para tratamento de exceções em uma
linguagem orientada a objeto. 29 p. Port. E-mail: isa@inf.puc-rio.br
Abstract: This article discusses a proposal and specification for
Exception Handling (EH) in object oriented languages. The idea is to
adapt conventional mechanisms of EH to the basic principles of object
orientation. The proposal has two main goals. One of them is to
respect the philosophy of classes and methods so that the EH resource
can be easily absorbed by the user. Another goal is to provide
flexibility in what refers to the scope of the handler (generic or
specific), to the level of coupling between handler and code
(instructions or methods), and to the moment of definition of the
handler (in modeling time of the object or in programming time).
[MCC18/93]
CARVALHO, S.E.R. Asynchronous behavior in the TOOL programming system.
32 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: It is expected that a large portion of software systems to
be constructed in this decade will involve object orientation, message
passing and graphical user interfaces. In this paper we present an
object and event driven programming system, TOOL, which takes full
advantage of object orientation, by considering the handling of asynchronous messages as part of object bahavior. In this way
low-level and error prone concerns with message queues and centralized
handling routines are eliminated. Moreover, we can achieve full
decoupling between interface and implementation in a GUI application,
and reuse stand-alone applications as components in other applications.
[MCC19/93]
LEITE, J.C.S.P. Working results in re-engineering. 16 p. Eng. E-mail:
julio@inf.puc-rio.br
Abstract: We view software re-engineering as a new approach to software
maintenance. Instead of performing maintenance at the source code of
systems, we work on high level abstractions. From these abstractions
we proceed in a forward manner reusing the available implementations,
when it is the case. As such, we view re-engineering as centered on
design recovery. We have been working on methods for re-engineering
and applying them to real cases. Our studies are centered on the idea
of using JSD as a way of casting the recovered design. We worked with
two small systems and a complex one. Our objective here is to highlight
our approach, report on what has been done and point out what was
learned.
[MCC20/93]
GARCIA, A.C.B.; STEFIK, M.J.; HOWARD,H.C. Supporting design
collaboration through active documents. 19 p. Eng. E-mail:
bicharra@inf.puc-rio.br
Abstract: Design is a cooperative activity that requires the
participants to negotiate over design specification. Negotiation
requires understanding of the decisions made by each participant.
Static design documents unsuccessfully play the role of communicating
rationale among design participants. In this paper, we present a new
approach to documentation - active design documents (ADD). Active
documents allow designers to communicate their design intent to other
design participants, supporting negotiation on design requirements and
cooperation during design. We describe the approach and present an
implemented architecture for building active documents. We tested the architecture for the realistic domain of preliminary design of Heating,
Ventilation and Air Conditioning Systems.
[MCC21/93]
HERTZ, A.; JAUMARD, B.; RIBEIRO, C.C.; FORMOSINHO FILHO, W.P. A multi-criteria tabu search approach to cell formation problems in group
technology with multiple objectives. 23 p. Eng. E-mail:
celso@inf.puc-rio.br
Abstract: Group technology techniques are now widely used in many
manufacturing systems. Several algorithms have been proposed for the
optimal design of efficient manufacturing cells. The cell formation
problem must take into account several objectives: the number of
bottleneck operations, the number of bottleneck machines and/or parts,
the intercell flow, the intracell workload balancing, the
subcontracting costs, the machine duplication costs, and the workload
of the busiest machine or cell, among others. In this paper, we
propose a multi-criteria methodology for solving the cell formation
problem with multiple objectives. This approach is based on the use
of the tabu search heuristic for solving a sequence of single-objective,
multi-constrained subproblems, in which each objective is taken and
optimized in turn, following their order of relative importance. The
subproblems are tackled by a strategic oscillation strategy.
Computational results concerning an application to a bi-criteria
problem are reported for instances with up to 100 machines and 1000
parts.
[MCC22/93]
de SOUZA, C.S.S.; DIAS, M.C.P.; GARCIA, L.S.; BASILIO, M.P. Semântica
lexical em linguagens pseudo-naturais de interface. 18 p. Port.E-mail: clarisse@inf.puc-rio.br
Abstract: This paper proposes an alternative to represent and process
lexical semantic information of utterances in pseudo-natural language,
occurring in dialogues between users and knowledge-based systems. The
proposal is presented within the framework of Project LINX, where the
formulation of users utterance may be supported by menu selection, and
system reasoning is supported by a Natural Deduction Theorem Prover
acting upon a logic knowledge base. The theoretical approach to lexical
semantics, applying to both interpretation and generation of pseudo-natural language utterances is that of Jackendoff's Conceptual
Structures. It offers important computational advantages, which are
discussed in terms of the distribution between linguistic processing
and logic proof, of the specificity of the notion of semantics in the
LINX environment, and the types of methods that can be derived for the
construction of both the knowledge base and the interface vocabulary.
[MCC23/93]
de SOUZA, C.S.; CUNHA, M.O. Animação de imagens fractais e representação
de processos em linguagens visuais. 15 p. Port. E-mail:
clarisse@inf.puc-rio.br
Abstract: The expression Visual Languages has been used in a variety
of senses. In this paper we explore the possibilities of visualy
representing computer processes at the user interface level by means
of animated fractal images. Although the selected images are not
iconic (i.e. they do not directly evoke the meaning of processes they
represent), important abstractions are shown to be systematically
related to perceptual changes in form. We discuss the implications of
such abstractions for Visual Languages, both in terms of human-computer
interactive codes and of declarative representation languages supporting
animation effects.
[MCC24/93]
de SOUZA, C.S. General help systems for network resource discovery. 12 p.
Eng. E-mail: clarisse@inf.puc-rio.br
Abstract: Wide area computer networks offer users a large volume and
variety of resources that can help them to solve many kinds of daily
problems in their work environment. However, the existence, let alone
the contribution, of such resources is generally ignored by networkers.
This work discusses usability issues as perceived in the INTERNET, and
presents a research project underway, relative to General Help Systems
(GHSs) - an intended means to narrow the distance between users needs
and network resources.
[MCC25/93]
SILVA, M.T.M.P.; FUKS, H. Um esboçoo de cálculo de influência de diálogos na escolha entre propostas de
ação. 40 p. Port. E-mail:
hugo@inf.puc-rio.br
Abstract: This work outlines an influence calculus for argumentative
dialogs for choosing a course of action in computer supported
cooperative work. Each possible action is examined when one of the
parts questions it. This triggers an argumentative dialog. Commitments
to the issued arguments and their backings together with their relative
weights are established as the dialog unfolds. These weights should
describe the influence that each locution has in the evaluation of the
course of action. The aim of such representation is to help the parts
to clarify their points of view and to support the evaluation of the
best course of action.
[MCC26/93]
STAA, A.v. Critérios para a avaliação da coesão. 17 p. Port. E-mail:
arndt@inf.puc-rio.br
Abstract: A set of quality control criteria is presented. These
criteria evaluate the quality factor cohesion. The criteria may be
used whenever representations having several levels of abstraction are
built. The criteria may be used with respect to several representation
languages, not just with respect to structured design. When working
with elements at different levels of abstraction a solution of each
abstract element must be provided. This solution is defined at
a lower level of abstraction. Furthemore, this solution must also
satisty several relations with respect to the abstract element it
intends to solve. The solution must also satisfy several structural
properties. The objective of the quality control criteria is to
provide a means to objectively decide wether a given solution is
good or not.
[MCC27/93]
STAA, A.v. Projeto TOTEM: meta-ambiente de desenvolvimento de software definição do projeto. 36 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: TOTEM's main objective is to contribute to the enhancement
of the current practice of software engineering. In order to achieve
this goal, a software engineering meta-environment will be built.
With this meta-environment specific computer aided software
engineering environment instances can be generated. Each of these
instances provides support to a selected set of development,
maintenance and/or management activities. The collection of instances
supports the cooperative work of development teams. Each instance may
be adapted to the specific needs of the object system to be developed
and to the needs of the people using the set of instances. In adition
to instantiating production environments, the TOTEM meta-environment
will also provide support to experimental research in Software
Engineering. This document defines the requirements of the TOTEM
meta-environment. It defines also the basic architecture of the
meta-environment.
[MCC28/93]
STAA, A.v. Uso de instrumentação para a construção de programas confiáveis. 11 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: In this paper we discuss the implementation of reliable
programs using "almost" reliable components. The implementation
method contributes alsoto the productivity increase when compared
to traditional implementation based on testing and debugging.
The implementation method is based on (i) the use of design and
programming tools aiming at the construction of "almost" correct
programs, (ii) the use of robust and auto-verifiable data structures,
(iii) the inclusion of executable assertions into the programs, (iv)
the use of co-routines to verify the structural correctness of the
data structures during idle cycles.
[MCC29/93]
FRIAS, M.; BAUM, G.; HAEBERER, A.M.; VELOSO, P.A.S. A representation
theorem for fork-algebras. Eng. E-mail: armando@inf.puc-rio.br
Abstract: Not available.
[MCC30/93]
FEIJO, B.; LUCENA, C.J.P.; BENTO, J. A formal approach to design
based on cognition. 17 p. Eng. E-mail: bruno@inf.puc-rio.br
Abstract: Most of the current general design methodologies do not
capture the cognitive nature of design. The present paper proposes
an approach based on an evolving theory of the design process inspired
on a cognitive interpretation of design. This approach provides a
pragmatic guideline for developing and evaluating design methodologies
used in connection with CAD and CASE systems. Furthermore, it seems
that several current design models are interpretations of the proposed
theory.
[MCC31/93]
de SOUZA, C.S. Testing predictions of semiotic engineering in HCI.
10 p. Eng. E-mail: clarisse@inf.puc-rio.br
Abstract: This paper presents an overview of Semiotic Engineering and,
with support of results achieved in a small-scale experiment, proposes
a method for testing predictions derived from semiotically-motivated
interface design principles. Semiotic Engineering is a theoretic
approach we have proposed for the construction of user interface
languages, within a perspective about HCI according to which systems
are themselves complex messages sent from designers to users. The
original semiotic theory from which our approach draws its fundamentals
is Umberto Eco's Theory of Sign Production. The long-range goal of
Semiotic Engineering is to contribute for a theory of design in HCI.
Thus, the fundamental principles we have proposed must be
experimentally tested as a means to evaluate the theory. Preliminary
test methods and results reported here suggest methodological
procedures for experimental studies in Semiotic Engineering.
[MCC32/93]
VELOSO, P.A.S.; HAEBERER, A M. On fork algebras and program
derivation. 35 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Fork algebras provide a useful basis for relational calculi
for program derivation; they arise as extensions of relational
algebras with a new operator, called fork, which anables the
introduction, by definition, of projections. In this paper we examine
some fundamental issues concerning fork algebras, presenting the
proofs of expressiveness and representability and discuss and
illustrate their importance for program derivation.
[MCC33/93]
CARVALHO, S.E.R. Specifying object behavior. 16 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: The procedural behavior, the only one usually available in
object oriented languages, is necessary in the construction of
programs. However, other well-known behavioral semantics in the
conventional programming world have no counterparts in object
orientation. In this paper we propose the inclusion, in classes, of
operations to handle asynchronous messages, exceptions, and the
production of sequences of values for loop control objects, offering
examples of their uses.
[MCC34/93]
CARVALHO, S.E.R. Coroutine semantics in the TOOL programming
environment. 18 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In this paper we discuss two situations, in object oriented
programming, where the semantics of coroutines is useful in the
implementations of loop iterators and of dynamic data structures
navigators. In both of these operations the receiving object is a loop
control object. Iterators are applied to produce, outside of the loop's
environment, the next value for the loop control object; navigators
are applied to indicate, outside of the loop environment, the next
element in a dynamic data structure.