Monografias em Ciência da Computação
1996
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: 18/DECEMBER/2003
[MCC01/96]
MARTINS, S.L.; RIBEIRO, C.C.C.; ROGRIGUEZ, N.D.L. Ferramentas para programação paralela em ambientes de
memória distribuída. 33 p. Port.
E-mail: celso@inf.puc-rio.br
Abstract: This article presents a survey of software tools for parallel
computing on a distributed memory environment. Some concepts of
parallel programming are introduced. Some particular software tools
for distributed memory environments (such as PVM, p4, Express, and
Linda) are described in more details and compared in terms of
performance, support, and ease of use.
[MCC02/96]
CIARLINI, A.E.M.; FURTADO, A.L. Sistema para reconhecimento e geração
de planos. 35 p. Port. E-mail: furtado@inf.puc-rio.br
Abstract: Plan recognition is an important feature of database
cooperative interfaces, since if a system knows what its user intends
to do, it will be in a better position to help him. Planning gains
importance when detected plans violate integrity constraints, because
it can be used both to adapt a detected plan and to generate another
one with the same effects. This paper presents a prototype where plan
recognition and generation are integrated within a database context.
[MCC03/96]
RIBEIRO, C.C.; PORTO, S.C.S. A case study on parallel synchronous
implementations for tabu search based on neighborhood decomposition.
34 p. Eng. E-mail: celso@inf.puc-rio.br
Abstract: We study in this paper different synchronous strategies for
the implementation of tabu search on a parallel machine. The task
scheduling problem on heterogeneous processors under precedence
constraints is used as the framework for the development,
implementation, validation, and performance evaluation of different
parallel strategies. Several strategies are proposed, discussed and
compared: the master-slave model, with two different schemes for
improved load balancing, and the single-program-multiple-data model,
with single-token and multiple-token schemes for message passing. The
IBM SP1 parallel machine running PVM is used for the implementation
and evaluation of these strategies. Computational results are presented
and the behavior of the different strategies is discussed, evaluated,
and compared.
[MCC04/96]
VELOSO, P.A.S. On algebraic structure of fork algebras. 12 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: A fork algebra is a relational algebra enriched with a new
binary operation. They have been introduced because their equational
calculus has applications in program construction. In this paper, we
present some simple results concerning the algebraic structure of
fork algebras and some of their metamathematical consequences. This
paper stems from the crucial, though simple, observation of the
interdefinability of fork and projections in fork algebras. We begin
with some preliminaries about fork algebras and their reducts:
relational and Boolean algebras. We introduce a basic expansion
construction and proceed to examine its connections with homomorphisms
and direct products. We establish the closure of the class of fork
algebras under some of its cases. Then, these results are used to
characterize the simple fork algebras as those with simple
relational-reducts and to decompose fork algebras into subdirect
products of their simple homomorphic images. We use these algebraic
results to reduce equational (and Horn-clause) properties of fork
algebras to their simple components. These simple results enable
one to reduce some properties of fork algebras to corresponding
ones about relational algebras.
[MCC05/96]
VELOSO, P.A.S. On finite and infinite fork algebras. 17 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstact: A fork algebra is a relational enriched with a new binary
operation. They have been introduced because their equational calculus
has applications in program construction, they also have some
interesting connections with algebraic logic. In this paper, which
stems from the crucial, albeit simple, observation of the
interdefinability of fork and projections in fork algebras, we examine
the finite and infinite fork algebras and contrast them with relational
algebras. We show that the finite fork algebras are somewhat
uninteresting, being essentially Boolean algebras, uniquely
characterized by their relational reducts. This contrasts with the
case of infinite fork algebras: we introduce a technique for the
analysis of fork algebras and use some set-theoretical constructions
to exhibit many relational algebras of each infinite cardinality with
many expansions to fork algebras. We begin by providing some background
about fork algebras and their reducts (relation and Boolean algebras):
their abstract versions, some simple results concerning the
algebraic structure of fork algebras, and their concrete, set-based,
versions (fields of sets and proper relational and fork algebras).
We then examine the Boolean fork algebras (where fork is Boolean meet),
show that their relational reducts are Boolean relational algebras,
and characterize them as subalgebras of direct powers of the
two-element fork algebra. These results are then applied to finite
fork algebras: they are described as finite direct powers of the
two-element fork algebra, the only simple finite fork algebras being
those with one or two elements. This shows that a finite fork
algebra is completely determined by its relational reduct (which
we call rigid), in contrast to the infinite fork algebras. We examine
fork-expansions of relational algebras, with the purpose of
comparing relational algebras and fork algebras. Then, we introduce
a technique for the analysis of fork algebras and use some
set-theoretical constructions to exhibit many (simple proper)
relational algebras of each infinite cardinality with many expansions
to fork algebras. Such (infinite) relational algebras demonstrate
quite clearly the diversity of possible fork operations.
[MCC06/96]
COLCHER, S.; SOARES, L.F.G.; CASANOVA, M.A.; SOUZA FILHO, G.L.
Modelo de objetos baseado no CORBA para sistemas hipermídia abertos
com garantias de sincronização. 19 p. Port. e-mail:
lfgs@inf.puc-rio.br
Abstract: This paper outlines some extensions to the object model
underlying the CORBA specification to addrress the requirements of
multimedia and hypermedia systems. These extensions include the
adaptationof many concepts brought from other standards, such as ODP,
ANSA and PREMO,like the concept of active objects. Based on the
synchronization aspectsof hypermedia models, the proposed extensions
include support forspecification of objects with continuous media
attributes, like audio andvideo. and the " Media Pipes ", which
allows for the selection of suitable abstractions to deal with the
access and transfer of continuous media information.
[MCC07/96]
MEDIANO, M.R.; CASANOVA, M.A.; GATTASS, M. Map-tree: um metodo de
acesso para mapas longos. 16 p. Port. e-mail: gattass@inf.puc-rio.br
Abstract: Access metods for map play a fundamental role on geographic
databases performance that typically stores very large maps. It becomes
necessary to treat a map as a long object. This paper introduces a new
data structure, called " map-tree ", designed to store geometrical and
topological information of very large maps. The VR-tree and winged-edge
structures are adopted to index the complete geometry description of
the map and optimize topological operations, respectively. The paper
also defines clustering techniques to optimize the access to secondary
storage.
[MCC08/96]
de SOUZA, C.S. The semiotic engineering of concreteness and abstractness:
from user interface languages to end user programming languages. 25 p.
Eng. E-mail: clarisse@inf.puc-rio.br
Abstract: Most successful User Interface Languages have been designed
observing two important guiding principles: task specificity and
direct manipulation of graphic objects. Programming Languages, in
their turn, have often been pursuing such goals as general
purposeness and efficient symbolic manipulation of linguistic
objects. When it comes to End User Programming Languages, features
that are apparently in conflict with each other must be combined
to allow non-programmers to write extensions to existing applications
and to design implement completely novel applications and programs.
In view of increasingly strong evidence for the need of engaging
end users in the programming of software tools, some researchers
advocate that the interface language should become a programming
language, whereas others remain skeptical about this posibility.
We propose that an integrated interface environment should be
designed within a unified semiotic framework that accounts for
interaction with and specification of computer applications. A
brief case study about a successful text editor and its extension
language reveals some of the features this unified semiotic
framework should have and provides important topics for empirical and
theoretical research agendas in the field. Integration of interactive and
programming profiles in interface systems design is the object
of the Semiotic Engineering of concretenes and abstractness in
computer-mediated interpersonal communication through software
applications.
[MCC09/96]
MAIA, A.C.; HAEUSLER, E.H.; LUCENA, C.J.P. A model for cooperative
software design. 29 p. Eng. E-mail: hermann@inf.puc-rio.br
ABSTRACT: In this paper we present a cooperative software design
process model. We are particularly concerned with software design as
a social interaction activity. Consequently, we focus on cooperative
design. By cooperative design we mean a form of design in which all
information exchange and decision-making are collectively undertaken
during design meetings. This sort of design is very interesting
because it is strongly based on cooperation among people with various
abilities and from differentareas of expertise. This leads to a great
diversity of cooperation (design) episodes to be analyzed. Design
episodes have been previously represented using diagrams called
Dynamics of Interaction Diagrams from which we have drawn up a
specification of the cooperative design process. We have now used
Coloured Petri Nets as the design process modeling language to produce
a model based discuss model validation and analyses results performed by
a tool, called ANARCO, which considers three net properties: boundedness, liveness and re-initiation. Finally, we present our
conclusions and provide comments on future work.
[MCC10/96]
DURAN, J.E. Some classes containing a fork algebra equivalent variety
involving projections and their use to specify abstract data types.
48 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Some varieties that are extensions of relational algebras
with two constants that play the role of projections are studied. They
are obtained by weakening some laws valid in abstract fork algebra.
Applications in the literature and in the specification of abstract
data types are exhibited. For the subvarieties formed with the models
that have a representable relational reduct, a representation
theorem is proved. For them the finitization problem is studied. Next
the varieties presented are compared by means of the inclusion order.
The existence of equivalent classes with a binary operation like fork
is studied. Simple models and elementary properties in the classes are
studied.
[MCC11/96]
OLIVEIRA, A.P.; OLIVEIRA,C.; CARVALHO, R.L. The application of
translation grammars to definitional theorem proving. 14 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: Since theorem proving is considered a difficult problem
it is worthwhile to use alternative methods of knowledge representation
and structuring in order to cut down on the number of axioms considered
and thus reduce the search space. Given a theory represented in such
a structured way we present a method of hybrid reasoning which
switches from resolution theorem proving to grammatical translations
to program interpretation in orther to bridge the hierarchical
levels of definitions.
[MCC12/96]
de SOUZA, C.S.; PRATES, R.O.; VAREJÃO, F.M. On classes and costs of
multimodal interfaces. 23 p. Eng. E-mail: clarisse@inf.puc-rio.br
Abstract: Multimodal Interfaces have considerably enhanced
computer-human interaction by allowing designers and users to
communicate via different codes, and often different channels.
Nevertheless, multimodality does not involve a homogeneous set of
design options. Rather, there are quite different situations for which
we propose a taxonomy of alternatives based on each mode's expressive
power relative to the application's conceptual model. According to it,
optional and mandatory cases of multimodality can be identified and
associated to specific cognitive and computational costs. We report
the results of a small-scale exploratory experiment carried out to
gauge the incremental costs of maintaining high-quality multimodes for
layout applications. And, we conclude that there are certain semiotic
conditions that maximize the chances of success in multimodal interface
design, a point which is further supported by research results achieved
in the field of Cognitive Science.
[MCC13/96]
RODRIGUEZ, N.L.R.; URURAHY, C.; IERUSALIMSCHY, R.; CERQUEIRA, R. The
use of interpreted languages for implementing parallel algorithms on
distributed systems. 12 p. Eng. E-mail: noemi@inf.puc-rio.br
Abstract: This paper proposes the investigation of the role of
interpreted languages as a tool for the development of parallel
programs in distributed environments. Besides, it argues that an
event-driven approach simplifies many aspects of concurrent
programming, since processes are never blocked on communication
primitives. The ideas have been experimented with through the
implementation of several solutions to the classical problem of
termination detection. This implementation has used a programming
environment based on the extension language Lua.
[MCC14/96]
STAA, A.v., ed. GG-01 Processos de criação e manutençao de normas de
engenharia de software. 15 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: In this document we describe how to create and maintain
technical standards internal to software development groups. The
resulting technical standards establish and explain sets of rules and
recommendations to be observed when creating or maintaining software.
The standardization process is similar to processes employed by
standardization institutions. This document defines the format of a
standard, the creation, assessment, adoption and maintenance processes.
[MCC15/96]
MILIDIÚ, R.L.; LABER, E.S. The WARM-UP algorithm: a lagrangean
construction of length restricted Huffman codes. 18 p. Eng. E-mail:
milidiu@inf.puc-rio.br
Abstract: An O(n.log n + n.log fn) algorithm is introduced for constructing an approximated solution to Variable Length Code Problem
with LengthRestriction, where n is the number of symbols in the
alphabet and fn is thehighest frequency ocurrence. The relative
error of the approximate solutionis no greater than 4/(w^(H-log n) -4),
where H is the maximum admissible length, and w is the golden ratio
1.618. From this result, we observe that we can get a very sharp
approximate solution.
[MCC16/96]
LERNER, A.; LIFSCHITZ, S.; PLASTINO, A. Análise de custos, desempenho e
balanceamento de carga de algoritmos de junção em ambientes com memória
distribuída. 36 p. Port. E-mail: sergio@inf.puc-rio.br
Abstract: We study here the practical and analytical behavior of some
parallel join algorithms implemented in a shared-nothing environment.
Particularly, we have considered the parallel approaches for the
nested-loops algorithm and the hashing algorithm. The implementations
are done in a IBM SP2, using the MPI and PVM tools. We first present a
cost model for both algorithms and some comments on the potential
performances before discussing the practical results achieved. Then we
discuss two important issues: the communication cost and workload
balancing. With respect to the latter, we suggest and implement a
parallel strategy that dynamically balance the workload based on a
better use of the computational resources available. We also show some
preliminary results and a performance discussion for this strategy.
[MCC17/96]
SANCHEZ, M.L.; MAFFEO, B. Software design baseado em encapsulamento de
dados e troca de mensagens entre subsistemas autônomos - focalizando reúso. 22 p. Port. E-mail: maffeo@inf.puc-rio.br
Abstract: This work presents a method of software design for real-time
control systems. The method is based on "Information Hiding and
Exchange of Messages between Independent Subsystems". Employing the
data encapsulation concept and concepts inherited from development
techniques using Configuration Languages, the method partitions a
complex system into more manageable subsystems intended for reuse in
other systems that have to perform similar functions.
[MCC18/96]
SANCHEZ, M.L.; MAFFEO, B. Modelagem conceitual de sistema de tempo-real -
um estudo de caso. 15 p. Port. E-mail: maffeo@inf.puc-rio.br
Abstract: This paper presents a summary of results concerning a
controlled experiment related to employing concepts, tools and
techniques for systems modeling to construct the conceptual
specification of the real-time control portion of a realistic
process-control system. The control subsystem, COMONEL, is intended
for COntroling and MONitoring ELectrons Beam Litography process, in
future use by the Department of Materials Science and Metalurgy
(DMSM) of the Pontifical Catholic University of Rio de Janeiro
(PUC-Rio). This work emphasizes an experimental approach to Software
Engineering. It follows a model of research inspired on methods of
empirical investigation used by traditional engineering disciplines
and by the sciences of nature. Specifically aiming at the conceptual
modeling of software systems, we elaborated on tools and techniques
proposed for the essential requirements specification of software for
process-control real-time systems as extensions of those in use by
practitionners for developing conventional information systems. This
choice reflects a concern related to reducing the costs associated with
the transfer to practice of the proposed method. These tools and
techniques were tested and refined within the context of a controlled
empirical process: the development of a realistic system, COMONEL,
with size and intrinsic complexity seemingly adequate to the scope of
the experiment. Specifically,the paper focuses: - the results of
Requirements Analysis and Specification restricted to the construction
of the Conceptual Model; - an overview of a deduction technique based
on the Essential Model for generating an object-like oriented design,
emphasizing the reuse possibilities of that model.
[MCC19/96]
de SOUZA, C.S.; BARBOSA, S.D.J. End-user programming environments: the
semiotic challenges. 13 p. Eng. E-mail: clarisse@inf.puc-rio.br
Abstract: Empowering users with programming abilities is an issue of
increasing importance in the software industry today. A few challenges
to be faced are the different trends between interface design and
programming language design, the lack of "semantic" embedding in
programming languages, and users' fear and lack of motivation to try
to program. End-User Programming Languages (EUPL) and User Interface
Languages (UIL) are a peculiar piece of communication between system
designer and system user, which form a continuum with each other, and
which once broken can seriously impact the whole endeavor of end-user
programming. A Semiotic approach to the problem will consider the
integration between EUPL and UIL as a dynamic integrative process,
like the processes of interpreting, understanding, and learning that users shoul go though when programming. We will illustrate how the
notion of an interpretant can organize and clarify the relationships
that hold between a single application's UI and its corresponding EUP Environment. Interpretants are crystallized into a predictable set of
variations which can be used to adjust meaning to a very precise
configuration of semantic parameters pertinent to a certain
application's domain. This approach has the potential to explain and
predict, in theoretic terms, the points of breakdown from UI to EUP
Environment.
[MCC20/96]
VELOSO, P.A.S. On infinite fork algebras and their relational reducts.
34 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A fork algebra is a relational algebra eriched with a new
binary operation. They have been introduced because their equational
calculus has applications in program construction, they also have
some interesting connections with algebraic logic. In this paper, we
concentrate on the infinite fork algebras, with the purpose of
contrasting them with relational algebras and with the finite fork
algebras. For this purpose, we introduce some concepts for the analysis
of fork algebrasand construct some special infinite relational algebras
and fork algebras. We try to correct a some what embarrassing mistake
(and simplify some constructions) that occured in a previous report.
The finite fork algebras are somewhat uninteresting, being essentially
Boolean algebras, uniquely characterized by their relational reducts.
This contrasts with the case of infinite fork algebras: we introduce
concepts and methods for the analysis of fork algebras and use some
set-theoretical constructions to exhibit many relational algebras of
each infinite cardinality with many expansions to fork algebras. We
begin by providing some background about fork algebras and their
reducts (relation and Boolean algebras): their abstract versions, some
simple results concerning the algebraic structure of fork algebras,
and their concrete, set-based, versions (fields of sets and proper
relational and fork algebras). We then recall some results concerning
the Boolean fork algebras (where fork is Boolean meet) and the finite
fork algebras (they are completely determined by their relational
reducts, which we call rigid, in contrast to the infinite fork
algebras). We examine fork-expansions of relational algebras, with
the purpose of comparing relational algebras and fork algebras. Then,
we introduce methods for the analysis and construction of fork
algebras and, finally, use some set-theoretical constructions to
exhibit many (simple, proper) relational algebras of each infinite
cardinality with many expansions to fork algebras. Such (infinite)
relational algebras demonstrate quite clearly the diversity of
possible fork operations.
[MCC21/96]
CAFEZEIRO, I.; HAEUSLER, E.H.; LUCENA, C.J.P. Paradigmas de linguagens
de programação: uma abordagem geométrica. 12 p. Port. E-mail:
lucena@inf.puc-rio.br
Abstract: This article proposes a framework for defining programming
languages paradigms. The main idea is the existence of various levels
ofabstraction over the notion of programs with inputs. Categorical
language and the concept of sheaf are used in order to obtain an
approach for a mathematical definition of programming languages
paradigms based a geometric definition of computable functions.
[MCC22/96]
FERREIRA, D.J.; SOUZA, C.S.; IERUSALIMSCHY, R. An analysis of strictly
visual codes in programming environments from a semiotic perspective.
15 p. Eng. E-mail: clarisse@infpuc-rio.br
Abstract: A semiotic analysis of the use of visual programming codes
supports the exploration of their limits for the specification of
programs. Results suggest why strictly visual representation for
program control and modularization structures are inadequate.
Nevertheless, visual codes can be combined with textual codes to help
programmers to understand and create software in a communicatively rich environment. VEPascal is one such environment being used in the study
as a reference for pilot tests. In it, images are based on geometric
forms, the composition of which evokes similar concepts to those of
the control and modularization structures in structured programming
languages. Such images are motivated by perceptions related to semantic
aspects of the control and modularization structures represented by
them and are modeled by means of L-systems designed so as tobe used
in processes of understanding, debugging or conversion of software.
[MCC23/96]
VELOSO, P.A.S. On cartesian codings and the set-theoretical
nature of fork algebras of relations. 20 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: A fork algebra is a relational algebra enriched with a new
binary operation. This class of algebras was introduced because its
equational calculus has applications in program construction. It
also has some interesting connections with algebraic logic. In
this report we examine the set-theoretical nature of fork algebras,
namely to what extent fork algebras of relations are concrete. We
investigate whether every fork algebra of relations can be
represented as a cartesian one (whose underlying coding is true
cartesian-product pair forming). We argue that the answer is
affirmative, but with a proviso. The main idea is using the room
provided by the neutral element for relational composition to
accommodate the cartesian behaviour. We first show that these widened
fork algebras of relations are still fork algebras, in that they
satisfy the fork equations, and then that can be represented by
proper fork algebra (with real identity). We also establish that
the fork algebras of relations can be represented as cartesian
ones, and exhibit a simple proper cartesian fork algebra of each
given infinite cardinality. We finally show that the enlargement
of the identity is essential, by exhibiting large collections of
(simple) proper fork algebras of relations that cannot be
represented as cartesian ones.
[MCC24/96]
STAA, A.v., ed. PG-01 Regras e recomendações para a escolha dos nomes
de elementos em programas C e C++ - Versão 1.01. 27 p. Port. E-mail:
arndt@inf.puc-rio.br
Abstract: In this document we establish rules and recommendations
forchoosing names of program elements. The standard structure of a
name is {<Product>|<Domain>}_<Type prefix><Theme><Type suffix>. This structure is used for all categories and usage modes of names
in C or C++ programs.When adopting this standard it is expected
that: a) the creation of namesis as developer independent as possible;
b) names in use can be easily and correctly remembered when creating
or modifying a program, without needing to search extensive
documentation; c) names can easily be shown to be correctly used
wherever they occur; d) documentation defining names can easily be
located; e) programmers can easily and rapidly understand and make
correct changes to existing programs.
[MCC25/96]
STAA, A.v., ed. PG-02 Regras e recomendações para o uso de constantes simbólicas em C e C++ -
Versão 1.00. 8 p. Port. E-mail:
arndt@inf.puc-rio.br
Abstract: In this document we establish rules and recommendations for
usingconstants in C or C++ programs. When adopting this standard it is
expectedthat: a) the maintenance of programs is simplified when
involving constant values; b) constants can be easily and correctly
remembered when creating or modifying a program, without needing to
search extensive documentation;c) programmers can easily and rapidly
understand and make correct changes to values and use of constants in
existing programs.
[MCC26/96]
STAA, A.v., ed. PG-03 Regras e recomendações para a programação
em C e C++ - Versão 1.01. 18 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: In this document we establish style and formatting rules
for programs written in C. These rules apply also to the sub-language
of C++ similar to C.
[MCC27/96]
STAA, A.v., ed. PG-04 Regras e recomendações específicas para a programação em C++ -
Versão 1.01. 14 p. Port. E-mail:
arndt@inf.puc-rio.br
Abstract: In this document we establish style rules for programs
written in C++, where this language differs from C.
[MCC28/96]
STAA, A.v., ed. PG-05 Regras e recomendações para a inclusão de especificações
no código de programas - Versão 1.00. 25 p. Port.
E-mail: arndt@inf.puc-rio.br
Abstract: In this document we establish rules and recommendations for
including comments in program source code. Comments are classified
according to their meaning. The meaning of every comment can be
identified by means of the source text syntax and markup text contained
in the comments. This assures the possibility to generate technical
documentation directly from source code.
[MCC29/96]
STAA, A.v., ed. PG-06 Regras e recomendações para fluxos de controle
em algoritmos - Versão 1.01. 17 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: In this document we define criteria for the control flow
designof programs. By adopting these criteria we expect that: a)
a perceptiblereduction of creation and maintenance cost; b)
a perceptible reduction ofcontrol flow errors; c) a standard control
flow organization of programs.
[MCC30/96]
STAA, A.v., ed. PG-07 Regras e recomendações para estruturas de
projeto - Versão 1.01. 21 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: In this document a set of design structure evaluation
criteria are presented. These criteria can be applied when-ever
design uses techniques based on successive decomposition. The
criteria are not directed towards a specific representation language
or design method. They apply equally well when designing algorithms,
class structures, data structures, data flow diagram structures.
When adopting this standard it is expected that: a) well organized
design structures will result; b) code fragments will tend to
aggregate all text concerning a given aspect of a problem to be
solved; c) maintenance will be simpler and less error prone.
[MCC31/96]
STAA, A.v., ed. PG-08 Regras e recomendações para o uso de instrumentação em programas C e C++ -
Versão 1.01. 20 p. Port.
E-mail: arndt@inf.puc-rio.br
Abstract: In this document active software instrumentation is
described. The instrumentation is geared towards C or C++ programs.
Several instruments are proposed: structural assertion verifiers,
which assure integrity of the contents of data structures; structure
explores, which support exploring and editing of the contents of data
structures; and verifying coroutines which perform verification during
idle times. When adopting this standard it is expected that: a) the effort required to diagnose errors will be perceptibly reduced; b) the
code will be capable to verify the correctness of data structures while
executing; c) efficiency and efficacy of tests will be increased; d)
there are means to dynamicallycontrol correctness of parallel programs,
or programs subjected to non repeatable event sequences.
[MCC32/96]
COSTA, M.; FEIJÓ, B. An architecture for concurrent reactive agents
in real-time animation. 6 p. Eng. E-mail: bruno@inf.puc-rio.br
Abstract: This paper proposes an architecture for real-time behavioral
animation based on parallel interactions between simple recursive
reactive agents and allowing for integration with external articulated
figure software. An animated sequence of a navigation scene where two
actors play different roles is generated by a prototype.
[MCC33/96]
VELOSO, P.A.S.; VELOSO, S.R.M.; FIADEIRO, J.L. On modularity under
internal and external choice in formal software development. 26 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: We examine some interactions between internal and external
choices performed by agents in the context of modular software
development of (versions of) programs from formal specifications. We
emphasise implementations of collections of specifications, which
may be viewed as describing versions of programs, and the use of
labels to tag them and their development paths. The concept of
implementation, as interpretation into a conservative extension,
is generalised to labelled collections of specifications and
formulated in categorical terms. We then show that the category of
such collections has pushouts and that this construction preserves
modularity as required for composing implementations.
[MCC34/96]
MORETH, R.C.; HAEUSLER, E.H. The decidability of MAO. 27 p. Eng.
E-mail: hermann@inf.puc-rio.br
Abstract: MAO - Modal Adjoint Operators - is a Modal Propositional
Theory, where the modal operators of necessity and possibility are
definable in the context of a Topos as adjointed geometric morphism.
The proof of Decidability of MAO follows a proof-theoretic framework.
We define a Sequent Calculus for MAO, showing MAO and sequent calculus
to MAO areequivalents in the Hilbert Style Presentation, and, the Cut-elimination Property is proved for the sequent calculus. Then observing
that any MAO-theorem has a proof-tree finitely built from botton-up,
so we have the main result.
[MCC35/96]
PORTO, S.C.S., KITAJIMA, J.P.F.W., RIBEIRO, C.C. Performance
evaluation of a parallel tabu search task scheduling algorithm.
22 p. Eng. E-mail: celso@inf.puc-rio.br
Abstract: This paper presents the solution quality analysis of a
parallel tabu search algorithm for the task scheduling problem on
heterogeneous processors under precedence constraints. We evaluate
the achieved makespan reduction of different parallel aplications
relatively to the results obtained by the best greedy algorithm
in the literature, as a function of parameters such as problem
size, system heterogeneity and number of processors. Our results
show that the tabu search algorithm is superior to the greedy
algorithm in many cases where the latter is not capable of profiting from the inherent application parallelism and system
heterogeneity.
[MCC36/96]
BATISTA, T.V.; RODRIGUEZ, N.L.R. Um estudo sobre a interoperabilidade
em ambientes distribuídos. 41 p. Port. E-mail: noemi@inf.puc-rio.br
Abstract: Development of distributed applications requires support for
interaction and integration between programs running on different
network sites, frequently on different software platforms. Current
mechanisms for the provision of interoperability in distributed systems
include software components, as proposed by standards such as CORBA and OLE/COM, and software agents. This report studies these two different
approaches, presenting basic concepts and interrelationships between
them. Some of the specific proposals, which were considered
representative of current trends, are also discussed.
[MCC37/96]
LIFSCHITZ, S.; PLASTINO, A.; RIBEIRO, C.C. Exploring load balancing
in parallel processing of recursive queries. 15 p. Eng. E-mail: sergio@inf.puc-rio.br
Abstract: Recent work on load balancing has confirmed its importance
when one wants to achieve good performance during the actual
evaluation of parallel database queries. Existing work mostly focuses
on the join processing for parallel relational databases. We are
interested here in more complex queries, such as recursive ones. The
main difference is that, in the latter case, the work due to a task
cannot be previously determined and, consequently, no method can define
at the outset the tasks to be executed in parallel in order to balance
the workload at each processor. We propose a "dose-driven" dynamic
strategy that aims at obtaining an improved workload balance and better
use of the available resources. We examine the applicability of our
strategy with its specialization to the case of the transitive closure
query. Preliminary computational results on randomly generated test
problems illustrate the efficiency of the proposed method.
[MCC38/96]
VAREJÃO, F.M.; GARCIA, A.C.B.; de SOUZA, C.S. ADD-GHS: a structured
annotation based proposal for ADD's extensions. 12 p. Eng. E-mail:
clarisse@inf.puc-rio.br
Abstract: Many approaches have been proposed to document the design
activity. ADD is a system that is based on the idea of transforming
documents from a repository of data to a model of the design. This
system provides a clearly delimited expressive language where a
previous set of domain abstractions and active and communicative
intentions is "fixed". However, design activity is "flexible" by
nature, in consequence of its own exploratory character. To solve this problem, we propose an ADD's extension that aims to increase its
expressiveness as a design rationale tool. This extension allows the
designer to include structured annotations to design documentation.
These annotations are free text annotiations organized by an index
structure captured from the context where the annotation is made. This structure supports retrieval of annotations in different context from
that the annotations is made.
[MCC39/96]
VAREJÃO, F.M.; GARCIA, A.C.B.; de SOUZA, C.S. Aquisição de design
rationale através de anotações semi-formais em documentos ativos de design. 40 p. Port. E-mail: clarisse@inf.puc-rio.br
Abstract: In this paper we classify the different approaches which
have been proposed to document the design activity. Comparing these
approaches we identify that argumentative, history and model based
approaches are complementary. In order to associate the advantages of
these approaches,we propose an ADD's extension based on the capture of
structured annotations made by the user during the design process.
These annotations are free text annotations organized by an index
structure captured from the context where the annotation is made. This
structure supports retrieval of annotations in different contexts from
that the annotation is made.
[MCC40/96]
ALMEIDA, E.S.; HAEUSLER, E.H. A lambda calculus for the Lambek
calculus. 17 p. Eng. E-mail: hermann@inf.puc-rio.br
Abstract: The Lambek Calculus was introduced by Lambek in order to
obtain effective rules to allow forming sentences and distinguishing
sentences from nonsentences. Two primitives types are defined in this
calculus and from these types is allowed to construct compound types
to the words of the sentence. We construct a lambda-calculus for the Lambek Calculus, Curry-Howard isomorphic to the sequent calculus. Some
proof-theoretical results and a denotational semantic for this
calculus, showing its adequacy with regard to the calculus, are shown.
A phase semantics, based on Girard's phase semantics for the Linear
Logic, searching to implement a verificationistic approach for meaning
in construtivism, is also shown for this calculus.
[MCC41/96]
VELOSO, P.A.S. On fork relations for program development. 16 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: We introduce the question of adequacy of a fork
relational framework for program development. We first argue that
the familiar apparatus of binary relations must be extended to
achieve this aim. Then we suggest that an appropriate extension
can be obtained by considering relations on structured universes
together with new operations.
[MCC42/96]
VELOSO, P.A.S. Fork relational frameworks on structured universes.
22 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: We examine a fork relational framework for program
development. We introduce some structural operations and constants,
consider some interconnections among them, which provide alternative
bases for the extension, and examine some properties of this fork
relational apparatus. In a previous report, we have argued that
the familiar apparatus of binary relations must be extended to be
adequate for programming; we have also suggested that an appropriate extension could be obtained by considering relations
on structured universes together with new operations. In this
report we examine more closely the nature of this fork relational
framework.
[MCC43/96]
VELOSO, P.A.S. On algorithmic fork relations: effectiveness and
program constructs. 28 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: We examine the adequacy of an extended relational
framework for program development. We argue that we can select,
by effectiveness considerations, a certain set of symbols deserving
the name "algorithmic" and we outline a programming language
correspondence, which indicates that this repertoire of symbols
provides adequate power for expressing programs. In previous
reports, we introduced the question of adequacy of an extended
relational framework for program development: we argued that the
familiar apparatus of binary relations should be extended to be
appropriate for programming and we examined the nature of such
an extension obtained by considering relations os structured
universes with new structural operations. The adequacy of such
an extended apparatus hinges on having an appropriate expressive
power. In this report we address the issue of adequate expressive
power for programming. We offer two explanations for the selection
of the algorithmic part and its computing-like nature, which
jointly justify its adequacy. First, the identification of the
proper repertoire is based on effectiveness, which guarantees
soundness, in the sense of not leaving the effective realm. The
second - more intuitive - explanation relies on the programming
language correspondence, which, besides reinforcing the first
explication, indicates that these algorithmic symbols provide
adequate power for expressing programs.
[MCC44/96]
LEITE, J.C.S.P.; SEQUERRA-BREITMAN, K. Requirements engineering
of virtual applications: some initial thoughts. 5 p. Eng. E-mail:
julio@inf.puc-rio.br
Abstract: In this paper, we argue that Web applications, here
referred to as virtual applications, pose different kind of
challenges to requirements engineering (RE). Our ongoing experience
in building an Internet collaborative site exemplifies those
challenges. Our virtual application is devoted to the acquisition
and compilation of a general requirements engineering bibliography,
database. Most RE methods and tecniques are centrered in the
communication between stakeholders, i.e., developers, users, and
clients, but in the case of virtual applicatons the usual
distinction between stakeholders is not so clear. Another
characteristic of virtual applications is the role of technology,
which imposes standarts which directly constraints the definition
space. As such, the traditional sequence from requirements to
design phases becomes blurred. We argue that virtual applications
require innovative requirements processes.
[MCC45/96]
UCHOA, E.M.A.; MELO, R.N.; LIFSCHITZ, S. Interoperabilidade de objetos
em sistemas de bancos de dados heterogêneos. 30 p. Port. E-mail:
rubens@inf.puc-rio.br
Abstract: Heterogeneous database systems have been considered one of
the most feasible solution for the integration of existing systems, autonomous and different, without the need of changing them. Object
oriented standards have been used as a strategy for a flexible
coordination and integration of information resources connected
through networks. In the heterogeneous database architecture, these
standards may be used for integration and interaction among the
heterogeneous components, increasing the federation flexibility and
its expansion capacity in new environments. We present in this work
the HEROS project, which has been developed in PUC-Rio, and discuss
object interoperability issues considering the CORBA architecture,
a object oriented standard. Other related projects - MIND and Jupiter -
are also cited and compared to HEROS.