Monografias em Ciência da Computação
1969-1992
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 were published in our series Monografias em Ciência da Computação (ISSN
0103-9741), from 1969 to 1992, and edited
by Prof. Carlos Lucena, starting 1993. 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: 24/APRIL/2009
1969
[MCC01/69]
SILVA, R.C.B. Conversion from BNF to syntax-graph, and syntax-graph reduction.
24 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In syntax directed compiling, the syntax of the source language is
described in the form of a data structure upon which the parser or analyser will
work. This paper presents a program that will convert BNF expressions into data
structures called the Syntax Graph. After the conversion of this list-form
structures, some reductions are made which will contribute towards the reduction
of parsing time and storage space. This Syntax Graph structure and Parsing
mechanism is described in a techical report by D.J. Cohen and C.C. Gotlieb.
[MCC02/69]
MASON, J.; SANTOS, J.R.R. An iterative computer solution for the equations of
elastic wall-girders. 18 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This report presents a computer solution of the eliptic differential
equations of elastic wall-girder theory. The method of solution is iterative and
overrelaxation is used in order to speed up convergence. Two kinds of boundary
conditions are accounted for.The results of the calculations will be commented
and comparisons will be made with related known solutions.
[MCC03/69]
FURTADO, A.L.; FREIRE, F. Formula manipulation in the Fletcher and Powell
optimization method. 13 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: The work is concerned with general least square curve fitting using the Fletcher and Powell
method. The method requires an evaluation of partial derivatives at each step.
The resulting derivatives has been either evaluated interpretively or compiled
into machine language and then executed under control of the optimization
program. An implementation of this technique was written in Fortran IV, MAP and
the list processsing system LISP. An IBM 7044 (32 k) of the Pontifícia
Universidade Católica do Rio de Janeiro was used to run a number of examples.
[MCC04/69]
FURTADO, A.L. Solution of ordinary differential equations by the Taylor series
method using formula manipulation. 4 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: The use of table series has been avoided in computer programming on
account of the necessity of obtaining higher order derivatives by hand. Formula
manipulation automates differentiation and provides mechanisms for the
evaluation of resulting derivatives. This makes it pratical to use Taylor
series, for instance, in the solution of ordinary differential equations. One
advantage of this generality: Taylor's formula remains the same as we add to it
as many
terms desired. It is also very easily extended to solve equations of any order,
or systems of any number of equations. Tests were performed on the IBM 7044 of
the Pontifícia Universidade Católica do Rio de Janeiro - Brasil.
[MCC05/69]
CARVALHO, S.E.R. On the Brooker-Morris expression recognition routine. 5 p. Eng.
E-mail:bib-di@inf.puc-rio.br
Abstract: A program for the Expression Recognition Routine developed by Brooker
and Morris was presented by Douglas K. Smith in his article "List Processing
Language Slip" (Rosen, Programming Systems and Languages) (Mc Graw Hill). The
purpose of this paper is to develop some considerations on certain aspects of
the program, particulary those referring to the syntax that must be constructed
for the Brooker and Morris routine.
[MCC06/69]
LUCENA, C.J.P. A software writing system. 14 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: The work illustrates through an example the COMASS meta language which
can handle a class of languages reffered to as z-language. This z-language is
composed of a rather classical ses of Fortan-like statements.
[MCC07/69]
CARVALHO, R.L. A slip application: the construction of turing machines. 7 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The work attempts to define what a turing machine and presents on of
its possible formulations. A method is presented to construct any turing
machine, being SNP the language which is adapted for such treatments.
[MCC08/69]
CARVALHO, S.E.R. A recognizer for a precedence grammar. 20 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: The work describes an algorithm which analyses a given string, stating
whether the string belongs to a grammar generated by a given language or not.
The recognizer represented here may be classified as a left-to-right, bottom-up
recognizer in the sense the string is repeatedly searched from left to right
until a substring is found which may be replaced by a certain symbol.
[MCC09/69]
FRANCISS, F.O.; PUCCINI, A.L. Identification of minor subsets pertaining to a
major set through simultaneous analysis of random samples. 8 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: abstract not provided.
[MCC10/69]
FRANCISS, F.O.; PUCCINI, A.L. Seepage in Earth dams with horizontal filter. 6 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper consists basicaly of a FORTRAN IV program to determine
analitically the flow net in an earth dam with an horizontal filter.
[MCC11/69]
SANTOS, J.R.R.; RIGAL, A.; BORDENAVE, M. Discretisation et resolution numérique
de l'equation des ondes. 34 p. French. E-mail: bib-di@inf.puc-rio.br
Abstract: This work aims at the discretisation and the numerical solution of the
wave equation by the relaxation method.
[MCC12/69]
SANTOS, J.R.R.; MASON, J. A finite element computer program for plane elasticity
with consideration of thermal effects. 16 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In this work, a programming method for the technique of
finite elements in plane elastic problems is developed. The characteristic
feature in the programming method is that it approaches closely the treatment in
the theory of structures. The program was written in FORTRAN IV for a 7044 IBM
computer. Numerical applications to some examples are added as an illustration.
------------------------------------------------------------------------------------------------------------------------------------
1970
[MCC01/70]
FURTADO, A.L. A two-level Newton method for function optimization. 9 p. Eng.
E-mail: furtado@inf.puc-rio.br
Abstract: The Newton method is used iteratively at two levels to determine an
unrestricted local minimum of a general function f(x1 , x2 , ... , xn). At the
first level a vector delta=(formula) is computed and at the second level a
scalar alfa is obtained to minimize (formula). Both levels involve a preliminary
first and second order partial differentiation and this is performed
symbolically by the computer. Run-time compilation translates the resulting
derivatives into machime code. This ensures the high speed of the repeated
numerical evaluations. The sub-program package to implement the algorithm was
written in FORTRAN IV plus the SLIP (1) system, but it is feasible in any
language or system supporting formula manipulation capabilities (2).
[MCC02/70]
PUCCINI, A.L. A Fortran program to solve the assignment problem. 18 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: The basic proposition of this report is to present a Fortran program,
recently developed, that solves the assignment problem.
[MCC03/70]
CHAITIN, G.J. Computational complexity and Godel's incompleteness theorem and to
a mathematical definition of 'Life'. 21 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The state and time complexities are defined for computations of
infinite sets of natural numbers by means of Turing machines. It's proved that
there are arbitrarily complex infinite computable sets of natural numbers. In
formal theories, however, it is not possible to demonstrate that specific
examples of such sets are of arbitrarily high specific complexity.
[MCC04/70]
FURTADO, A.L. A low-level mathematical pattern - matching algorithm. 37 p. Eng.
E-mail: furtado@inf.puc-rio.br
Abstract: A number of questions concerning pattern-matching are discussed with
the aid of an algorithm that is now operational for the IBM-7044, under a
modified $IBFTC FORTRAN IV compiler. The pattern-matching processes discussed
here are classified as low-level, in the sense that they exhibit a score of very
detailed mechanisms
that in general are quite understandable for a programmer but inconvenient for
direct use by a mathematician. Such mechanisms, however, indicate how
higher-level facilities could be constructed from them. Some features were taken
from several existing systems and a few of them are original. Experience is
still needed to confirm their
usefulness and to suggest further improvements and extensions. A member of
examples are scattered through the following sections and four of them are more
throughly expounded at section 4.
[MCC05/70]
STAA, A.v. Basic functions for handling binary trees. 56 p. Eng. E-mail: arndt@inf.puc-rio.br
Abstract: In this paper several basic subroutines for handling binary tree
structures are presented. The subroutines may handle threated binary tree
representations of trees and/or normal binary tree representations. The
described functions perform the following activities: pointer handling;
insertion and creation of nodes; copy and deletion of trees; conversion from
normal tree to threaded tree representation; traversing of threaded binary trees;
schematic
printing of trees. Some utility subroutines are included. The main algothms are
presented and the use of the subroutines is described.
[MCC06/70]
SALIM, C.S.; SALIM, H.K. The Sparse system. 16 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The sparce system is a set of subroutine that manipulates both sparse
matrices and polynomials which are stored in the memory of the computer as
linked lists. The system can be split conveniently into two distinct parts; the
first concerns sparse matrices and the second concerns sparse polynomials; so
these topics are presented separately.
[MCC07/70]
SANTOS, S.M. Transformational grammars as models for natural languages. 14 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The aim of this paper is to present Transformational Grammars as
possible models for natural languages. To this end, there is an attempt at
showing that such Transformational Grammars can satisfy some of the required
conditions of the said models. The critarion of recursiveness is particulary
discussed. To make the discussion possible a mathematical model for the
Transformational Grammars in minutely presented, this model was elaborated
by Barbara Partee and Seymour Ginsburg.
[MCC08/70]
STAA, A.v. The COMCOM - software writing system. 18 p. Eng. E-mail: E-mail:
arndt@inf.puc-rio.br
Abstract: The COMpiler COMpiler system was primarily designed as a tool for
compiler writing. By compiling we mean any kind of automatic artificial language
translation. In general the system, as seen by the user, is composed of two very
flexible languages; a syntactic metalanguage and a semantic matalanguage. We
required the object compiler produced by this sysyem to be efficient and not
just another academic research tool. Powerful capabilities for compiler writers
were supplied that enable the design of efficient object compilers which produce
good target codes. Moreover the system also provides for experimental work on
compiling techniques, leading to comparative study of different compiling
strategies. A feature a system of this kind ought to have is as much machine
independence as
possible. For that the COMCOM system compiles object.
[MCC09/70]
KERSCHBERG, L.; HAPP, W.W. Eigenfunction propagation in interconnected systems.
8 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The complete set of characteristic functions for a multiterminal
system is defined, and the test configurations for these functions are
enumerated by group theoretic and combinatorial techniques. The
configurations are coded in binary form and generator masks reduce the
enumeration to the union, shift, and masking of binary codes. A system
interconnection algorithm expresses the composite system's eigenfunctions
in terms of the eigenfunctions of its multiterminal compoments.
[MCC10/70]
LUCENA, C.J.P. An approach for mapping abstract information structures on
digital computer memories. 11 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: One of the strongest motivations for research in the area of Computer
Science is to give software a firm basis. By firm basis we mean a
systematization of concepts, but not unecessary formalism. The first issue that
arises when one explores along these lines is the need for a unified principle
for, computer information storage. The mapping of abstract or concrete models
into storage should ideally be performed in a well defined fashion. In our work
we propose one theory for representing information structure in computers.
Instead of proposing a "general recipe" for data structures, we design a
formalism that enables a constructive study of modeling techniques in
programming. The system emcompasses all the know types of data structures. The
theory of directed graphs is used as the basic tool for this work. An attempt is
made to generalize graphs to structures involving vertices (nodes) composed of
various information sets with connections among them. The basic element of our
system is called an "information module". It contains features which establish
interconnections with other modules (variable number of
links), as well as descriptors that describe the information associated with the
module. A descriptor can be a diagraph in which each vertex (module) can also be
a digraph. Some interesting results can be obtained when we design algorithms in
the context. The work also discusses some issues related to the implementation
of the proposed system.
[MCC11/70]
FURTADO, A.L. Recursive techniques in dynamic programming. 20 p. Eng. E-mail:
furtado@inf.puc-rio.br
Abstract: Dynamic programming is an important area of operations research. It
allows the solution of a wide class of optimization problems that are
expressible in a certain very general recursive formula. Since recursion was not
available in most programming languages, these problems could not be solved
through a direct application of the formula. A frequently laborious task has
been undertaken to devise iterative techniques for each problem. However if one
has an efficient implementation of recursion, the direct approach becomes more
attractive, for no preliminary
reformulation is needed and ease and naturalness in the transition from the
problem to the programming algorithm are ensured. The example we present
here-the determination of the maximun or minimun path in a network - also
illustrates the use of list processing to provide a quite natural input format
and a convenient storage representation for a graph. The use of a non -
numerical technique, like processing, to an essentially numerical problema is a
noticeable trend in present day programming.
[MCC12/70]
CARVALHO, R.L. On the use of pushdown automata for the parsing of sentences of
context-Free languages. 11 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This work is a different presentation of an existing algorithm for
parsing sentences of context-free languages. A formal presentation of the
algorithm is given, and improvement are made in the processing time.
-------------------------------------------------------------------------------------------------------------------------------------
1971
[MCC01/71]
MARTINS, L.C. Preventive maintenance scheduling on an equipment. p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: The problem of preventive maintenance planning for a system becomes
more difficult as the number of system components increases. This study presents
a computational solution to the problem of minimizing the weekly load
fluctuations of a maintenance department over a once year period. Three
algorithms are developded which provide adequate solutions to different
formulations of the planning problem. These algorithms are: Similation by
randomic solutions; Load soting; Partial solutions. The results obtained by
means of the algorithm were excellent. In the ten cases studied, the weekly load
profiles over a one year period exhibited small fluctuations. Also, a
theoretical formulation of the problem is presented by means of Fourier Series
expansions.
[MCC02/71]
FURTADO, A.L. PUCMAT - A programming module for arithmetic pattern-matching. 28
p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: An effort towards a convenient notation for pattern-matching as
applied to formula manipulation of arithmetic expressions led to the definition
of a compact set of statements. These are being experimented with, at present,
under the form of an independent programming language (PUCMAT) which is compiled
into an extended FORTRAN IV language via the COMCOM [1] software-writing system.
However PUCMAT will be better utilized as a module of some high level language
at a later stage. PUCMAT is very much indebted to FORMULA ALGOL, COMIT, SNOBOL,
CONVERT, AXLE and SCHATCHEN.
[MCC03/71]
QUINTELLA, H.M. Diophantine systems and applications. p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This work contains a description of a technique for the resolution of
the linear Diophantine equations systems and, presumably, is original in many
aspects. On the other hand it offers a first application of the described
method to a typical problem of linear programming; the transportation problem.
It is hoped that this method turns out to be, an alternative to the traditional
methods of linear programming which hinges on linear algebra. In the first place
because it is simpler, employing as it does arithmetical concepts. Secondly,
because everything points to the fact that it has a greater computational
efficiency. A computer implementation being now operational at
PUC, a series of tests and comparisons are in process.
[MCC04/71]
BROWN, M.P. A comparative study of symbol tables. 73 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Since symbol table look-up appears so frequently in everyday
programming, an appropriate choice of the techniques to be employed strongly
reflects on the efficiency of such programs. The purpose of the present work is
to compare the best known symbol table construction and search techniques, with
regard to processing time and core storage requirements. An attempt is then made
to establich some criteria that would indicate which technique should be used
for a particular application. Experiments were run on an IBM-7044, using from
one to six characters (one machine word) for symbol names, Modified algorithms
to work with variable length symbols are presented but no measurements are given
for these.
[MCC05/71]
KERSCHBERG, L.; SKANDERA, R. Urban traffic under computer control: a
logical-mathematical view. 15 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: For about ten years now, American and European cities like San Jose (California),
Fort Lauderdale (Florida), New York, Toronto, or London, have been enjoying
benefits of process control based on eletronic computers in the
management of city traffic or transportation, and lately also for many other
tasks of urban administration. During the nineteen-seventies, electronics
traffic control will be installed in many other American and European cities.
The possiblity of traffic-light control has also been under consideration for
Brazilian cities like Rio de Janeiro or Sao Paulo, and during the last few years
a frequent discussion subject of the popular press. That electronics will
eventually come also to the Guanabara Bay is beyond doubt, only the time of its
arrival is in question. When it comes, it will be based on a set of
logic-mathematical propositions known generally as process control. The purpose
of this paper is to explore the main arguments of this logic, and particulary of
its ramification for urban administration. In this manner they may serve, it is
hoped, as an opening gambit for city engineer and administrators for a deeper
study of the subject when they ultimately come face to face with the problem.
[MCC06/71]
CARVALHO, R.L.; MILLAN, M.R. On the construction and minimization of finite
state automata. p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The aim of this paper is to present an effective construction of the
finite state automata (fsa's) from a set of regular expressions. The
contribution of this paper consists of the fact that this presentation provides
a complete algorithm solution for this problem. The minimization of the fsa is
shown to be independent of the theory of sequential machines.
[MCC07/71]
RIBEIRO, M.T.; FURTADO, A.L.; PFEFFER, A.S.; MEDEIROS, A.T. Graph - Processing
with LISP. 29 p. E-mail: furtado@inf.puc-rio.br
Abstract: Graph-processing languages or packages usually represent graphs under
matrix or list form. Although algorithms using lists are not in general the most
efficient, they easy to write and to understand. New algorithms could first be
sketched in LIST and then translated into another form, having in mind run time
and core storage minimization. In this tutorial paper a simple LIST
representation for graphs in presented together with a number of basic functions.
All programs were tested on an IBM - 1620 of the Centro Brasileiro de Pesquisas
Fisicas.
[MCC08/71]
HESS, L.A. Process of reducing figures into graphic structures: minimization and
continuity of graph paths. p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In interdisciplinary being lies the significance of this study. The
development and formalization of the ideas was possible only through cooperation
and understanding of the professionals whose fields were involved. While its
application in Industrial Design is still limited at this time, nevertheless, it
represents an initial step towards the Computer Aided Design. Placing in the
work itself our gratitude to those whose time and effort was spent, we present
it as a work open to futher development. For operational purpose the traditional
grid, upon which figures are represented, has been conceived as a matrix, thus
freeing one from continual reference to figure coordinates. The assertion, of
whether or not there exists a fuctional relation among the elements of the
matrix determines which of two methods each uttterly distinct in theories of
formalization - will be used for the matrix developing process. The choice of
method is decide according to the applications required.
[MCC09/71]
LUCENA, C.J.P.; CUNHA, L.F.A. A modelling technique in programming. 13 p. Eng.
E-mail: lucena@inf.puc-rio.br
Abstract: This paper presents an approach for the implementation of the
semantics of information structures. It is hoped that the facility described
will be useful in the process of incorporating the existing formalisms for the
description of information structures in programming languages. The system here
discussed in operational in the form of a package of sub-programs written in
FORTRAN and assembler language which can, with very small effort, be adapted to
any existing computer system.
[MCC10/71]
PASSOS, E.P.L. Introduction to mechanical theorem proving. p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: The aim of this paper is to provide an introduction to theorem proving
in Formal Theories. It is based on a work by Newell, Shaw and Simon, "The Logic
Theory Machine", where the authors present a program in IPL for proving the
Theorems of Propositional Calculus of Principia Mathematica. This paper present
a program 3 for proving the above theorems using a programming module (PUCMAT) 2
which is compiled into an extended FORTRAN IV Language via the COMCOM 9
software-writing system, (IBM 7044).
[MCC11/71]
CHAVES, T.F. An approach to predictors experiments and determination of better
methods. 13 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Based on experiments and on the analysis of its results we found new
formulae which used as predictors gave us better approximations than the other
well known ones.
[MCC12/71]
MACEDO, L.T. A set of programs to test and parse LL(K) type languages. 14 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper describes a system which tests the LL(k) condition for a
given grammar and provides a recognizer for strings of the language generated by
this grammar. During the recognition phase the system generates code so that we
have, in a semantic stack, information about the code generated so far.
------------------------------------------------------------------------------------------------------------------------------------
1972
[MCC01/72]
FURTADO, A.L.; SANTOS, C.S.; ROSCHKE, S.I.; BAUER, J.C.P. Finding the optimal
colorings of a graph. 21 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: The problem of finding the chromatic number of a graph and exhibiting
one or all optimal colorings has several practical applications. It is
equivalent to partitioning a set of objects, some of which are pairwise "incompatible",
into the minimum number of cells, so that no two incompatible objects are
assigned to the same cell. Situations where this applies are production
scheduling, construction of examination timetables, storage of goods, etc.
Heuristic procedures for the solution of the described problem have been
developed by Berge,
Welsh and Powell, and Wood. More recently Christofides has presented a
deterministic algorithm that is based on the concept of maximal internally
stable sets. This paper also employs this concept to suggest three different
approaches: a. a simple algorithm with relatively small storage requirements; b.
an integer linear programming formulation; c. a branch and bound algorithm, that
keeps storage requirements at a reasonable level aims at efficiency by
minimizing the number of steps. We have used as sub-algorithm an efficient
method by Bron-Kerbosch
originally developed for determining the cliques of a graph, but that can be
easily adapted to obtain the maximal internally stable sets. A number of
examples were run on an IBM/360 model 40.
[MCC02/72]
SOUSA, F.P. A taxonomic information handling system. 20 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper consists of a description of an information retrieval
system designed for taxonometrics purposes, but with a reasonably wide range of
applications. Simple implementation and use characterize this system that can be
used in batch or tele-processing by means of an English-like language and which
grammar and syntax can be quickly learned. The user can easily update the data
banks, which makes the system totally independent of specialized personnel.
[MCC03/72]
BAUER, J.C.P.; FURTADO, A.L. Extending the control structures of PL/I. 22 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A number of control statements have been suggested as extensions to
ALGOL 60. Several languages such as ALGOL W, EULER, BLISS and PASCAL have
implemented one or more of them. Besides contributing to a more
natural style in programming, they can be used in situations where a go to
statement would seem to be unavoidable. Some authors now tend to believe that
the go to statement should not be present in well structured
programs [2]. The implementation described here uses the preprocessor facility
of PL/I. This approach has the follwing disadvantages: a. the preprocessor phase
consumes additional computer time; b. some characteristics of the new statements
were imposed for the convenient use of the preprocessor. And as advantages: a.
being written in the high level preprocessor language the program to implement
the statements is easy to understand and modify; b. since the PL/I compiler
itself is not changed the regular PL/I programs are not affected. It may be
expected that
if the new statements prove their value through actual use, which is made
possible by this implementation, their addition to the PL/I language could then
be considered.
[MCC04/72]
FURTADO, A.L. A canonical form for minimum state finite automata. 21 p. Eng.
E-mail: furtado@inf.puc-rio.br
Abstract: A well-known algorithm exists for obtaining from a finite state
automaton (fsa) accepting a set L the corresponding minimum state fsa, which is
unique up to an isomorphism. The algorithm is indicated and a thorough and
detailed description is given. If the algorithm is applied to two fsa M and M'
the two resulting minimum state fsa should be isomorphic whenever M and M' are
equivalent, in the sense of accepting the same L. However the time requirement
for testing for isomorphism is given by O (n!), n being the number of states in
the minimum state machines. A simple addition to the basic minimization
algorithm is presented, whereby the minimum state machines will be equal rather
than just isomorphic. Testing for equality is performed in linear time. The
modified algorithm yields a canonical form for all fsa accepting a given L. The
key idea-lexicographic ordering - has been suggested by Corneil.
[MCC05/72]
BOVET, D.P. On the use of models employing both simulation and analytical
solutions for scheduling computing centers. 13 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Large scale computing centers are expensive facilities where
considerable savings can be achieved through improved scheduling of operations.
Several proprietary packages that use both simulation and analytical solutions
have been developed to yield optimized schedulings. This paper discusses in some
details several approaches that have been taken to solve this problem and
explains the trade-off existing between accuracy of the results obtained and
costs involved in setting up the model.
[MCC06/72]
GALDA, K.; PASSOS, E.P.L. Applications of quantifier elimination to mechanical
theorem proving. 17 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The purpose of the paper is to develop algorithms, suitable for
computer programming, which apply quantifier elimination methods to prove
mathematical theorems. A general discussion attempts to relate the present paper
with other work in mechanical theorem proving. A detailed algorithm for the
theory of densely ordered sets without first or last element is shown, along
with examples of theorems proved with this algorithm. Then the theory of abelian
groups with total discrete orderings is considered. Due to the complexity of
quantifier elimination in this theory, the algorithm is not presented in
complete detail, but an outline showing the principal stages is given. The
similarities between the two algorithms are emphasized to show how all the
programs can be written within the same framework. A discussion of the actual
computer implementation of the algorithm concludes the paper.
[MCC07/72]
FURTADO, A.L. Algebraic concepts in data structures. 62 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A survey of same aspects of data structures to which algebraic
formalisms apply is attempted. In each section one or a few references provide
most of the material; they are marked with an asterisk in the list of references.
We belive that the concepts reviewed here are strongly related and that they
should be considered together for any further work in the area of data
structures. Two valid research directions can be pursued: a). the construction
of a comprehensive formalism that would contribute to a better understanding of
data structures, and hence to the study of program correctness and low-level
complexity; b). the elaboration of a reasonably powerful
data definition facility capable of supporting the more complex data structures
currently used in data base systems and non-numerical computation in general.
[MCC08/72]
SANTOS, S.M.; MILLAN, M.R. Automatic proofs for theorems on predicate calculus.
22 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The attempt to use a computer to prove propositions of formalized
theories has characterized in the last few years a special field of Computer
Science, Artificial Intelligence. Our aim in this paper is to prove theorems of
propositional and pure predicate calculus in a automatic way using the
programming language SNOBOL-4. We choose this language because it is appropriate
for handling structures such as arrays and trees. The formal system we use is
the one developed by M. Smullyan. This system constructs proofs for expressions
in the propositional, as well as in the predicate calculus, in the form of trees,
or analytic tableaux as Smullyan calls them. The proofs for
propositional calculus being straigh-forward, have the advantage of being very
simple and elegant. It is even more striking that those properties are also
present in proofs of expressions in the predicate calculus for which we cannot
provide a decision procedure. Then it is not a trivial task to find an automatic
way of constructing proofs for formulas in a subset of its theorems.
[MCC09/72]
KERSCHBERG, L. The primal factorization of complete graphs. 16 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: The Kronecker sum and Kronecker product of graphs are defined. For the
class of complete graphs, Km, on m vertices, a primal factorization is obtained
in terms of the Kronecker sum and product of prime complete graphs, Kp, p a
prime.
[MCC10/72]
TEIXEIRA, S.R.P.; CUNHA, L.F.A. On the reduction of the size of transition
matrices. 26 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Although the general context free grammar has shown to be a suitable
model for programing language, it has not been used in practice due to time and
memory space limitations. More restricted models which guarantee parsing time
proportional to n (where n is the length of the input string) have been used
instead. Among these
schemes, the use of transition matrices has proved to be remarkably efficient.
The great speed of this method lies in the fact that for each table reference it
does, it makes a syntatic reduction on the sentential form, no further searching
being necessary. The transition matrix is accessed at each step of compilation
given the element at
the top of the stack and the next element on the input string. Some entries in
the matrix specify reductions to be made while others specify error conditions.
The main disadvantage of the method is the large size of the transition matrices
for practical programming languages. This paper presents a method to partition
the original grammar into several grammars so that several transition matrices
are used instead of just one. Sufficient conditions are given to
allow the processor to switch matrices as it is parsing a sentence of the
original grammar. This method has all the advantages of the transition matrices
technique (mainly speed), while sensibly reducing the memory space required (the
most serious drawback of the original method). Besides, for some grammars and
partitions the new method is more powerful than the original method, as shown.
The method presented in this paper is being used in the parser of a fast
resident PL/I compiler for the IBM 370/165, being developed at Pontificia
Universidade Catolica do Rio de Janeiro. It has shown great speed and moderate
memory requirements.
[MCC11/72]
SANTOS, C.S.; FURTADO, A.L. G/PL/I - Extending PL/I for graph processing. 24 p.
Eng. E-mail: furtado@inf.puc-rio.br
Abstract: G/PL/I extends PL/I to handle both directed and undirected graphs,
which may be multi - graphs. An arbitrary number of attribute-value pairs can be
associated with the graph itself and with it nodes and edges. Special kinds of
sets together with set theoretic operations are provided. The implementation
uses pre-processing. It consists of a supervisor and modules for several
extensions to PL/I, G/PL/I being one of them.
[MCC12/72]
TEIXEIRA, S.R.P.; NUNES, D.J. SDM - a Syntax Directed Macro-Processor. 9 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: SDM is a Syntax-Directed Macro-Processor which allows one to extend
the syntax and semantics of a high level language. It is a string processor
which uses R-expressions to define the syntax of new statements (macros) and a
language, SL, to define the semantics of these statements.
------------------------------------------------------------------------------------------------------------------------------------
1973
[MCC01/73]
HARTMANN, C.R.P.; KERSCHBERG, L. A characterization of algebraic
functions whose solutions are Nth roots of unity. 14 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: This investigation presents existence theorems for algebraic
fuctions over Galois Fields which admit nth roots of unity as solutions.
For a special class of these functions, the exixtence test reduces to
calculating the greatest common divisor of integers. These results are
applied to the characterization of a class of binary cyclic codes whose
minimum distance is exactly three.
[MCC02/73]
CHAVES, R.N.M. The use of learning algorithms in non-minimax solutions
of games. 25 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper deals with the problem of two-person, sero - sum
games in the case that one of the players is using a strategy different
from the usual von Neumann minimax strategy. The method is to use
learning algorithms which are based on one player's estimate of the
other's strategy after various repetitions of the same game. The
algorithms attempt to let the first player take full advantage of the
other1s weaknesses. Suppose at the K - th repetitions of the game the
first and second player have apparent strategies of X(K) and Y(K)
respectively. Then the strategy of the first player for the next
repetitions is determined by the difference equation. [equation]
f(y(K)) represents the optimal pure response of the first player
to the strategyY (K). (K+1) is a parameter to be chosen to assign
weights to different strategies. Various models of this situation
are studied by varying the different parameters of the equation.
Empirical test of the results are made using a 3x3 payoff matrix
which has no saddle point and a unique minimax solution.
[MCC03/73]
KERSCHBERG, L. The characteristic polynomial of graph products. 18 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: An algebraic method is presented which calculates the
characteristic polynomial of the product of graphs (boolean operations
and expressions on grphs) in terms of the polynomials of the factor
graphs.
----------------------------------------------------------------------------------------------------------------------------------
1974
[MCC01/74]
FURTADO, A.L.; PFEFFER, A.S. Pattern matching for structured programming.
13 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A programming module for adding a simple string pattern-matching
capability to PL/I is presented. It is argued that pattern-matching is
compatibe with control structures that conform to the principles of
structured programming.
[MCC02/74]
PASSOS, E.P.L.; SILVEIRA, G.F.G. Applications of quantifier elimination
to mechanical theorem proving - implementation. 19 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: The purpose of this paper is to implement by using LISP 1.5
functions defined in Galda & Passos having as equipment IBM/370-165. The
formula transformations are special functions which can be utilized
by any of the algorithms mentioned in this paper. The algorithm in detail is
implemented for the theory of Densely Ordered Sets Without First or Last
Element. Appendix D contains a complet list of the program. In this paper
the authors intended only to present the implementation of the
algorithms described in a paper by Galda & Passos. Consequently a previous
acquaintance with it is required to the understading of the present paper.
[MCC03/74]
TEIXEIRA, S.R.P. Time-Varying languages. 18 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: A characterization is given for a subfamily of the family of
time-varying languages and some of its properties are studied. A
restriction of g.s.m. mappings and substitutions is given for which both
families are closed.
[MCC04/74]
LUCENA, C.J.P. On the synthesis of programs and reliability. 21 p. Eng.
E-mail: lucena@inf.puc-rio.br
Abstract: This paper discusses the problem of synthesis of reliable
programs. Reliability requires a good approximation of the solution of the
problem of correspondence between a program and its flowchart. Reliability
also calls for the ability of program structures to fail-softly, to permit
simple modification, and to permit large-scale composability.
[MCC05/74]
FURTADO, A.L. Characterizing sets of data structures by the connectivity
relation. 23 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A formalism based on the directed graph connectivity relation
is presented, where a first order predicate calculus notation is used
with the purpose of defining sets of data structures and characterizing
the structural operations on them.
----------------------------------------------------------------------------------------------------------------------------
1975
[MCC01/75]
MYLOPOULOS, J.; FURTADO, A.L. Using graph grammars for the definition
of sets of digraphs. 34 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A graphn grammar formalism is described and used to define
several interresting sets of digraphs such as strongly connected
graphs, rooted acyclic graphs and lattices. It is argued that the
formalism is descriptionally powerful and inexpensive and that it
constitutes a constructive method for the precise definition of many
structures arising in computer science. A discussion comparing
constructive methods for the definition of sets of structures to
axiomatic ones is also included.
[MCC02/75]
CARVALHO, S.E.R. An efficient way of selecting lexical types. 15 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: When constructing an analyzer for a given grammar, the choice
of the lexical types for the grammar is usually based solely upon adhoc
criteria. In this paper we show a way which more efficient criteria can be
used to that effect. First we introduce some properties lexical analyzers
should necessarily possess, obtaining a set of candidates for lexical
types. |Then we show how for a particular analyzer model the set of
candidates can be refined, until we are left with a set of nonterminals
which can be considered lexical types for the given grammar.
[MCC03/75]
CARVALHO, S.E.R. On the generation of improved intermediate language
for a class of arithmetic expressions. 28 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: Many algorithms for the production of improved object code
for arithmetic expressions have been described in the literature. In
particular, Sethi and Ullman [6] present an algorithm for which the
optimality property is proved with respect to the length of code
produced. This algorithm consists mainly in modifying the intermediate
language representation of an arithmetic expression of a certain class
in such a way that full advantage of the algebraic properties of
commutativity and associativity is taken. In this paper we describe
an augmented syntactical analyzer that directly produces improved
intermediate language in the sense of [6], given an arithmetic
expression in the same class as described in a p.
[MCC04/75]
LUCENA, C.J.P.; SCHWABE, D.; BERRY, D. Issues in data type construction
facilities. 26 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: This work deals with the problem of synthesizing correct data
representations for data abstractions. An extension of the "cluster"
approach is proposed that also addresses the problems of efficiency and
portability.
[MCC05/75]
STAA, A.v.; LUCENA, C.J.P. On the implementation of data generality.
13 p. Eng. E-mail: arndt@inf.puc-rio.br
Abstract: Data generality is the property through which program
modules are able to communicate via arbritary data structures. Since
the design of module interfaces is a very difficult and error prone
activity in systems design, the implementation of data generality is
a very desirable goal in programming. The present work describes one
approach to the implementation of data generality and sketches the
algorithm for its implementation.
[MCC06/75]
CARVALHO, S.E.R.; LUCENA, C.J.P.; SCHWABE, D.; ROSA FILHO, P.L. PEP:
a language for provability, efficiency and portability. 39 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: PEP is a very high level language aimed at Provability,
Efficiency and Portability. The language PEP has a comprehensive set
os data and control structures, all of which can be easily defined
axiomatically. PEP user's have the ability to define abstract data
types. The language is informally described, and an implementation
model is presented.
[MCC07/75]
CARVALHO, S.E.R. On type definition facilities in very high level
programming languages. 8 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Very high level languages are being developed to serve
as a tool in the production of reliable software. One of the features
of such languages in the ability programmers have of defining new data
types. In this paper we define one such type, the domain, which, when
coupled with a generalized FOR statement, can be a valuable aid to
programming in high levels of abstraction.
[MCC08/75]
NOVOA, M.A.A.; CARVALHO, S.E.R. On the use of pointers and the teaching
of disciplined programming. 27 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In the past few years there has been considerable debate
over the question of pointers in programming languages. Some maintain
that pointers should not be allwoed, while others try to restrict their
use in a number of way. In this paper we try to justify our view that
pointers are a natural and useful way to teach beginners in Computer
Science to manipulate list structures, provided a group of strong
limitations is placed upon them. We define and give implementation model
of the use of pointers in SPL, a language to teach beginners disciplined
programming.
[MCC09/75]
FURTADO, A.L.; SCHWABE, D. An incremental extension for recursive programs
and structures in FORTRAN. 16 p. Eng. E-mail:
furtado@inf.puc-rio.br
Abstract: An extension to FORTRAN is proposed which is incremental in
the sense that it comprises three successive stages, each stage requiring
the availability of the lower ones. The three stages are: recursion,
LISP-like list processing, and run-time compilation of arithmetic
expressions that have been created and symbolically manipulated in list
representation. The purpose of the extension is to increase the power of
the language by making it suitable for application in areas where recursive
programs and structures are indicated. It is therefore an "orthogonal
extension", rather than a mere expansion of the syntax. Also, the
syntax itself has been augmented (never changed) as little as possible,
trying to find a compromise between the ease of extension and the desire
to conform to the original style of the language.
[MCC10/75]
SCHWABE, D.; LUCENA, C.J.P. Specification and uniform reference to data
structures in PL/I. 12 p. Eng. E-mail: dschwabe@inf.puc-rio.br
Abstract: Through the use of a modified concept of cluster, we
propose the association of the notions of abstract data types and
uniform reference to data structures to PL/I. The proposed programming
mechanisms enhance PL/I by the addition of two new linguistic
dimensions: a specification level and a common base language to handle
the implementation os data structures. This report informally describes
the syntax and semantics of the added constructs and gives an example of
their use.
[MCC11/75]
FURTADO, A.L. Semantic aspects of the relational model - a research
outline. 11 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: The relational data base model has been criticized on the
grounds that more emphasis should be given to "meaning" and that
relational languages are not what non-mathematical users would need.
On the other hand, the unrestricted use of natural language seems too
expensive, at the present stage, to be employed with commercial data
bases. A line of research is indicated, involving the determination of
a severely restricted subset of natural language, duly adapted to the
relational model, to be used as a means of communication with data bases.
[MCC12/75]
STAA, A.v. On the design of languages for a disciplined use of references.
10 p. Eng. E-mail: arndt@inf.puc-rio.br
Asbract: In this paper we study programming language design aspects with
the purpose of providing means for a disciplined use of references. This
objective is achieved through the introduction of the concept of values
of type type.
----------------------------------------------------------------------------------------------------------------------------------
1976
[MCC01/76]
MELO, R.N.; SCHWABE, D. Extending the control structures of FORTRAN via
a macro-generator. 13 p. Eng. E-mail: rubens@inf.puc-rio.br
Abstrac: A technique for extending programming languages via a general
purpose macro-generator is introduced. Particulary an implementation
of important control structured programming in FORTRAN and some text
substitution facilities are presented. The portability and case of
implementation issues are discussed as well as possibilities of
further extensions.
[MCC02/76]
KERSCHBERG, L.; PACHECO, J.E.S. A functional data base model. 24 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A functional model of data is presented as a labelled
pseudograph whose nodes are sets and whose arcs are total functions.
The model allows one to represent partial functions, binary relations,
n-ary relations, as well as m-ary associations among relations.
Injective functions play the role of cadidate keys. Graphs algorithms
transform the model into the relational DBTG/CODASYL, and entity set
models. Query schema are defined as queries in normal form and can be
specified via quantified semi-paths in the graph. A Query Schema Syntax
is proposed for query specifications.
[MCC03/76]
STAA, A.v. On monitoring the use of data. 14 p. Eng. E-mail:
arndt@inf.puc-rio.br
Abstract: The concept of monitoring the use of values of a given type
is introduced. Operation emulating functions are introduced as one of
the ways to permit monitoring. Demons, breakpoints and mousetraps are
defined and an implementation of these by means of operation emulating
functions is presented. More evidence is gathered showing that hardware
support is beneficial to implement these programming tools.
[MCC04/76]
STAA, A.v. Generator functions in modular programming. 17 p. Eng.
E-mail: arndt@inf.puc-rio.br
Abstract: Generator functions are defined as being functions which
allow sequential accesses to successive elements (values) in some
sequence (set). We study in this paper the basic characteristics of
generator functions as well as their implementation.
[MCC05/76]
LAUTERBACH, C.H.; STAA, A.v. On the tree organization of abstract
data types. 14 p. Eng. E-mail: arndt@inf.puc-rio.br
Abstract: The concept of an abstract type tree is presented. By means
of this tree a well defined mechanism to automatically perform type
conversions is presented. It is shown how the existence of this type
tree allows achieving data generality.
[MCC06/76]
FURTADO, A.L. Formal aspects of the relational model. 27 p. Eng.
E-mail: furtado@inf.puc-rio.br
Abstract: The relational model of data bases is studied from three
interdependent view points. Relational data bases are first modelled
by directed hypergraphs, a concept derived in a straightforward way
from Berge's hypergraph theory. Then the abstract directed hypergraphs
are interpreted using a linguistic model, and finally represented as
a necessary step towards computer implementation. The normalization
of relations is briefly discussed in the context of the three
approaches.
[MCC07/76]
FURTADO, A.L.; BRODIE, M.L. A data structure for fast relational
algebra operations. 20 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A logical design for the implementation of fast
relational algebra operations, in the context of a query -
oriented data base, is described. The logical data structure and the
algorithms are presented and evaluated.
[MCC08/76]
MELO, R.N. Suspension of JOBS in the IBM-1130. 11 p. Eng. E-mail:
rubens@inf.puc-rio.br
Abstract: A simple technique which permits the suspension of a running
program on a IBM-1130 for later resumption is presented. A slight
modification in a system routine is also shown which allows the
suspension of program which uses floating-point arithmetic. The
simplicity of the technique implies some restrictions but even so it
has proved to be very useful in at least one installation.
[MCC09/76]
MELO, R.N. Implementing character strings in FORTRAN. 20 p. Eng.
E-mail: rubens@inf.puc-rio.br
Abstract: A simple technique for representing and manipulating variable
character string is developed. Some algorithms for the main operations
are described in a structured language similar to a programming language.
A simple algorithm for collecting available space between strings is
proposed. A concrete example in FORTRAN is also presented.
[MCC10/76]
FURTADO, A.L.; KERSCHBERG, L. An algebra of quotient relations - (DRAFT).
23 P. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: An algebra which operates on partitioned relations is described.
It is shown that the proposed algebra is as powerful as the original
relational algebra, having the advantages of greater flexibility for
expressing queries in ways that are more straighforward and conducive
to a more efficient processing. The convenience of using the algebra
as an intermediate language is indicated.
[MCC11/76]
RUAS, V. Some results on the curved plate bending problem solved with
non-conforming finite elements. 23 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Convergence properties are studied for two non conforming
finite elements of degree two and three for the plate bending problem,
which were introduced respectively by MORLEY and FRAEIJS DE VEUBEKE.
Unlike some other non conforming elements, such as the so-called
Zienkiewicz triangle, they turn out to be very suitable for the case
of curved boundaries since success in the patch-test is guaranteed
without any restrictions on the shape of the plate. Furthermore, one
is allowed to suppose that no kind of curved elements are needed to
attain the same rates of convergence derived by LASCAUX & LESAINT for
the polygonal case, because of the low degree of the corresponding
space of polynomials. Two kind of support conditions are examined:
For the clamped plate, the above assuptions are verified for both
elements. This provides a simple alternative to avoid the complexity
involved in handling curved boundaries with standard conforming
elements. In the case of the simply supported plate, Morley's element
preserves the same convergence properties as in the polygonal case
without curved elements. For Fraeijs de Veubeke's triangle however
this is only possible with the use of second degree parabolas to
approximate the boundary. In addition to the above results, an
indication is given for the optimal choice of Poisson's coefficient
to be used in the variational formulation for clamped plates and
numerical examples are shown.
[MCC12/76]
BARROSO, P.B.; FURTADO, A.L. Implementing a data definition facility
driven by graph grammars. 20 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: The implementation of a data definition facility based on
graph transformations is discussed. The theory of graph grammars allows
a precise characterization of these transformations, facilitating proofs
of correctness. The implementation consists of an extension to PL/I,
and utilizes the standard PL/I.
[MCC13/76]
MAGALHAES, G.C.; FURTADO, A.L. A linear time sort algorithm applicable
to data base management. 16 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A sorting algorithm suitable for data base management
applications, especially with relational data bases, is described. It
is shown that it sorts a relation in time essentially linear in the
number of n-tuples in the relation. The assumed data structures are
described, as well as certain strategies for the convenient handling of
secondary storage.
[MCC14/76]
SCHWABE, D.; LUCENA. C.J.P. Design and implementation of a data
abstraction definition facility. 19 p. Eng. E-mail:
dschwabe@inf.puc-rio.br
Abstract: This paper describes the implementation model of a data
definition facility for abstract data types, implemented as an
extension to PL/I. The facility is based on a modified version of the
cluster mechanism for the implementation of types. The proposed version
tries to address the issues of efficiency and portability in connection
with the goal of systematic programming.
-----------------------------------------------------------------------------------------------------------------------------
1977
[MCC01/77]
GONNET, G.H. Average lower bounds for open-addressing hash - coding. 7 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: In this paper we derive average lower bounds on the, worst case and
average, number of accesses for open-addressing hashing tables. The average
worst case for full tables is found to be (formula) while for tables with an
occupation factor the lower bound when (formula). We find that an average lower
bound on the average number of accesses is 1.668... Simulation results indicate
that the worst case bounds are very tight.
[MCC02/77]
MELO, R.N.; SILVA, E.O. Especificação de informações para o projeto lógico de um
banco de dados. 33 p. Port. E-mail: rubens@inf.puc-rio.br
Abstract: An important aspect of the Data Base project is the specification and
analysis of its information contents. The purpose of this work is to suggest a
method to perform this specification. First, a specification of Data Base in
natural language is presented, and then corresponding specification in PSL is
showed. The specification is divided into two parts: static and dynamic. An
implementation corresponding to the specification is also presented.
[MCC03/77]
LUCENA, C.J.P.; DELAROLI, R.; SILVA, V.G. On the use of a problem statement
language in a software development environment. 13 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: This paper describes a methodology which enables an effective use of
the PSL/PSA system in a software development environment. A preliminary problem
statement notation is interposed between the user (system's programmer) and PSL.
A PSL problem statement can be systematically derived from this notation. The
work also addresses the issue of making a specialized use of PSL to guide the
production of a reliable implementation from the problem specification.
[MCC04/77]
FURTADO, A.L.; LUCENA, C.J.P. An incremental approach to the construction of
data base software. 14 p. Eng. E-mail:
furtado@inf.puc-rio.br
Abstract: A language design methodology is proposed for application in the
development of data base software. The methodology involves a three-level
approach and makes use of the cluster concept.
[MCC05/77]
FURTADO, A.L. Towards the design of data base interfaces for non-programmers. 10
p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A proposal for meeting the requirements of non-programmers, in the
areas of data base management systems, is presented. It attempts a compromise
between the freedom of natural language and the limitations imposed by
efficiency considerations, given the present state of the art.
[MCC06/77]
RUAS, V. Geração automática de malhas para resolução de problemas de contorno
bidimensionais pelo método dos elementos finitos. 23 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: A method for automatic generation of triangulations of curved or
polygonal two-dimensional domains, to be used when solving partial differential
equations with finite elements is introduced. Refinement of the mesh is simply
obtained by increasing the value of a positive integer parameter p. We prove
that, for starshaped domains whose boundaries do not have cusps, the
triangulation is regular in the following sense: there exists a strictly
positive constant c, independent of p, such that: (formula) where h is the
largest and the smallest side of a triangle of the
mesh. So, according to standard results, if the finite elements are suitably
chosen, convergence to the exact solution is provided as they become arbitratily
small. In addition, procedures for automatic numbering and calculation of the
coordinates of the vertices of the triangles are given.
[MCC07/77]
QUINTELLA, H.M.; SANTIMATEO, D.; PASCHOA, A. Computer kinetic modelling of
radionuclide accumulation in marine organisms. 13 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Continuous System Modelling Program (CSMP) is used to simulate the
first step of the Kinetic of a radionuclide in a food chain by using the
exponential model of accumulation from water-to-algae based on data found in the
literature. The use of computer modelling as a tool for environmental studies is
discussed as far as economical advantages and future applications are concerned.
[MCC08/77]
QUINTELLA, H.M.; SILVA, E.O.; SILVA, V.G. Estudos preliminares para
especificação e implementação de uma linguagem geral de simulação (LGS). 22 p.
Port. E-mail: bib-di@inf.puc-rio.br
Abstract: In this work we present a preliminary study done at the Dep. de
Informática PUC for the development of a general simulation language (LGS) that
almeted in the production of the just prototype. In the present phase we dealt
with GPSS-like characteristics that will be present in L.G.S. In particular we
studied: a) the possibility of improving some structures for transaction
manipulation by means of a simulation language base machine (LBM) that is the
abstract concept of chains. b) the definition of a model especification language
of a higher level than GPSS, utilizing Jensen and Wirth's form.
[MCC09/77]
CHALLIS, M.F. Integrity techniques in the Jackdaw database package. 15 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: The main body of this paper, Section II, is devoted to the description
of a general technique for ensuring the integrity of a database. This technique
has been successfully employed by the author in the Jackdaw database package,
and the first section provides a brief introduction to this system. Finally, in
section III, some further
applications of the technique in a multi-user environment are suggested.
[MCC10/77]
MAIBAUM, T.; LUCENA, C.J.P. Higher order data types. 36 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: We consider a generalization of the concept of abstract data type
suitable for modelling situations in which there is more than one level of
functionality. An instance of such a situation is the different in level of
functionality between the query and update functions in a data base. We
introduce the concept of a higher order data type to model this idea. The
underlying algebraic ideas are outlined and sample applications of the concept
presented.
[MCC11/77]
PASSOS, E.P.L. Efeitos de erros no cálculo de zeros de polinômios. 40 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstrac: The purpose of this paper is to make a study about Rounding Erros in
Computation and its effects in the zeros finds polinomials in Digital
Computation.
[MCC12/77]
VELOSO, P.A.S. Characterizing the regular prefix codes. 11 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: This paper gives an intrinsic characterization for the regular prefix
codes, analogous to the one of regular sets by regular expressions. Two new
binary operations on languages are introduced: "arrow" (related to star and
concatenation) and "prefix-union", and the class of prefix codes is shown to be
closed under these operations. A regular prefix code is expressed in terms of
these operations, concatenation and single-word languages, by using the form of
its minimal finite automaton.
[MCC13/77]
PEREDA BORQUEZ, A.; CARVALHO, R.L. A short introduction to the Lambda-Alfa-Beta-n
calculus with applications (first draft). 26 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The basic concepts of the Lambda calculus are defined. Two
applications in the area of programming languages semantics are presented.
[MCC14/77]
MELO, R.N.; LELLIS, L. O mapeamento da especificacao conceitual em banco de
dados gerenciado pelo TOTAL. 23 p. Port. E-mail: rubens@inf.puc-rio.br
Abstract: The object of this paper is to propose an approach to obtain the
internal schema of the data base of a system which has been conceptually
specified in PSL using the TOTAL DBMS. First, the basic ideas of the conceptual
specification of an information system are presented. Then the relevant
characteristics of the TOTAL system are described and finally a method is
suggested to map a conceptual specification of the system's data base to an
internal schema using TOTAL.
[MCC15/77]
GOTLIEB, C.C.; FURTADO, A.L. Data schemata based on directed graphs.
67 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: Rooted, labelled, directed graphs (RLD's) are taken as the
basic for describing data structures. A constructive formalism is set
up to describe RLD's, generate them by means of grammars, and
carry out such operations as accessing nodes, inserting and deleting
data items, and recognizing graph patterns. It is show how the
formalism can be translated into languages for data definition and
data manipulation, of the type associated with data base systems. The
availability of the formalism allows a systematic development of
such languages, and provides a method of incorporaring consistency
preconditions to structural operations and proving correctness of the
data structures which arise in using such languages.
[MCC16/77]
STAA, A.v. Especificacao do projeto COMCOM2. 11 p. Port. E-mail:
arndt@inf.puc-rio.br
Abstract: The compiler and/or pre-processor writing system COMCOM2
is described. The hardware and software environment for this system
is caracterized. The documentation, programming and test standards
are specified.
[MCC17/77]
CARVALHO, R.L.; FURTADO, A.L.; PEREDA BORQUEZ, A. A relational model
towards the synthesis of data structures. 25 p. Eng. E-mail:
furtado@inf.puc-rio.br
Abstract: Data structures are defined by means of relations, and the
allowable operations on them are expressed in terms of a few
"well-structured" primitive operations.
[MCC18/77]
SILVEIRA, A.M.; LUCENA, C.J.P. Geracao de dados de teste baseada nos
aspectos estruturais de programas. 28 p. Port. E-mail:
lucena@inf.puc-rio.br
Abstract: In this paper we discuss the difficulties met in the
process of generating test data and current research in this area.
One methodology of test data generation is proposed based on the
structural aspects of programs. This metholology shows that the
problems of nontraversable paths and arrays are solved when we
symbolically execute a program by forward substitution. With the
proposed method the detection of nontraversable paths occurs when
we meet a pair of inconsistent restrictions during a symbolic
execution of a program path.
[MCC19/77]
GONNET, G.H.; ROGERS, L.D. An algorithmic and complexity analysis of
the heap as a data structure. 44 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: A heap is defined as a class of data structures used to
represent a partialy ordered set of data from which we can repeatedly
and efficiently extract the maximum (or minimum) element. The
definition of the class covers heaps of integer as well as real branch
factor. We define and describe the basic operations on a heap and evalue
the running times of various algorithms to perform these operations. The
complexity of a heap is defined in a way that proves to be a useful
tool for evaluation of running times. We give, in detail, an average
case analysis of these algorithms as well as considering the worst case.
A relation between probabilistic models of heap is given and various
comparisons of the running times are presented for the most common heap
structures. In addition we consider some less common heap structures
and describe one heap which resambles the tournament selection process.
[MCC20/77]
CASTILHO, R.T.L. Pesquisas em andamento em Ciência da Computação. 68 p.
Port. E-mail: bib-di@inf.puc-rio.br
Abstract: Resumos das pesquisas em processo em Ciência da Computação,
realizadas por professores e alunos do Departamento de Informática da PUC/RJ,
apresentadas por ocasião da 1a. Conferência do Departamento de Informatica, 9-11
de setembro de 1977, Mendes, RJ.
[MCC21/77]
GONNET, G.H.; ROGERS, L.D. The interpolation-sequential search
algorithms. 5 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The interpolation sequential search algorithm is an
algorithm to search ordered tables using implicit information about
the distribution of the keys. It performs one probe based on an
interpolation formula and then searches sequentially towards the
appropriate end of the table. It is shown that under a model of random
keys, the average number of accesses needed for the successful search
is (formula). The analysis is extended to the same search applied to
blocked external files.
[MCC22/77]
GONNET, G.H. Expected longest probe sequence in hash code searching.
16 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: We define the expected longest probe sequence, an expeded
worst case, of a hash table as the expected value of the maximum
number of accesses needed to locate any element in a random file. This
differs from the usual definition of worst case which, in the case of
hashing, is the longest sequence of accesses for the worst file. We
find asymptotic expressions of these expected values for full and
partially filled tables. For the open addressing scheme with a
clustering-free model we find these values to be (formula), where n
is the number of records, m is the size of the table, and (formula).
For the open addressing scheme reordering the insertion such that we
minimize the worst case, under a random probing model, we find the
tight lower bounds (formula) respectively. Finally for the separate
chaining (or direct chaining) method we find both expected values
to be (formula). These results show that generally the actual
behaviour of the worst case in hash tables is on average quite good.
[MCC23/77]
GONNET, G.H. Notes on the derivation of asymptotic expressions from
summations. 13 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstraction: This paper contains mathematical tools for the derivation
of asymptotic expressions from summations. The first is a generalized
form of the Euler-Maclaurin summations formula that proves very effective
in the evaluation of the constant term. The second is the application of
functional equations. Both methods are illustrated with several examples
taken from the complexity analysis literature.
[MCC24/77]
CHAHON, J.A.; MENDES, J.A.F.; SOLEY, N. Fatores humanos na programação.
21 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: Human factors involved in the programming activity are
considered, with a special emphasis on aspects often disregarded both
in the literature and in the practical world.
[MCC25/77]
LUCENA, C.J.P.; PEQUENO, T.H.C. A view of the program derivation
process based on incompletely defined data types: a case study. 20 p.
Eng. E-mail: lucena@inf.puc-rio.br
Abstract: The present paper discusses some issues in program synthesis
by relating the idea of systematic program derivation with the concepts
of data type and correctness of data representation. The notion of an
incomplete definition of a data type at a high level of abstraction is
introduced. The ideas are illustrated through an example previously
discussed in the literature by D. Gries.
[MCC26/77]
SEVCIK, K.C.; FURTADO, A.L. Complete and compatible sets of update
operations. 22 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: We examine the problem of defining data base updates on user
views so that all anticipated enterprise activities can be represented
in the data base, but that certain declared constraints, which delimit
the set of acceptable data base states, are preserved. In order to
verify that a set of operations on views meets these criteria, it is
necessary to consider the interactions of all users. Some updates must
have side-effects not observable by the user requesting the update
in order to preserve certain constraints.
[Fasc.Esp].
CASTILHO, R.T.L. "Software de apoio para o desenvolvimento de sistemas de
informacão" e "Solução numérica de equações diferenciais"; Relatório dos
projetos de pesquisa: I. 47 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: Progress report of research projects being
conducted by professors Carlos Lucena and Michael Stanton, at the Departamento
de Informática, PUC-Rio, under the sponsorship of CNPq.
-------------------------------------------------------------------------------------------------------------------------------------
1978
[MCC01/78]
GOTLIEB, C.C. Programs for Data Processing and Computer Science in
two-years colleges. 34 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This report examines the two-years program in Computer Science
("Project 15") in Brazil and its counterpart in Canada.
[MCC02/78]
FURTADO, A.L.; SEVCIK, K.C. Permitting updates through views of data
bases. 44 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: Providing different views (logical images of the structure
of a data base) to various users creates the problem of determining
how update operations expressed in terms of the views should affect
the stored form of the data base. For data bases with a relational
organization, we indicate the effects of a wide range of update
operation on views. We conclude that some operations must be
prohibited in order to assure harmonious interactions among data base
users, but that many other operations can be allowed even through the
structure of the view may differ substantially from the actual
structure of the data base. We consider views not only as "windows"
through which to see a data base in a particular way, but also as
"shades" to conceal and protect information, and as "screens" to
intercept any update operations that could leave the stored form of
the data base in an unacceptable state.
[MCC03/78]
FURTADO, A.L. A view construct for the specification of external schemas.
31 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A view construct is proposed which consists of a derived
relation and the operations defined on it. Attention is focussed on the
update operations, for which the conditions, effects, and side effects
must be specified. In order to guarantee that constraints are preserved,
it is proposed that all sets of views, constituting the external schema
of each user or class of users, be specified (and revised when needed)
together, by the enterprise administrator in consultation with the
application administrators. A simple data base environment is described
and used to illustrate the suggested approach.
[MCC04/78]
VELOSO, P.A.S. Characterizations for the regular prefix codes and related
families. 18 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Intrinsic characterizations by means of analogues of regular
expressions are given for six families of regular languages related to the
prefix codes, namely their reversals and their closure under union, the
right and left ideals and their complements. First, a characterization for
the regular prefix codes is obtained, which is then used to characterize
the other families. Characterizations by finite automata also presented.
[MCC05/78]
TOMPA, F.W. A practical example of the specification of abstract data
types. 36 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The algebra of quotient relations, a relationally complete
set of operations data base applications, is formally defined in terms
of the algebraic specification technique. The process of constructing
an algebraic specification for data type is described in order that
future formal definitions are more easely derived. Several improvements
to current algebraic presentation techniques are also introduced.
[MCC06/78]
CHALLIS, M.F. Database consistency and integrity in a multi-user
environment. 39 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This monograph discusses the problems of data base consistency
and integrity in a multi-user environment and presents a solution based
on the ability of one physical data file to represent several similar
"instances" of a data base at the same time. This technique has been
successfully used by the author to provide integrity in a single-user
environment for the JACKDAW data base package.
[MCC07/78]
GONNET, G.H. Open addressing hashing with unequal-probability keys.
14 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The analysis of hashing algorithms is usually done under the
assumption that all keys are equally likely to be accessed. In practice,
this is generally not true and since most probable keys tend to appear
first during table creation, our estimates are pessimistic. We compute the
resulting expected number of accessed in a model of open-addressing hashing
for several key distributions. The results presented here correspond to
tables that were created inserting keys with decreasing probability, i.e.
the optimal ordering when we do not know the specific hashing function. For
several distributions we find a significant reduction in the average number
of accesses, mainly for full tables where even the order may be better.
[MCC08/78]
QUINTELLA, H.M.; KOELSCH, W.C.; GOMES, M.C.L. Estudo comparativo da
aplicação de linguagens de simulação em sistema de filas. 18 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstract: In this work a simple model of queue and service station
implemented in GPSS, SIMSCRIPT, GASP and LGS is studied in terms of the
programming structures that were utilized in each model and in terms of
the statistical analysis of the results obtained. This work has two
objectives: a) as a tutorial it documents in detail (for use in class)
an example in four simulation languages used in this university. b)
as a report it partially documents initial experiments with the first
LGS prototype.
[MCC09/78]
BOLCH, G.R.H. A heavy traffic model of a multiprogramming system.
24 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In the present paper we consider an analytical queueing
network model of a multiprogramming system with symmetric processor,
several peripheral devices and an abstraviles distributed number of
programs in the system. In order to find a simple model for this
system we assume that the processor are always ackive and with this
"heavy traffic assumption". We obtain a much simple model than the
models which are derived with the wellknown methods of Gordon/Newell and Busen. We also give a relation to check whether the
heavy traffic condition is satisfied.
[MCC10/78]
MELO, R.N. A arquitetura do REDAS (um sistema de gerência de banco
de dados). 20 p. Port. E-mail: rubens@inf.puc-rio.br
Abstract: REDAS is a database management system based on an
entity-relationship model. This paper surveys the
main aspects of the architecture of the system. Many of the concepts
and terms employed come from the recommendations of the ANSI/SPARC
report. The languages provided by the system are introduced. The
implementation details are not shown in this paper.
[MCC11/78]
FURTADO, A.L.; STAA, A.v. Diretório de dados: utilidade e especificação.
19 p. Port. E-mail: furtado@inf.puc-rio.br
Abstract: Data is a valuable resource. The value of data increases as
its quality improves, as it becomes more meaningful to its end user,
and as it becomes easier to more it between different systems. In
this text we discuss what a Data Directory is and how it contributes
to the increase in value of data.
[MCC12/78]
ARSAC, J.J. A puzzle. 9 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The use of some programming techniques is illustrated by
the development of a program to solve a puzzle. The method used
consists of getting an initial solution (a recursice one in the
present case) and applying some transformations to the program
to improve the solution according to a given goal. Program
transformations seem to be a major way to reduce the role of
invention in programming.
[MCC13/78]
STEINBRUCH, P.L.; MELO, R.N. Normas de programação e documentação:
versão 1. 1 v. Port. E-mail: rubens@inf.puc-rio.br
Abstract: This work establishes guides to be used in the programming
and documentation activities of the project: "Tools for the Design
and Implementation of Information Systems Suported by Data Bases".
The progamming language mainly utilized in this project is FOURTRAN
therefore most guides in this manual are Fourtran-oriented.
Nevertheless it is clained that the manual may be useful with minor
adaptations even if some other languages is used. First some concepts
regarding structured programming and modular programming. Are
introduced. Then guides for the documentation of activities and
programs are presented. Finally in the apendices the lay out of the
used forms are showed.
[MCC14/78]
PEQUENO, T.H.C.; LUCENA, C.J.P. An approach for data type specification
and its use in program verification. 14 p. Eng. E-mail:
lucena@inf.puc-rio.br
Abstract: This work presents an approach for the specification of data
types and data representation. The approach was motivated by the problem
of verifying programs that handle abstract data types. The ideas are
presented in this paper through the specification and analysis of a
sorting program.
[MCC15/78]
CARVALHO, R.L.; PASSOS, E.P.L.; PEIXOTO, S.R.G. Communication
predicates: a complete strategy for resolution-based theorem provers -
an evaluation of an implementation. 14 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: A new and complete strategy for resolution-based theorem
provers for first order logic is presented. This strategy is a
central result. The strategy extends Bledsoe's splitting
technique which consists of the replacement of a set (formula) of
clauses by two sets (formulas) of clauses. We extend it in the
following senses: a - it enlarges the range of applications by
allowing to split sets of clauses, and; b - it allows the occurrance
of common variables in the split parts. The new strategy is
implemented and is presented from practical point of view. The
examples illustrating the effects of the strategy are discussed.
[MCC16/78]
PASSOS, S.M.; VASQUES, R.P. O suporte básico do sistema de HYADES de
gerência de banco de dados. Vol. 1: O pacote de gerência de banco de
dados (parte 2); Vol. 2: O pacote de avaliação de eficiência. 1 v.
Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This work is a System of Performance Evaluation (SAE) of a
System of Data Base (SBD). The analysis of the results get of SAE gives
to the users elements that allow to adapt the SBD to his necessities
and to get a grather eficiency; this analysis also gives us a support
to modification into versions futures of SBD. This SAE is a system
defined specifically about the SBD, which is the work of tese of Roberto
Pires Vasques and was presented at same time of this work.
[MCC17/78]
CHALLIS, M.F. Jackdaw II - Preliminary specification; part 2: Structural
description. 31 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This monograph forms part of the preliminary definition of
the Jackdaw II data base package (see the preface). It describes the
facilities provides for the representation of data and data relationships
in data base, and the 'access paths' which may be followed to retrieve
items stored within it.
[MCC18/78]
CHALLIS, M.F. Jackdaw II - Preliminary specification; part 3: the
definition language. 45 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This monograph forms part of the preliminary definition of
the Jackdaw II data base package (see the preface). It contains a
formal description of the language used to define the structure of a
data base (often called the 'DDL'). This language also includes
facilities for modifying the structure of an exixting data base.
[MCC19/78]
MELO, R.N.; STEINBRUCH, P. FORTS: um preprocessador para FORTRAN-IV
estruturado. 32 p. Port. E-mail: rubens@inf.puc-rio.br
Abstract: FORTS (Structured FORTRAN) was developed at PUCRJ from
a general purpose macro-generator. This extention to FORTRAN-IV
permits the development of programs according to the concepts of
structured programming. This report overviews the FORTS facilities
and may be used as a "User's Guide" of the system.
--------------------------------------------------------------------------------------------------------------------------------
1979
[MCC01/79]
AKONTEH, A.N. Microprogramming part 0: Theoretical evolution of the
microprogram concept. 13 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This is part 0 of a series on microprograming. It developes
basic concepts and the mathematical representation of each stage in
the evolution of microprogramming.
[MCC02/79]
BOLCH, G.R.H. Upper and lower bounds for the waiting time in the M/M/m
and M/G/m queueing systems. 18 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In the modelling of computer systems the waiting time in
M/M/m and M/G/m queueing is a very important variable. There exists
a formula for the waiting time in M/M/m queueing systems. But this
formula is very complex compared with the formula for a M/M/1 queueing
system. For M/G/m queueing systems there exists no formula for the
waiting time. In this case one can only approximate the waiting time
by using the M/M/m formula or the existing formulae for the upper and
the lower bounds of the waiting time in G/G/m queueing systems. In the
first part of the paper formulae for an upper and a lower bound are
developed and from those approximate formula for the waiting time in
M/M/m queueing systems is derived. These formulae are not more
complicated than the M/M/1 waiting time formula. These results are
extended to the M/G/m queueing system in the second part. It is shown
that these are much better than the results by an M/M/m approximation
and that the new bounds are within the known bounds for G/G/m queueing
systems.
[MCC03/79]
MENASCÉ, D.A. Selective reloading of very large databases. 11 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: The property of a database management system to recover from
failures and maintain the database integrity is extremely important.
Some types of failures, like media failures, require that the database
be reloaded from a previously saved copy or dump. This operation may be
extremely time consuming for very large databases. This paper presents a
technique by which it is not necessary to reload the whole database but
only portions of it. These portions must be carefully selected so as not
to destroy the semantic integrity of the database. This technique is
based on a general formal model of crash recovery developed by the author. An implementation for the recovery model is also given
here.
[MCC04/79]
AKONTEH, A.N. Microprogramming: principles and developments.
19 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This is Part I of a series on Microprogramming. This part
analysis developments in microprogramming from Wilkes (1951) through
its commercial application by IBM (1964) to today. It recognizes the
software/hardware duality and shows microprogramming as a tradeoff
that offers an alternate and efficient level of program implementation.
The rest of the study analysis the basic micro-instruction design,
encoding, implementation and timing.
[MCC05/79]
AKONTEH, A.N. Microprogramming part II: developments in
microprogramming languages. 9 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This study, part II of a series on microprogramming,
reviews some of the difficulties in the development of Higher Level
Microprogramming Languages (HLML) and how some of these difficulties
have been resolved. It concludes that the difficulties of HLML
design are partly due to lack of participation of language designers
in the hardware design.
[MCC06/79]
AKONTEH, A.N. Microprogramming part III: trends in emulation
technology. 23 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This Part III of a series on Microprogramming focuses on
trends in emulation technology. The study develops a formal
representation of an emulation environment and defines an emulator
in terms of a transformation process (formula) equivalent to an
environment (formula) created by imbedding the state image of a
target machine y into a host machine x. A performance index
(formula) of the emulator is developed to indicate its relative
versatility. The rest of the study analyses the static and dynamic
process of emulation and trends in emulation technology characterised
by developments in semiconductor technology that have made possible
the application of processor-memory-switch concepts in emulation.
[MCC07/79]
MELO, R.N.; LELLIS, L. O mapeamento da especificação conceitual em
banco de dados gerenciado pelo ADABAS. 22 p. Port. E-mail:
rubens@inf.puc-rio.br
Abstract: The objective is to devise a methodology for the mapping
from the conceptual specification of a data base to an internal
schema at the level of the usual commercial DBMS. This is one of a
series of similar works which deals with such a problem and considers
in this case the ADABAS system. First the basic ideas of conceptual
specification of information systems and a language for the conceptual
specification of data bases are introduced. Then, some main
characteristics of ADABAS are surveyed, and finally a mapping from the
conceptual specification to an internal schema expressed in terms of
ADABAS structures is proposed.
[MCC08/79]
MENASCÉ, D.A.; MONTEIRO, M.A. On the problem of capacity assignment
in computer networks which carry messages with different priorities.
19 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper deals with the problem of optimal capacity
assignment in computer networks which carry messages of different
priorities. Given that it is not possible to obtain a closed form
analytical solution to this problem, the paper presents an algorithm,
which uses heuristic techniques, in order to obtain suboptimal
solutions to the problem. It is shown here how to derive the average
delay, Tp, experienced by a message of priority p. The paper concludes
with the presentation of several numerical examples of the utilization
of the algorithm, as well as an evaluation of the effectiveness of the
proposed heuristic techniques.
[MCC09/79]
STAA, A.v. Desenvolvimento estruturado de sistemas automatizados.
73 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: The problems related to the development of automated
systems are examined. The study is conduced observing always the
whole development problem, without considering details such as
methods and techniques for planning, economic analysis, specification,
construction, test and operation. Quality and utility attributes,
software profitability and development conditions are described.
Also a software system life cycle is described, where objectives and
products per phase are specified.
[MCC10/79]
VELOSO, P.A.S.; PEQUENO, T.H.C. Don't write more axioms than you
have to: a methodology for the complete and correct specification
of abstract data types; with examples. 29 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: A data type can be formally specified by a set of correct
axioms that is sufficient to completely characterize it. This paper
presents a methodology that indicates what axioms to write and when
to stop writing them. Some data types are specified to illustrate the
application of the method, which is based on the concept of cannonical
term algebra.
[MCC11/79]
RUAS, V. A direct method for solving two-dimensional one phase
Stefan problem. 21 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A new algorithm is proposed for solving the Stefan problem
for the case when the initial region occupied by the medium in a given
phase is a starshaped two-dimensional domain. The evolution of this
region as time increases is determined by plotting the free boundary
directly. At each time step this is approximated by a polygon in the
interior of which the heat equation is solved with piecewise linear
infinite elements. Numerical experiments indicate that the method is
stable and that the convergence is to be expected, under suitable
assumptions on the regularity of both the boundary and initial data
of the problem.
[MCC12/79]
CARVALHO, R.L.; PASSOS, E.P.L.; LANZELOTTI, R. MTD-conversational
system oriented for topology. p. Eng. E-mail:
bib-di@inf.puc-rio.br (report
not available)
Abstract: abstract not provided.
[Fac.Esp]
RUAS, V. Introdução aos problemas variacionais. 129 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: Variational methods have grown in importance in the last decade, by
introducing powerful techniques to the the numerical solution of the so called
variational problems. This text aims at providing essential notions on the
appropriate handle of variational problems to those who gather some expertise on
the basic concepts of functional analysis.
[Fac.Esp]
NAKANISHI, T.; RUAS, V. Elementos de análise funcional aplicada. 150 p.
Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This work aims at presenting, briefly and objectively, basic concepts of applied functional analysis.
------------------------------------------------------------------------------------------------------------------------------------
1980
[MCC01/80]
HONIG, G.; HIRDES, U. A method for the numerical inversion of Laplace
transforms. 28 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A method for the Numerical Inversion of Laplace Transforms.
In this paper a numerical inversion method for Laplace transforms,
based on a Fourier series expansion developed by Durbin (1973), is
presented. The disadventage of the inversion methods of that type,
the encountered dependence of discretization and truncation error
on the free parameters, is removed by the simultaneous application
of a procedure for the reduction of the discretization error, a method
for accelerating the convergence of the Fourier series and a procedure
that computes approximately the 'best' choice of the free parameters.
Suitable for a given problem, the inversion method allows the adequate
application of these procedures. Therefore, in a big range of
applications a high accuracy can be achieved with only a few function
evaluations of the Laplace transform. The inversion method is implemented
as a FORTRAN subroutine.
[MCC02/80]
(distrib. 1979)
FURTADO, A.L.; SANTOS, C.S. Synthesis of update transactions.
(also Technical Report DB107901).
Eng. E-mail: furtado@inf.puc-rio.br
(report not available)
Abstract: abstract not provided.
[MCC03/80]
MENASCÉ, D.A.; NAKANISHI, T. Optimistic versus pessimistic concurrency
control mechanisms in database management systems. 19 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: This paper presents a performance evaluation of locking oriented and
conflict oriented concurrency control mechanisms. Analytical models as well
simulation models are used to obtain the average response time of transactions
under both types of mechanisms.
[MCC04/80]
MENASCÉ, D.A.; LANDES, O.E. On the design of a reliable storage component
for distributed database management systems. 36 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: This paper describes an experience of integrating several
independently proposed ideas and crash recovery techniques into the design of a
robust storage component of a distributed data base management system (DBMS),
proved to be a non trivial task. The result is an integrated design which can
lead to a direct implementation.
[MCC05/80]
LANDES, O.E.; MENASCE, D.A. Um estudo sobre técnicas de recuperação
de erros em banco de dados. 33 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This work is a survey of several different techniques used
for crash recovery purposes in modern database management systems and
file systems. These techniques restore the DB to a consistent state
after a failure occurs. Different recovery mechanisms have to be
used for different kinds of failures - transaction, system and
secondary storage failures. These techniques also differ with respect
to the state of integrity of the DB after the occurrence of a crash.
Some of them are fault tolerant, others restore the DB to any previous
consistent state, and others restore the DB to the most recent consistent
state. Finally, we present some techniques which consider the transaction
as the unit of recovery and consistency and implement the atomic
("all or none") property for transaction.
[MCC06/80](distrib. 1979)
FURTADO, A.L.; MAIBAUM, T.S.E.; SANTOS, C.S. A uniform logical treatment
of queries and updates. Eng. E-mail: furtado@inf.puc-rio.br
(report not available)
Abstract: abstract not provided.
[MCC07/80]
LOBEL, R.E.; MELO, R.N. Um estudo de sistemas de dicionário de dados.
34 p. Eng. E-mail: rubens@inf.puc-rio.br
Abstract: Recently Data Dictionary Systems (DDSs) have increased in
relevance as a tool for analysis, design, implementation and maintenance
of enterprizes information systems. The currently available DDSs do not
have common terminology and characteristics and as a result their
comparison becomes difficult. This work presents the basic concepts of
DDSs, comments on their use as a Data Administration tool and introduces
a standard terminology that permits a comparison and a compilation of the
main characteristics of some of the commercially available systems.
[MCC08/80]
CASTILHO, J.M.V.; FURTADO, A.L.; VELOSO, P.A.S. Algebraic specification
of data base applications. 13 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: With the algebraic approach to abstract data types, data base
applications can be formally specified, by describing the interactions
among opreations meaningful to the application area specialists. The
original specification covers the behavioural aspects of data base
application, and also, in a provisional way, other aspects such as
accessibility, usage interface and representation. At later stages,
the last three aspects are decoupled and refined, giving origin to a
modular architecture. The modules provide set-structured access path,
interfaces for different classes of users, and representation by a
version of the entity-relationship data model. All modules are
expressed in a procedural style of algebraic presentation, which is
easy to translate into some symbol-manipulation language (SNOBOL,
icon, LISP, etc.). This leads to early testing and experimental
usage, in addition to verifications of correctness.
---------------------------------------------------------------------------------------------------------------------------
1981
[MCC01/81]
REMY, J.L.; VELOSO, P.A.S. Comparing abstract data type specifications
via their normal forms. 21 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A simple technique is presented for verifying that two
abstract data type specificatons are equivalent in that they have
isomorphic initial algebras. The method uses normal forms to
attemp reducing the number of equations to be checked. It is
applied to a simple example and some extensions and related
problems are also discussed.
[MCC02/81]
CASANOVA, M.A.; BERNSTEIN, P.A. On the construction of database
schedulers based on conflict-preserving serializability. 44 p.
Eng. E-mail: casanova@inf.puc-rio.br
Abstract: This paper discusses solutions to the concurrency
control problem for databases systems using a method called
conflict-preserving serializability, an approach significantly
different from conventional locking methods. The major results
of the paper spell out how to implement such a method within
practical space bounds. They are applied to the construction of
schedulers for centralized, as well as distributed database
systems.
[MCC03/81]
CASANOVA, M.A. The theory of functional and subset dependencies over
relational expressions. 31 p. Eng. E-mail: casanova@inf.puc-rio.br
Abstract: A formal system for reasoning about fuctional dependencies
(FDs) and subset dependencies (SDs) defined over relational expressions
is described. An FD (formula) indicates that Y is functionally
dependent on X in the relation denoted by expression e; an SD (formula)
indicates that the relation denoted by e is a subset of that denoted
by f. The system is shown to be sound and complete by resorting to the
analytic tableaux method. Applications of the system include the problem
of determining if a constraint of a subschema is implied by the
constraints of the base schema and the development of database design
methodologies similar to normalization.
[MCC04/81]
FURTADO, A.L.; VELOSO, P.A.S.; CASTILHO, J.M.V. Verification and
testing of simple entity-relationship representations. 26 p. Eng.
E-mail: furtado@inf.puc-rio.br
Abstract: A methodology is proposed for representing a data base
application on a simple entity-relationship data model, based on
formally specifying both as abstract data types. This methodology
includes the verification and testing of the representation,
which are simplified by the usage of procedural specifications. An
example data base application is used to illustrate the general
discussion.
[MCC05/81]
MENASCE, D.A.; ALMEIDA, V.A.F. A multiclass queueing network model
of computer systems with variable degree of multiprogramming. 38 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Current closed queueing network models suffer from a severe
limitation since they require that the number of jobs in the system
be fixed. However, in actual systems, the number of jobs multiprogrammed
in each job class is not fixed but varies dinamically depending on the
nature of the class and on the amount of memory available for each class.
This paper presents the solution of a multiclass queueing network model
in which the number of jobs of a given class is not fixed but varies
within a given range.
[MCC06/81]
FURTADO, A.L.; MAIBAUM, T.S.E. An informal approach to formal
specifications. 21 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: abstract not provided
[MCC07/81]
VELOSO, P.A.S. Methodical specification of abstract data types via
rewriting systems. 41 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A data type is often given by an informal model. Its formal
specification is an important task, but also difficult and error-prone.
Here a methodology for this task is presented. Its steps are, first,
the election of a canonical form defining a canonical term algebra;
second, a system of sound rewriting rules powerful enough to achieve
the syntactical transformations of the canonical term algebra. The
final translation of rewriting rules into equations is immediate.
The methodology is illustrated by the detailed presentation of a
simple example.
[MCC08/81]
FURTADO, A.L.; VELOSO, P.A.S. On multi-level specifications based
on traces. 34 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A methodology for the formal specification of data base
application is presented. Data base states are denoted by the
traces of the update operations invoked. Using the knowledge of
preconditions and effects of updates, procedures working on traces
are designed to specify each update and query operation. By starting
with the full traces, and then passing to modified traces, successive
specifications are derived until a level corresponding to canonical
terms is reached. At each level one has theb symbolic execution
capability, fundamental for the early usage and testing of
specifications. The relationships between these specifications and
those based on equations are examined.
[MCC09/81]
MENDES, I.A. Redes de computadores: protocolos na rede de comunicações
de dados. 94 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: Computer networks are being developed or designed by many
countries, including Brazil, using the packet switching technology as
a means of communication between computers and/or terminals. These
networks use a hierarchy of protocols keeping in lower levels the
protocols that there are inside the data communication network.
These protocols are responsible for the accuracy and reliability
in transfering data between source and destination switching nodes.
To provide this facility, this level of hierarchy uses inter nodes
trunks allied to a routing strategy and an end-to-end procedure
between source-node and destination-node. This assures that packet
sequencing is preserved and carries out the flow control in the
network. Starting from the detailed description of what a protocol
is like and which functions it executes to assure the data
exchangeability, between processes that implement it, in an orderly
manner, this work intends to identify, define and specify the
protocols that will establish the transmission layer: the data
communication network - RECOMDOS, that is used as a means of
communication in computer networks. As protocols, routing techniques
and other internal controls of RECOMDOS are invisible to network
users, one intends to generate, as one of the aims a broad didactic
text about the subject issued, apart from an formal specification
of protocols identified, using a protocol specification language
called APSL.
[MCC10/81]
NAKANISHI T.; MENASCE, D.A. Correctness and performance evaluation
of a two-phase commit based protocol for DDBs. 52 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: Many concurrency control algorithms for distributed
database management systems have been proposed in the last few years,
but little has been done to analyze their performance. This paper
presents the specification of a concurrency control algorithm based
on the two-phase commit protocol for DDBs. A correctness proof of the
algorithm as well as a complete performance analysis is included.
[MCC11/81]
CASANOVA, M.A.; CASTILHO, J.M.V.; FURTADO, A.L. Properties of
conceptual and external database schemas. 31 p. Eng. E-mail:
casanova@inf.puc-rio.br
Abstract: The correctness of the design of a database application
is characterized by identifying groups of properties that the
conceptual schema and the external schemas must satisfy. Each
property is then formalized, with certain restrictions, using
first-order logic, dynamic logic or modal logic. The relational
model of data is used throughout the development.
[MCC12/81]
CASANOVA, M.A. A theory of data dependencies over relational
expressions. 60 p. Eng. E-mail: casanova@inf.puc-rio.br
Abstract: A formal system for reasoning about implicational
dependencies over relational expressions (IDEXs) is first
described. The System is shown to be sound and complete by
resorting to the analytic tableaux method. Then, a class of
IDEXs is exhibited whose inference problem is solvable by
the method.
[MCC13/81]
FURTADO, A.L. Horizontal decomposition to improve a non-BCNF scheme.
4 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: Whenever in a non-BCNF scheme a set of non-key attributes
determines part of a key, a problem arises: decomposition eliminates
anomalies but causes the loss of a dependency. The paper suggests
horizontal decomposition as a way to obtain an improved schema.
[MCC14/81]
SANTOS, C.S.; MAIBAUM, T.S.E.; FURTADO, A.L. Conceptual modelling
of data base operations. 17 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A formalism adequate for the specification of behavioral
properties of data bases is proposed. The formalism is a many-sorted
first-order predicate calculus, including a formalized notion of data
base state. Both update and query requests are modelled through
expressions by the use of predicates supplied in the language of the
formal system, and are treated uniformly as a theorem proving process.
The process consists of using the axioms defining the data base for
either synthesizing a valid sequence of update operations (if such
exists) or for answering the query.
[MCC15/81]
ANDRADE, D.A.; VERAS, A.F.; MELO, R.N. Um estudo comparativo de
metodologias de programação. 102 p. Port. E-mail:
rubens@inf.puc-rio.br
Abstract: This work makes a brief presentation of the main Program
Design and Implementation techniques which have been recently proposed
in the literature. The methods are also analysed and compared based on
some desirable aspects for a good methodology.
[MCC16/81]
CASTILHO, R.T.L. Catálogo de teses e dissertações do Departamento de
Informática da PUC/RJ 1969-1981. 102 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: Catalogue of thesis and dissertations presented to the Departamento de
Informática of PUC/RJ, 1969-1981.
[Fac.Esp]
STAA, A.v. LASO - Laboratório de Software. 24 p. Port.
E-mail: bib-di@inf.puc-rio.br.
Abstract: Describes the design of LASO, the sofware laboratory of Departamento de informática or PUC/RJ. Emphasys is given to its research and development directions, as a means of coordinating and agglutinating the research activities in the Department
-------------------------------------------------------------------------------------------------------------------------------
1982
[MCC01/82]
ALBRECHT, P. Métodos iterativos para sistemas lineares e sua aplicação
na solução de equações diferenciais parciais. 104 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: This text gives a reasonably complete introduction to
classical iteration methods for linear algebraic systems and theirapplication to
certain partial differential equation problems. The aim was to collect the
relevant material in easily accessible form and, in the last chapter, to present
new results with possibilities for further research.
[MCC02/82]
CASTILHO, R.T.L. Catálogo das publicações do Departamento de Informática
1968-1982. 114 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: Catalogue of publications in Computer Science by faculties and
students from the Departamento de Informática of PUC/RJ, covering the period
1968-1982.
[MCC03/82]
ANDREEWSKY, A.; RUAS, V. Indexação automática baseada em métodos linguísticos e
sua aplicabilidade a língua portuguesa. 31 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper deals with the automatic indexing based on linguistic and
statistical methods, whose aim is to allow the processing of documents in
natural language. We describe the main lines of a system called SPIRIT, that
uses such methods, and that was developed for the French Languages by a group of
researchers of the CNRS including the first author. We finally consider some
basic aspects of the applicability of those methods to the Portuguese Language.
[MCC04/82]
CASTILHO, J.M.V.; CASANOVA, M.A.; FURTADO, A.L. A temporal framework for
database specifications. 29 p. Eng. E-mail: casanova@inf.puc-rio.br
Abstract: A database description framework is introduced that accounts for
static constraints, that is, constraints on what data can be stored, as well as
transition constraints, that is, constraints on how data can be updated. Two
levels of specification are considered. At the first level of specification, a
database description D1 does not indicate how the database will be updated.
Transition constraints are then specified with the help of a convenient variant
of Temporal Logic. By contrast, at the second level of specification, a database
description D2 includes a set of builtin update operations which, by convention,
must be used by any update transaction. These operations are described by their
properties, rather than by actual code. A second variant of temporal Logic is
used for this purpose. The two descriptions, D1 and D2, are connected by a
notion of refinement where the set of built-in update properties listed
in D2 must guarantee all constraints defined in D1. The advantages accrued from
this approach are two fold: first-level specifications give a direct, stable
description of constraints, while second-level specifications suggest an
effective strategy to enforce constraints.
[MCC05/82]
MOURA, C.M.O.; CASANOVA, M.A. Design-by-example (preliminary report). 19 p. Eng.
E-mail: casanova@inf.puc-rio.br
Abstract: A constraint definition language, that provides a uniform notation for
data dependencies commonly used, is introduced. Constraints are expressed in
this language in much the same way as queries are defined in Query-by-Example.
Dictionary facilities to manage constraint written in this language are also
described. Finally, the problem of
checking if a set of constraints captures the intended semantics of the
enterprise is considered.
[MCC06/82]
FURTADO, A.L.; FURTADO, A.A.B.; MESSEDER, F.A. Instructional graphics packages
to be used with a line printer. 25 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: Two similar packages - one in WATFIV-S and the other in Pascal - for
teaching elementary graphics are completely described. The packages are to be
used with conventional line printers, offering a reasonable alternative to
installations where either specific graphics hardware is not available or the
size of the student classes makes its usage incovenient.
[MCC07/82]
VELOSO, P.A.S.; MAIBAUM, T.S.E. Specifying abstract data types via series
rewriting systems. 13 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Abstract data types have been widely recognized as a powerful
programming tool. However, the full exploitation of their benefits requires
formal specifications, which are generally not so easy to obtain or to
understand. Helping alleviating both problems is an important motivation for
proposing multi-level specifications. Each level is to consist of a system of
rewrite rules transforming an approximation to a canonical form into a better
one. This supports a stepwise refinement approach to the problem, leading to a
better documentation for the specification.
The problem of formally specifying a model is decomposed into first obtaining
canonical representatives, then designing a rewriting system. Each of these
subproblems in turn is factorized into a finite sequence of approximations. Some
criteria are developed which guide the application of the methodology and
justify it, in that they give sufficient conditions for the correcteness and
completeness of the specification so obtained.
[MCC08/82]
RUAS, V. On the solvability of asymmetric quasilinear finite element approximate
problems in nonlinear incompressible
elasticity. 57 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper deals with a class of simplicial finite elements for
solving incompressible elasticity problems in
n-dimensional space, n=2 or 3. An asymetric structure of the shape functions
with respect to the centroid of the simplex, renders them particularly stable in
the large strain case, in which the incompressibility condition is nonlinear. We
prove that under certain assembling conditions of the elements, there exists a
solution to the corresponding
discrete problems. Numerical examples illustrate the efficiency of the method.
[MCC09/82]
FURTADO, A.L. A W-grammar approach to data bases. 14 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A generative formalism for the characterization of fundamental data
base concepts and for the specification of data base applications is proposed.
The formalism is based on W-grammars, which are two-level grammars whereby a
possibly infinite set of context-free productions can be derived: W-grammars can
cope with non-local constraints as found in data base applications. The
formalism is used to precisely characterize the concepts of state, transition,
execution of primitive operations, execution of application-oriented operations
and traces. Involved, in turn, in the
characterization are facts, static and transition constraints, pre-conditions,
transactions and encapsulation. The use of
W-grammars to formalize mappings between schemas is outlined.
[MCC10/82]
RUAS, V. Quasilinear finite elements for the stokes problem in R3. 28 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: We discuss a special kind of finite element approximation of the
three-dimensional Stokes problem, giving rise to quasi-solenoidal velocity
fields. Convergence results for the case of a parallelepipedal domain are
derived, and numerical examples are shown.
[MCC11/82]
STAA, A.v. DSAC: desenvolvimento de software apoiado em computador. 22 p. Port.
E-mail: arndt@inf.puc-rio.br
Abstract: Describes a system to support software development projects at the
Departamento de informática or PUC/RJ. DSAC main objetive is to serve as a
means of coordinating and agglutinating software engineering research activities
at the Department.
[MCC12/82]
PESSOA, F.E.P.; VELOSO, P.A.S. Introdução à programação com tipos abstratos de
dados. 60 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper presents a didactical introduction to some important
aspects of abstract data types in programming. Abstract data types have been
recognized as a powerful tool in the development of reliable programs. The usage
of abstract data types enables an elegant program construction: the program is
factored into two
parts: a program manipulating abstract data types objects by means of their
operations and an implementation, which represents these objects and operations
in terms of more concrete data types. As a result a natural factorization is
obtained for several programming tasks, namely specification, development,
documentation, verification, testing, etc. The introductory chapter consists of
general remarks about the usage of abstraction in programming, stepwise
refiments, etc. The next chapter presents Hoare's data structuring mechanisms
and how they appear in programming
languages like PASCAL, ALGOL 68, etc. It also presents general purpose data
abstraction mechanisms such as those existing in CLU. This programming language
is employed in chapter III to present a detailed example illustrating the
process of program development by means of abstract data types. The final
chapter contains some general remarks on formal specification and implementation
of abstract data types.
[MCC13/82]
STAA, A.v. Metodologias para desenvolvimento de sistemas automatizados: a
proposta de desenvolvimento. 64 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: Presents a guideline to write and evaluate automated systems
development proposals.
[MCC14/82]
VELOSO, P.A.S. Outlines of a mathematical theory of problems.
26 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper outlines a program of research aiming at a
mathematical theory of problems with a wide applicability. Motivation,
present status with typical results, ongoing work and future directions
are outlined. Problems, solutions and problem-solving methods are
notions widely dealt with in Heuristics, Artificial Inteligence, etc.
However, these notions are generally treated either too restrictively
or in vague ways. In order to undertake a rigorous study of problems
and associated notions, one must have them precisely defined. Here we
propose a formulation of problem as a mathematical structure, solution
being certain functions. Thereby, we have at our disposal the available
logico-algebraic machinery. Moreover, within this framework, notions
such as solvability, reduction, decomposition, etc. can be precisely
formulated and rigorously examined. We outline a framework for the
study and critical analysis of problems. This framework is mathematical
in order to have rigor. But, it is not oriented only towards mathematical
problems, rather an effort is made so as to have it applicable to a wide
diversity of problems.
-----------------------------------------------------------------------------------------------------------------------------
1983
[MCC01/83]
VELOSO, P.A.S. Problem solving via divide-and-conquer and abstract data types.
16 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The divide-and-conquer approach to problem-solving consists of
decomposing a problem into smaller problems. Here this powerful approach is
formalized by means of an incompletely specified abstract data type and a
general program, proven to be correct, on it. Thus, solving a problem via
divide-and-conquer amounts to interpreting the abstract data type on the problem
domain. Examples are given to illustrate the applicability of this viewpoint to
problem-solving.
[MCC02/83]
VELOSO, P.A.S.; FURTADO, A.L. On multi-step methods stepwise construction of
algebraic specifications for data base applications. 40 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A multi-step methodology for the formal specification of data base
applications, entirely within the algebraic approach to abstract data types, is
presented. Towards this end the concept of traces is extended to several levels,
which gives a useful tool to obtain formal specifications in a systematic and
constructive way. In addition, the concept of traces has familiar simple
analogues. The presentation is based on a simplified example of data base, which
is successively specified in three formats: procedural notation, systems of
term-rewriting rules and conditional equations.
[MCC03/83]
VELOSO, P.A.S. A methodology for the sound and complete specification of
abstract data types. 9 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper outlines and justifies a methodology for the sound and
complete specification of abstract data types viewed as initial algebras. This
methodology helps overcoming the problems of what equations to write and when to
stop writing them by means of canonical term algebras and symbolic
transformations. The methodology
is justified by showing that the equations obtained always form a sound complete
specification of the given model. Furthermore, the methodology is shown to be
non-obtrusive, in that it does not prevent finding such a specification it one
exists at all.
[MCC04/83]
LE TALLEC, P.; RUAS, V. On the convergence of the bilinear velocity-constant
pressure finite element method in viscous flow. 14 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In this paper we show that the standard isoparametric (formula)
velocity-pressure finite element method for solving viscous flow problems, leads
to a fully and optimally convergent sequence of approximations, if an approxiate
quadrangulation of the domain is used.
[MCC05/83]
LUCENA, C.J.P.; VELOSO, P.A.S.; MARTINS, R.C.B.; COWAN, D.D. The data transform
programming method and file processing problems. 46 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: This paper presents a new programming method, called the data
transform programming method. In particular, we present a specification of data
transform programming to deal with file processing applications. Direct
comparison is made with Jackson's approach 1 by the presentation of uniform
solutions to problems that cannot be solved trhough his basic method. The new
method consists of the application of data transformations to the
abstract problem statement, following the formal notions of problem reduction
and problem decomposition. Data transformations are expressed in programming
terms through a basic set of data types constructors. The method reduces the
original problem to a set of sub-problems that can be solved trhough the direct
application of Jackson's method. It produces a solution which is correct by
construction.
[MCC06/83]
RUAS, V. A convergent finite element method for solving dynamic problems with
consistent diagonalized mass matrix. 14 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A finite element method for solving dynamic problems having piecewise
quasilinear basis functions is presented. The method leads to a consistent
diagonalized mass matrix, whereas the stiffness matrix is essentially the same
as in the piecewise linear case. Convergence of the approximate solution to the
exact one is guaranteed.
[MCC07/83]
STAA, A.v.; ROCHA, A.R.C. Towards a model for evaluating specifications. 19 p.
Eng. E-mail: arndt@inf.puc-rio.br
Abstract: Software quality depends directly on the quality of its specification.
In other words, in spite of all our efforts, it will be almost impossible to
construct high quality software unless high quality specifications are used. It
is thus necessary to identify the characteristics which high quality
specifications should satisfy. Furthermore, specifications are created following
some methodology and using some language. Frequently these methodologies and
specification language are ad hoc, thus not necessarily leading to the
construction of high quality specifications.
It is necessary then to identify the characteristics which methodologies and the
specification languages must possess in order to produce high quality
specifications. In this paper a specification quality model is outlined. The
objectives of this model are twofold. First, the model should serve as a means
to evaluate the quality of a given specification. Second, the model should serve
as a means to specify the requirements of methodologies and specification
languages which lead almost naturaly to quality specifications.
[MCC08/83]
VELOSO, P.A.S.; FURTADO, A.L. On some view constructs for the specification and
design of external schemas. 20 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A view construct is proposed which consists of derived objects and
operations defined on them. Attention is focussed on the update operations, for
which the conditions, effects, and side-effects must be specified. This
construct is a template, appropriate both for abstract specification and
concrete realization. A simple data base environment is described and employed
to illustrate the proposed approach at three levels: informal description,
formal specification and representation in terms of (a simplified version of)
the entity - relationship model.
[MCC09/83]
ALVARENGA, C.C.; D'IPOLITTO, C.; MELO, R.N. Sistema de dicionário de dados da
PUC (SDDPUC) - manual do usuário. 37 p. Port. E-mail: rubens@inf.puc-rio.br
Abstract: This work presents an User's Manual for the SDDPUC (PUC's Data
Dictionary System). Firstly, the manual presents a brief description of the
system and of its implementation. Next, the manual provides the definition of
the system's commands and an example of a specification using SDDPUC.
[MCC10/83]
WAJZENBERG, A.; CASTILHO, R.T.L.; ALMEIDA, L.C.; CASANOVA, M.A. Sistema de
informação para o controle e acompanhamento de atividades acadêmicas do
Departamento de Informática - Parte 1 - Projeto logico do banco de dados. 75 p.
Port. E-mail: casanova@inf.puc-rio.br
Abstract: A methodology is described for the logical design of an information
system to assist and control the PUC/RJ - Departamento de Informática academic
activities.
[MCC11/83]
TUCHERMAN, L.; FURTADO, A.L.; CASANOVA, M.A. A pragmatical approach to
structured database design. 51 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: A database design methodology, based on the concept of module, is
proposed as a way of managing the complexity of database descriptions and, at
the same time, enforcing integrity constraints. The design of database is
carried out in two levels of abstraction, the specification level, which is
independent of any database management system, and the representation level,
that refines the first one into an actual implementation of the database. At the
specification level, the definition of a module consists of a high-level
description of the structures and operations of the module, as well as the
integrity constraints. Two module constructors, extension and subsumption, are
used to define new modules from old ones. Extension is similar to the usual view
mechanism. Subsumption is a new module constructor that permits adding new
structures, operations and constraints to those of old modules, and redefining
old operations, which may be required to maintain integrity. The representation
level description of a database is carried out using the SQL/DS system, which
indicates that the modular database design proposed can be used in conjunction
with present day systems. Finally, the concept of module graph is introduced to
capture the modular structure of the database.
[MCC12/83]
ALBRECHT, P. Numerical treatment of ordinary differential equations: the theory
of A-methods. 47 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Almost all commonly used methods for O.D.Es. and their most
miscellaneous compositions are A-methods, i.e. they can be reduced to (formula).
This paper presents a general theory for A-methods and discusses its practical
consequences. An analysis of local discretization error (l.d.e.) accumulation
results in a general order criterium and reveals which part of the l.d.e.
effectively influences the global error. This facilitates the comparison of
methods and
generalizes considerably the conpet of error constants. It is shown, as a
consequence, that the global error cannot be safely controlled by the size of
the l.d.e. and that the conventional error control may fail in important cases.
Furthermore, Butcher's "effective order" methods, the conept of Nordsieck forms,
and Gar's interpretation of linear k-step schemes as relaxation methods are
generalized. The stability of step changing is shortly discussed.
[MCC13/83]
ALBRECHT, P.; PEREIRA, A.B.; MARTINS, S.P. Uma nova base teórica para a
integração numérica de equações diferenciais ordinárias. 56 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: Almost all commonly used methods for O.D.Es. and their most
miscellaneous compositions are A-methods, i.e. they can be reduced to the
A-dependent form (formula). This paper presents a general theory for such
methods in order to provide the necessary toolsfor the theoretical approisal of
composite methods. After a short introduction to the theory of Dahlquist, the
A-method concept is presented and its stability discussed. The order condition
presented in chapter 3 is of major importance for the theory, especially to
error control (which is not discussed here). Finally,
the idea of equivalent methods is presented resulting in a new approach to
Nordsieck's methods, and the effects of step changes to stability is discussed.
[MCC14/83]
VELOSO, P.A.S. On the logic of namable models. 15 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Some logical properties of namable models for structured data (data
structures and data types) are presented, mostly from a model-theoretic
viewpoint. It is argued that "namability" captures the notions of accessibility
and constructibility of structured data, the corresponding axiomatic theories
serving as logical specifications for them. Related concepts are also discussed.
[MCC15/83]
VELOSO, P.A.S.; MAIBAUM, T.S.E. A theory of abstract data types for program
development: bridging the gap? 25 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper outlines a logical approach to abstract data types, which
is motivated by, and more adequate for, the practice of programming. Abstract
data types are specified as axiomatic theories and notions concerning the former
are captured by syntactical concepts concerning the latter. The basic concept of
namability, conservative
extensions and interpretations of theories explain implementation, refinement
and parameterization. Being simple, natural and flexible this approach is quite
appropriate for program development and certification.
[MCC16/83]
VELOSO, P.A.S. On the role of additivity and linearity in mathematical systems
theory. 15 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper shows that many properties of linear time-invariant systems
are due to the underlying group structure even if not commutative. Within a
general time-systems framework some properties of additive time-varying systems
are examined: attainability, observability, reachability, controllability,
realizability and state-space construction. These are regarded from the
viewpoint of mathematical foundations of general time-systems theory.
[MCC17/83]
RUAS, V. Análise aplicada. 175 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This text is an introductory presentation of topics in Functional
Analysis for the use of advanced level students or specialists in Applied
Sciences, such as Engineering, Continuum Mechanics, Optimization, Systems Theory
or Numerical Analysis. Its aim is to provide a mathematical foundation to all
those who usually do not undergo a regular education in Functional Analysis, and
who are therefore prevented from making the best use of some of the modern and
efficient methods that they have at their disposal in their respective fields.
The subjects, which were selected in order to cover the widest possible spectrum
of interest, are: Linear Vector Spaces, Normed Spaces, Banach and Hilbert Spaces
and Continuous Linear Functionals and Operators. In order to allow the best and
easiest understanding of abstract concepts for those who do not usually have
enough time to devote themselves to the study of Mathematics, only some simple
reflexions on them are left to the reader. On the other hand, a relatively large
number of examples illustrate the various definitions and theorems that are
given.
[MCC18/83]
RUAS, V. Automatic generation of tetrahedral meshes with application to finite
element solution of Stefan problem.
20 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A simple and straightforward procedure for the automatic generation of
partitions into tetrahedrons of three-dimensional starshaped domains is
introduced. The method generalizes the one previously proposed for the
two-dimensional case. As in that case, we consider the application of the method
to the numerical solution of one-phase Stefan problems.
[MCC19/83]
VELOSO, P.A.S.; MARTINS, R.C.B. On some notions of reduction among general
problems. 15 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The notion of reduction among problems is widely employed. Here this
notion is examined in the context of a mathematical theory of problems. Three
precise versions of reduction are introduced, characterized and compared. The
aim is a clarification of the essential features of this method of problem
transformation.
[MCC20/83]
PESSOA, F.E.P.; VELOSO, P.A.S. Introdução à especificação e implementação de
tipos abstratos de dados. 102 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper presents a didactical introduction to the basic concepts of
specification and implementation of abstract data types within an algebraic
approach. Abstract data types are a powerful tool for the development of
reliable programs. By employing abstract data types the program is factorized
into two parts, namely a program, called abstract, manipulating objects of the
abstract data type solely by means of its operations, and an implementation
module, which represents the objects and operations of this data type in terms
of other, more concrete, data type(s). A specification of an abstract data type
must describe the behavior of its operations without resorting to any specific
representation. Specification and implementation are examined here from an
algebraic viewpoint without consideration of programming language aspects. The
introductory chapter presents some remarks on the usage of abstraction in
program development and on the concept of type in programming. Chapter II deals
with
specification of abstract data types, first the error-free case, then including
errors, the problem of specification correctness, and presents a methodology for
the construction of correct specifications. Chapter III deals with
implementation: the basic concept, the problem of correctness and suggests a
methodology for verifying the correctness of implementations. The final chapter
presents some brief remarks on the relationship between program verification and
specifications and implementations as well as on abstract data types in
programming languages. Finally, the appendix makes more precise some details
concerning the specification of abstract data types as initial algebras.
[MCC21/83]
MAIA, A.C.P. Um estudo em compressão de dados. 30 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: Data compression techniques are tools that can and must be used on
information systems in order to improve their performance. This is possible by
reducing the necessary storage space for data representation. The paper tries to
analyse the techniques described in the literature on data compression and
discuss the benefits and constraints associated with their use.
----------------------------------------------------------------------------------------------------------------------------------
1984
[MCC01/84]
VELOSO, P.A.S.; CASANOVA, M.A.; FURTADO, A.L. Formal data base specification -
an ecletic perspective. 48 p. Eng. E-mail: casanova@inf.puc-rio.br
Abstract: Logical, algebraic, programming language, grammatical and denotational
formalisms are investigated with respect to their applicability to formal data
base specification. On applying each formalism for the purpose that originally
motivated its proposal, it is shown that they all have a fundamental and well
integrated role to play in different parts of the specification process. An
example is included to illustrate the methodological aspects.
[MCC02/84]
RUAS, V. Finite element solution of 3D Viscous flow problems using nonstandard
degrees of freedom. 27 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Two velocity-pressure finite element methods for solving
incompressible flow problems in three-dimension space are presented. The
velocity is defined by means of a new type of degree of freedom called
parametrized. Though nonconforming in velocity, optimal convergence results are
proven to hold for both methods.
[MCC03/84]
ALVARENGA, C.; TANAKA, A.K.; MELO, R.N. Padronização de sistemas gráficos. 82 p.
Port. E-mail: rubens@inf.puc-rio.br
Abstract: Much effort has been invested during the last decade towards an
adequate minimum for a graphics package. This work presents the two main
proposal for the standardization of such softwares: the CORE system and the
Graphical Kernel System (GKS). First these systems are analysed and then
compared in their main features.
[MCC04/84]
TAVARES, O.L. Manual de implementação do protocolo de transferência de arquivos
da REDPUC. 114 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This report presents the PASCAL code of the REDPUC FILE TRANSFER
PROTOCOL (PTA - REDPUC) and gives complementary informations to reference [1] to
make easier the PTA-REDPUC implementation.
[MCC05/84]
FURTADO, A.L.; MOURA, C.M.O. Expert helpers to data-based information systems.
17 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: This paper discusses some features of software tools - expert helpers
- to provide expert assistance in the specification, usage and maintenance of
data-based information systems. A simple PROLOG prototype and an example
information system are used to illustrate the discussion.
[MCC06/84]
RUAS, V. Métodos de elementos finitos mistos: pt.1- Introdução aos fundamentos
matemáticos. p. Port. E-mail:
bib-di@inf.puc-rio.br (report not available)
Abstract: abstract not provided.
[MCC07/84]
MELO, R.N.; SILVA, S.D. DBTGinho: uma implementação da proposta CODASYL. 48 p.
Port. E-mail: rubens@inf.puc-rio.br
Abstract: This work presents the general caracteristics of DBTGinho, a data base
management system (DBMS), development in the Departamento de Informática -
PUC/RJ. The system is of the "network" type, being based in the DBTG-CODASYL's
proposal (1971).
--------------------------------------------------------------------------------------------------------------------------------------
1985
[MCC01/85]
VELOSO, P.A.S. On the concept of problem - solving method. 22 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: This paper proposes precise formulations, based on abstract data types,
for the concepts of problem, problem-solving method, and the application of a
problem-solving method to a problem. These formulations are argued to agree with
the intuitive understanding of these ideas, thereby formalizing them. This
formalization is based on few basic concepts: abstract data type and an
extension mechanism (here, a general cluster-like module). Moreover, by
embodying ideas related to stepwise renement they are applicable both to problem
solving in general and to the process of program developement. Examples are
provided to illustrate the main ideas and their applications.
[MCC02/85]
VELOSO, P.A.S. What do you mean by "Here is a problem related to yours..."? 21
p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The basic question examined in this paper is: what should one
understand by 'related' is assertions such as "Here is a problem related to
yours...". Problems can be related in various ways, depending on the connexions
between them. Each such connexionestablishes relations between the solutions of
the corresponding problems. Here, some precise formulations for these connexions
and the corresponding relations are proposed and examined. A problem is defined
as a mathematical structure, its solutions being functions satisfying the
problem requirement. The connexions examined are reduction, homomorphism,
analogy, and similarity. The aim is gaining a better understanding of these
important notations by means of a precise investigation of their properties.
[MCC03/85]
RUAS, V. Uma introdução a teoria matemática dos métodos de elementos finitos
mistos. 42 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: The aim of this work is to present the essential mathematical aspects
related to the study of mixed finite element methods. As it is well-known, such
aspects provide a basis for both under - standing and analysing most of the
finite element methods of this type currently in use. The material is intendend
to be an introduction to another text on the Numerical Analysis of these methods
to be edited by this Series of Monographs in the near future. Taking into
account the lack of detailed study about this topic in the literature on finite
element methods, one of the
author's main concern in preparing this text was being didactic, while making it
as self-contained as possible.
[MCC04/85]
VELOSO, P.A.S. Programme development as theory manipulations. 30 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: The process of programme development consists of manipulation of
theories. A case is presented for this position, both as describing a fact ("what
does happen") and as proposing a viewpoint ("what should happen"). Its rationale
is the realisation that programmes do not manipulate directly real-world objects
but only their symbolic representations. The process of programme development (by
means of abstract data types) is argued to be best described, explained and
understood in this syntactical manner without resource to other entities.
Supporting this position are both a theory of abstract data types and a
methodology for programme development by stepwise refinements. The former, based
on a few logical concepts (conservative extensions and interpretations of
theories), offers a natural and simple treatment of (incomplete) specifications,
implementation, parameterisation and errors. The
latter is oriented towards the smooth construction of reliable, verifiable
programmes. We feel that both model what (good) programmers (should) do.
[MCC05/85]
ALBRECHT, P. A new theoretical approach to Runge-Kutta methods. 29 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: RK-methods are treated here as linear multistage methods within the
author's concept of A-methods. As a consequence, the traditional difference in
treatment of RK-methods and linear multitep methods vanishes: in particular, it
is not necessary to consider elementary differentials. It is shown how the order
of a RK-method depends on the error constants of its stages, and the conditions
(nonlinear equations) for order p are generated from a very simple recursion.
[MCC06/85]
VELOSO, P.A.S. On the role of (data) abstraction in program development and
problem solving. 26 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: Abstraction has played an extremely important role in the process of
program development and should play an even more important one in that of
problem solving. Program development by means of stewise refinements can be more
confidently carried out by employing abstract data types (ADI's for short). This
allows the programmer to concentrate on the problem by employing (abstract)
operations close to it rather than worrying about their detailed representations
from the very beginning. An even more flexible variation employs incompletely
specified ADT's
which frees the programmer from the need to provides complete specifications for
the data abstractions involved. A further step of abstraction leads to the
concepts of problem and problem-solving method. A concrete problem (CP, for
short) is a two-sorted mathematical structure consisting of two domains, one of
(input) data and one of (OUTPUT) results, and a binary relation between them,
the problem conditions; a solution is a function assigning results to data so as
to satisfy the problem condition. An abstract problem (AP, for short) is a class
of CP's specified by their properties, say by axioms. In solving a problem one
generally defines a solution for it by extending its language, which leads to
the idea of PSM (short for problem-solving method) as an extension mechanism for
defining fuctions. A PSM is a module-like linguistic construct, operating on an
ADT, with a designated main procedure. Thus, AP's and PSM's are regarded as
ADT's and applying a PSM to an AP amounts to implementation of the corresponding
ADT's in that the PSM when interpreted on any CP of the AP defines a solution
for it. Among the PSM's that have already been precisely formulated in this
manner we mention reduction, divide-and-conquer, the greedy method, dynamic
programming, etc. This framework appears to be adequate to a precise
investigation of problem-solving methods aiming at a better understanding of
their applicability and power.
[MCC07/85]
STAA, A.v. Projeto MOSAICO: definição do projeto. 31 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: MOSAIC aims at supporting software lifecycle, including the
development and maintenance of all its eventual prototypes.
[MCC08/85]
STAA, A.v. MOSAICO - estruturado: requisitos. 30 p. Port. E-mail: arndt@inf.puc-rio.br
Abstract: In this report are defined: the objectives, architecture and the
environment requirements to support the MOSAIC structured programming system
project.
------------------------------------------------------------------------------------------------------------
1986
[MCC01/86]
RUAS, V. A quadratic finite element method for solving biharmonic problems in
IRn. 16 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A family of simplicial finite element methods
having the simplest possible structure, is introduced to solve biharmonic
problems in (formula), using the primal variable. Athough the family is inspired
in the MORLEY triangle for the two dimensional case, this element cannot be
simply viewd as its member corresponding to the value n=2. On the other hand
equivalent convergergence results are proven to hold for this family of methods.
--------------------------------------------------------------------------------------------------------------------------------
1987
[MCC01/87]
HAEUSLER, E.H. Automatic theorem proving: an attempt to improve readability of
proofs generated by resolution. 15 p. Eng. E-mail: hermann@inf.puc-rio.br
Abstract: The resolution method to generate proofs by machine is widely used
because it is a quick way to check whether a formula is a theorem. But the
proofs il gives are hard to read. We set out criteria for reability of proofs,
and then present a function which translates resolution proofs for the
propositional logic into Natural Deduction proofs. The latter will satisfy the
criteria.
[MCC02/87]
HAEBERER, A.M.; BAUM, G.; VELOSO, P.A.S. Sobre una teoria algebraica de
problemas y el desarrollo de software. 32 p. Esp. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper is a preliminary report on an algebraic theory of problems
and its applications to the software development process. The aim of this
ongoing research is providing a formal tool for the description of the various
transformations and heuristics involved in the software development process. A
good starting point for this purpose appears to be the notion of problem.
Problems are defined as mathematical structures and their solutions as certain
functions. Two operations on problems, sum and product, are introduced and their
algebraic properties investigated. The concepts of additive subproblem and of
complete additive subproblem are introduced and the algebraic structure of the
sets of such subproblems of a given problem is investigated. Finally, these
ideas are applied, in a tentative way, to the explication of a strategy for
problem solving and program development.
[MCC03/87]
HAEBERER, A.M.; VELOSO, P.A.S.; BAUM, G. Hacia un metamodelo del processo de
desarrolo de software baseado en teoria de problemas. 49 p. Esp. E-mail: bib-di@inf.puc-rio.br
Abstract: The need for a formal model of the software development process has
been felt for some time now. Such a model is needeed in order to understand the
deep nature of this process and for the design and implementation of an
environment to support software development. This work is based on the viewpoint
that the software development process may be regarded as consisting of a series
of linguistic transformations starting from the requirements of a
problem and ending with a solution for it in the form of an efficient program.
First, some fundamental notions on the concept of model as well as Lehman's PW
model are reviwed. Then, some methodologies for program construction are
examined, which suggests a first view of the software process as solving
problems. Some concepts from an algebraic theory of problems are briefly
introduced and used to provide a framework for the analysis of the software
process. Finally, a more precise description of our metamodel is presented,
emphasizing the distinctions between executable and non-executable, formal and
informal specifications, as well as between verification and validation by
testing.
[MCC04/87]
IERUSALIMSCHY, R. Abstração de dados em linguagens de programação: tipos e
objetos. 15 p. Port. E-mail: roberto@inf.puc-rio.br
Abstract: This work discusses data types objects as data abstraction mechanisms
in programming languages, with particular emphasis in software reutilization and
typing. Many languages are referred to on such discussion, being Ada, CLU and
Smalltalk Investigated in more detail.
-------------------------------------------------------------------------------------------------------------------------------
1988
[MCC01/88]
MENASCE, D.A.; ALMEIDA, V.A.F. On the investigation of supercomputer
architectures in multiprogramming environments using analytic models. 23 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: Supercomputers are being widely used for applications that require
high speed computing, such as weather forecasting, spaceship and aircraft design
and simulation, and analysis of geological and seismic data, to name a few.
These machines run multiprogrammed time-sharing operating systems, so that their
facilities can be shared by many local and remote users. Therefore, it is
important to be able to assess the performance of supercomputers
in multiprogrammed environments. Most studies of supercomputer are concerned
with the evaluation of the effective speed of a program running in isolation on
a particular supercomputer. Analytic models based on Queueing Networks (QNs) and
Stochastic Petri Nets (SPNs) are used in this paper with two purposes. The first
is to evaluate the performance of supercomputers in multiprogrammed environments,
and the second is to compare performance-wise conventional supercomputer
architectures with a novel architecture proposed here. It is shown, with the aid
of the analytic models, that the proposed architecture is preferable
performance-wise over the existing conventional supercomputers. A three level
worload characterization model for supercomputers is presented. Input data for
the numerical examples discussed here are extracted from the well known Los
Alamos Benchmark.
[MCC02/88]
RUAS, V. Approximation of the vector potential for viscous incompressible flow
via the constant stress finite elements. 24 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A convergence analysis for a piecewise quadratic finite element method
to solve vector biharmonic problems in IR3 in primal variables is presented. The
application to the equations of the vector potential for the flow of
incompressible viscous fluids is focused. For simplicity, only the particular
case of stationary stokesian flows is treated in detail, but it is showed that
the method applies as well to more complex flows of such fluids.
[MCC03/88]
BITTEL, O.; ALENCAR, P.S.C. Towards a tableau-based intuitionistic theorem
prover. 30 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A proof procedure for the first-order intuitionistic logic which is
based on an improved version of the intuitionistic Beth tableau calculus is
presented. It also treats the problem of proving under intuitionistic theory.
[MCC04/88]
VELOSO, P.A.S.; HAEBERER, A.M. A problem-theoretic analysis and (meta-)model of
the software development process. 46 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The software development process is analyzed from a problem-theoretic
viewpoint and a precise (meta-)model is proposed. This provides a uniform
conceptual structure for understanding this process by clarifying its semantics
and indicates some important requirements on formalisms purporting to represent
it. The software
development process goes from informal descriptions to efficient programs, which
are formal and executable, via precise specifications. The first phase, of
formalization, is similar to theory construction in natural science and is
validated as such. The process of program construction obtains an efficient
program from a precise specification
and has as central step the construction of solutions for problems. Auxiliary
steps, capturing divide-and-conquer and reduction ideas, consist of
specification translations, with refinements and decompositions, and program
translations, with recombinations and extensions. This meta-model provides a
formalization for a large portion of software development process, leaving
another portion as heuristics, which appears to be an essential ingredient in
any widely
applicable method. This analysis also sugests the non-existence of a single
canonical step for the entire process as well as obstacles to its complete
formalization or automation.
[MCC05/88]
PESSOA, T.E.C. Existe logica em redes semanticas? 29 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstract: The aim of this work is to investigate the possibility of
representing in logic the information and the inference process
usually found in semantic networks. First of all, some notations and
meanings sometimes found in semantic networks are criticized. Based
on this criticism a notation and some inference mechanisms, with their
usual interpretation, are chosen in order to investigate their
representation in logic.
[MCC06/88]
SOARES, J.F.; IERUSALIMSCHY, R.; PESSOA, T.E.C. Um ambiente para a
transformacao semi-automatica de diagramas de fluxos de dados em
diagramas de objetos. 25 p. Port. E-mail: roberto@inf.puc-rio.br
Abstract: This work describes a heuristics based environment whose
function is to transform Data Flow Diagrams into Object Diagrams.
Besides the description of the system and its architecture, some
aspects of the technique used in this development (Object Oriented
Programming) are discussed together with some considerations about
the language and the implementation environment (Smalltalk).
[MCC07/88]
FURTADO, A.L.; VELOSO, P.A.S. Iteration for applicative languages:
a proposal. 9 p. Eng. E-mail: furtado@inf.puc-rio.br
Abstract: The mathematical notion of function exponentiation is used
to introduce an iteration construct suitable to applicative languages.
The elements of the construct are explained as well as its evaluation.
A prototype Prolog implementation is included to illustrate the discussion.
[MCC08/88]
SOARES, J.F.; GUARANYS, P.Y. Extensoes propostas sobre o monitor
para apoio a programacao em logica. 24 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: This work describes a proposal for the alteration of the
specification of the system "MPL - An aid Monitor for Logical
Programming" [GUAR 88]. The two main goals for the proposed modifications
are: the definition of a human-machine interface system to facilitate
the comfortable and efficient use of the system by users with diferent
levels of expertise, and the introduction of a help tool to the domain
inheritance mechanisms of the parameters.
[MCC09/88]
SOARES, J.F.; GUARANYS, P.Y. Um monitor para apoio a programação
em lógica. 20 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper describes a software tool that aids the
construction of programs written in Rule Based Oriented programming
language. Edition and monitoring functions are included. The monitoring
functions ckeck the completeness and the matching of the various
program components of an application.
[MCC10/88]
NUNES, M.G.V. Deep generation in a crime knowledge-based system.
54 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A deep generation technique is proposed for producing
cooperative replies to Yes/No questions. It is based on the linguistic
notion of focus and involves the use of common-sense knowledge about
the domain of discourse. Information selectec or derived from domain
knowledge constitute the response and form the terminal elements of
a discourse structure that is based on Rhetorical Structure Theory.
[MCC11/88]
RANGEL NETTO, J.L.M. Manual de operacao do sistema de geração de
analisadores sintáticos R*S simples. 48 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: This paper presents the necessary information for the use
of a parser generator which is based on the simple version of the
R*S parsing method. The generator itself has been in use for four
years, and has been shown as a flexible and powerful tool for use
in the construction of compilers and similar software. In order to
be self-contained, this paper includes a short presentation of the
theory of the method, and general description of the implementation.
We have also included information on practical ways of ambiguity
renoval, and conflict resolution and on the attachment of semantic
actions to syntax rules in simple R*S grammars. A companion program
which gererates tables in compact form is also presented. This last
program generates code which may be directly inserted in Turbo Pascal
programs. Some small modifications would be required, in the case of
other languages.
[MCC12/88]
SILVA, J.R.; LUCENA, C.J.P. Um novo paradigma para o problema
de reutilização de software. 15 p. Port. E-mail:
lucena@inf.puc-rio.br
Abstract: Presents the central ideas of a new paradigm for the treatment of
software reutilization problem, based on a formal theory of metaphors named "constrained
semantics transference".
[MCC13/88]
SCOTT, D.R.; SOUZA, C.S. Conciliatory planning for extended
descriptive texts. 15 p. Eng. E-mail: clarisse@inf.puc-rio.br
Abstract: Good text requires good planning. This is even more
crucial when the text is long and therefore more sensitive
to stylistic biunders that can affect cognitive processing.
Descriptions of complex data objects are an instance of such
a text. GEMA is a language generation system for producing
descriptions of complex data objects. These descriptions
will usually contain several paragraphs. Texts of this
length demand more stylistic harmonization than is typically
required of text generators, and producing them commands a
great deal of interaction between planning and realizing
conponents of the generator. This brings with it some
computational problems that are not very well handled by
existing planning approaches. We describe in this paper a
planning approach that has been developed for GEMA that
combines some of the more desireable features of traditional
text-planning approaches and which achieves good stylistic
effects. We have called this concillatory planning.
[MCC14/88]
LUCENA, C.J.P.; SILVA, J.R. An approach to software reuse based
on a formal theory of metaphors. 9 p. Eng. E-mail:
lucena@inf.puc-rio.br
Abstract: The present paper examines the relationship between
software reuse and a formaltheory of metaphors and analogies.
More specifically, we have used a formal theory of metaphors as
a metaphor for the problem of software reusability. Metaphors
use symbols belonging to a domain, called the source domain,
to refer to objects that belong to a possibly different domain,
called the target domain. We explore an example by demonstrating
the viability of reuse when a systematic development method is
applied in both the source and the target domains. We also
examine the computational aspects of the method to show that
it may become a promising technique for the reuse of software
designs.
[MCC15/88]
GUARANYS, P.Y.; LUCENA, C.J.P. PUC: a knowledge based environment
for planned user communication. 18 p. Eng. E-mail:
lucena@inf.puc-rio.br
Abstract: PUC's requirements are based on our view that the ideal
environment for designing a personalised interface is one which
involves the collaboration of the user and an interface designer
who knows about the application. The approach used in the design
of PUC was to incorporate the interface designer "into the
environment" and invite the user to produce his/her own interface
with its assistance. The approach aims to allow the end user to
plan his/her future interaction with an application while
learning about it.
[MCC16/88]
LUCENA, C.J.P.; VEGA, I.S.; SICHMAN, J.S.; LEVENTHAL, J.;
CAMARGO JR., J.B.; SILVA, J.R.; BARRETO, M.R.P. An intelligent
environment for the design of production systems units. p.
Eng. E-mail: lucena@inf.puc-rio.br (report
not available)
Abstract: abstract not provided.
[MCC17/88]
FERNANDES, C.T. Um algoritmo de hifenização multilíngue. 25 p.
Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This report presents an automatic hyphenation algorithm
for several languages. The user can inform the hyphenator the
current language of the text through formatting commands. The
algorithm works well for languages with well-defined rules, such
as Portuguese, as well as for languages with difficult hyphenation,
such as English. A few ideas are shown for improving the process
of hyphenation. It is also shown how the language structures are
stored in a real implementation.
[MCC18/88]
HAEUSLER, E.H. Intuitionistic type theory and general problem
theory: a relationship. 52 p. Eng. E-mail: hermann@inf.puc-rio.br
Abstract: Constructive reasoning may be used in some different
fields, such as Set Theory, Logic and Problem Theory. Martin-Lof's
intuitionistic type theory (ITT) is a way to express
constructive reasoning in these fields. Veloso's general problem
theory (GPT) is an approach to explain the concept
of problem in the context of problem solving (it is restricted to
formalized problem). In this work we explore a relatioship between
GPT and the problematic interpretation of ITT, searching common
features. We conclude this work by giving an approach to program
development based on this relationship.
[MCC19/88]
FERNANDES, C.T.; RANGEL NETTO, J.L.M. Otimização de código
utilizando gramáticas de atributos. 41 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: Solutions for two data flow problems are presented -
reaching definitions and available expressions - by means of
attribute grammars. Abstract trees are used as intermediate
representation instead of the usual syntax trees. An
algorithm performing the common subexpression elimination in
linear time on the number of the subexpression occurences is
also presented. This algorithm is based on the available
expression information. Some examples illustrate the technique
used.
[MCC20/88]
BRAZ, M.H.B. O desenvolvimento de interfaces. 41 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstract: In this work fundamental contributions of Software
Engineering for the development of user-computer interfaces
are analysed. Also some software environments which support
the development of interative systems are discribed.
[MCC21/88]
BRAZ, M.H.B. Interfaces inteligentes. 40 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: This work discusses the meaning of "intelligence"
in the context of Interactive Systems specially when applied
to models and interfaces. The case of Decision Support
Systems is used as an example. It also discusses some
characteristics that may be used to classify an interface as
"intelligent".
---------------------------------------------------------------------------------------------------------------------------
1989
[MCC01/89]
NUNES, M.G.V. Lettera: um gerador de textos. 28 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstract: A text generator in Portuguese is proposed. It
syntactically realises answers in a question-answer system.
The semantic representaton of an answer is previously
constructed by the planner, based on the Rhetorical
Structure Theory of Mann and Thompson. Stylistic and
focus-driven transformations are applied on basic sentences
generated by a unification grammar.
[MCC02/89]
IERUSALIMSCHY, R. Em busca de uma linguagem orientada a objetos
compatível com métodos rigorosos de desenvolvimento de programas.
28 p. Port. E-mail: roberto@inf.puc-rio.br
Abstract: The intention of this text is to lay a basis for a
research project on the use of formal methods for software
development with Object-Oriented Languages. We investigate
which mechanisms are relevant for object orientation and which
are the difficulties involved in the formalization of these
mechanisms. Facilities for Programming in the Large receive
special attention.
[MCC03/89]
GUARANYS, P.Y. S.O.S. - Sistema orientado a socorrer. 35 p.
Port. E-mail: bib-di@inf.puc-rio.br
[MCC04/89]
SILVA, W.T.; RICHTER, G. Formalização da abordagem orientada a objetos em redes
de Petri. 29 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: The object-oriented paradigm is gaining increasing impact as a guiding
conception for systems design and
development. However, the lack of an appropriates standard terminology based on
clearly defined concepts difficults
comprehension and comparison of the growing number of proposals which refer to
the object-oriented approach. This paper proposes a formalization of the main
concepts of object-oriented approach. This paper proposes a formalization of the
main concepts of object-oriented languages in term of high-level Petri nets
called predicate/Transition (Pr/T) Nets.
[MCC05/89]
LISANDRE, B.; SANTOS FILHO, H.N. Um gerador automático de interfaces homem -
máquina. 16 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: English abstract not provided.
[MCC06/89]
VARGAS, D.A.; HAEBERER, A.M. Formal theories of problems. 65 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: This work is based on the Algebraic Theory of Problems, developed by
Veloso, Haeberer and Baum. The aim
of the theory is to be a formal tool for treating diverse aspects of the
software process. This is not an independent
effort; in the last years, there have been a few attempts towards this goal, for
instance, [Leh83-Mai84-Sin84,85,86].
In its current version, or in slight variations there of, this theory has been
used to model the software development
process, the relationships among the application concept, its specification and
a program satisfying it, as well as to
develop a program derivation calculus, and also to explain programming
methodologies. First of all, this work tries to complete the mathematical
framework of the algebraic theory of problems, viewed as 4-tuples, called the
Theory of restricted problems (TRP). Using as a standard interpretation, an
axiomatization is proposed, giving rise to the so called Axiomatic Theory of
problems (ATP). Now, problems can also be thought of as 3-tuples - Theory of
irrestricted problems (TIP). It is shown that TIP is a model of a restriction of
the axiomatic theory. It is also shown that TIP cannot be extended to be a model
of the complete axiomatic theory. Both ways of seeing problems, TRP and TIP,
have shown their applicability, depending on the specific aspect of the software
development process one is dealing with.
[MCC07/89]
HAEBERER, A.M.; VELOSO, P.A.S. On the requirement - specification - program
triangle: a theoretical analysis.
30 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The interconnections among requirements, specifications and programs
are analyzed from a theoretical
standpoint by means of Carnap's Two-level Theory of the Language of Science and
the Algebraic Theory of Problems.
The goal of software development is argued to be the construction of an
engineering model of the application concept. The synthetic relation "being-an-engineering-model"
is argued to be a disposition, which has interesting consequences. On the one
hand, specification validation and program testing are inevitable, but the
latter must be preceded by some correctness verification. On the other hand, the
software process exhibits an inherent non-monotonocity, both globally and
locally. Within this formal framework we are able to state, and establish, in a
precise way some facts that are generally belived on intuitive grounds only.
[MCC08/89]
de SOUZA, C.S.; SCOTT, D.R.; NUNES, M.G.V. Enhancing text quality in question
answering systems. 12 p. Eng. E-mail: clarisse@inf.puc-rio.br
Abstract: English abstract not provided.
[MCC09/89]
de SOUZA, C.S.; CARVALHO, E.B.S. Aspects of natural language queries to database
revisited. 9 p. Eng. E-mail:
clarisse@inf.puc-rio.br
Abstract: Natural Language Interfaces for Database enquiry have lost most of
their appeal since discourse theory
entered the field of Artificial Intelligence and proved the need for solid
pragmatic processing in intelligent
computer-human interfaces. However, Database Systems are not likely to disappear
in the near future and man-machine communications in this environment still
calls for improvement. The present paper reports the results of research done
along the line of syntax-oriented natural language processing in DB enquiries,
emphasizing portability issues, and introduces Determination Grammars as a means
to develop DB frontends.
[MCC10/89]
SOUZA, C.S. Gramáticas de determinação: uma abordagem metodológica. 15 p. Port.
E-mail: clarisse@inf.puc-rio.br
Abstract: English abstract not provided.
[MCC11/89]
MATICH, G.H.; CARVALHO, S.E.R. Principios e polêmicas sobre "orientação a
objetos". 37 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: In this work we priliminary try to establish the basic characteristics
of object oriented programming
languages, discussing important related topics, such as TYPES, BINDING and
INHERITANCE.
[MCC12/89]
HAEUSLER, E.H.; FERNANDES, C.T.; RANGEL NETTO, J.L.M. Uma proposta de
arquitetura para ambientes práticos de
especificação de linguagens. 15 p. Port. E-mail: hermann@inf.puc-rio.br
Abstract: We introduce a proposed structure for a kind of software environment,
which we refer to as a language
specification environment (LSE). This proposal follows the trend of general
software development environments,
towards interactive, incremental structures. Due to the reduced development
cycle they support, environments of
this kind offer facilities for partially validating language specification,
through rapid prototyping. We foresee that LSE's, due to the ease of practical
use, will forward the use of formal methods.
[MCC13/89]
LIMA, F.S. Estabilidade e convêrgencia do método da projeção. 51 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: The treatment of numerical stability and convergence for the
projection methods at an increasing number of coordinate (test) functions is
analysed. Some basic propositions on quadratic extreme problems are presented
according to which the correspondent energy approach is viewed as equivalent to
the Rayleigh-Ritz algorithm. Minimal systems are considered and stability
conditions for the projection methods are analysed, concerning the nearly
orthonormed systems, as well as relations between stability and convergence for
the Finite Element Method.
[MCC14/89]
LIMA, F.S. Fórmulas de Green para operadores lineares relacionadas com uma ou
duas integrais de contorno.
35 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: A detailed survey on the construction of the 1st, 2sd and 3rd Green's
formulas is presented. The GauB Theorem is given, to prove systematically all of
the formulas in order to collect them in a set of basic concepts which can be
applied in theoretical and practical development of Continuum Mechanics, Physics
and Computational Mathematics (Finite Element Method). To the variational
formulation for Diaz and Greenberg's method of inclusion a special treatment is
carried out in detail, where Green's Formulas with two boundary integrals are
applied.
[MCC15/89]
ALENCAR, P.S.C.; BUCHSBAUM, A.R.V. Um método automático de prova para a lógica
polisortida deõntica de ações.
22 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: English abstract not provided.
[MCC16/89]
FERNANDES, C.T. A denotational model of types. 18 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A model of types for use in both programming and specification
languages is presented. The denotational
approach is used to build up minimal, closed universes of denotations for all
required values. Standard types consisting of finitary values are given
set-theoretic denotations, whereas just a simplified use of the Scott domain
theory is enough to provide denotations for the remaining constructs, such as
expressions and procedures. This model is applied to the VDM metalanguage as an
illustration, since it has rich type set.
[MCC17/89]
FERNANDES, C.T. Uma taxonomia para ambientes de software. 32 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: A new taxonomy for software environments is presented: the
3-dimensional model. This model is composed
of three levels. The first one refers to the dimensional level representing
three points of view: interaction between Artificial Intelligence and Software
Engineering, covering of methodological paradigms and scale (concerning number
of users and system's size). Each point of view presents a value or state set in
which it can vary. The triple <state,state,state> , where state; belong to the
first dimension, state, to the second dimension and state, to the third
dimension, constitutes one out of mant possible cubes which can model software
environments. The second
level refers to the instantiation mechanisms, which consists of dividing the
group of environment belonging to each cube in smaller classes. The third level
refers to the general model of environments, which consists of establishing the
components politics, mechanisms and structures for each instance. The model is
extended to a n-dimensional model and the structure of the levels is abstracted
to a meta-taxonomy for software environment taxonomies. The proposed
3-dimensional model may be obtained from this meta-taxonomy by instantiation.
[MCC18/89]
REZENDE, M.A.M. HIER - Highly Interactive Expert Resolver: uma ferramenta para
sistemas especialistas. 53 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstract: The Implementation of Expert Systems demands environments providing a
high level of abstraction, as required by the nature of the applications
involved. With the appearance of descriptive languages, such an abstraction has
become less hard to offer. However, many desired resources and facilities are
not promptly available yet. This work describes an auxiliary tool - HIER - to
supply some of these functions, namely "query-the-user", maintenance of
integrity constraints and explanations. Following a brief introduction
describing the contex of Expert Systems together with their characteristics and
main components, some already existing systems are outlined. Next, the Highly
Interactive Expert Resolver is detailed. In the appendix, a list of available
commands and syntax rules, some examples of use and the Prolog code are
presented.
[MCC19/89]
HAEBERER, A.M.; VELOSO, P.A.S.; ELUSTONDO, P.M. Towards a problem-oriented
relational calculus for software
construction. 22 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A calculus for program derivation is presented. This calculus is based
on the algebraic theory of problems.
A problem consists of two sets and a relation between them. The calculus is
based on properties of problems as atomic objects. Several levels of detail can
be uniformly handled within the calculus : from global strategies through design
decisions to local manipulations. An important feature of the calculus is its
ability to capture synthetic aspects.
This is due to the design of the calculus aiming at its extension to cover the
entire software process.
[MCC20/89]
FURTADO, A.L. Some extension to Warren's plan-generation algorithm. 17 p. Eng.
E-mail: furtado@inf.puc-rio.br
Abstract: An extended version of the WARPLAN plan-generation algorithm of D. S.
D. Warren is presented. The extensions cover a few cases outside the scope of
the original version. An example, adopting the abstract data type paradigm, and
the complete listing of the ARITY Prolog implementation are included.
[MCC12/89]
FURTADO, A.L. Treating workspace and SQL facts uniformily in PROLOG. 12 p. Eng.
E-mail: furtado@inf.puc-rio.br
Abstract: The transparent use of a Data Base Management System inside Prolog
programs is motivated. A facility for
this purpose is presented. The paper discusses the details of its this
implementation in ARITY Prolog.
[MCC22/89]
ALENCAR, P.S.C. Uma abordagem lógica para sistemas evolutivos de software. 38 p.
Port. E-mail:
bib-di@inf.puc-rio.br
Abstract:
[MCC23/89]
SCOTT, D.R.; de SOUZA, C.S. Getting the message across: a computational grammar
of text. 21 p. Eng. E-mail:
clarisse@inf.puc-rio.br
Abstract: For text to be correct it must be grammatical, but for text to be good
it must also be effective. In other words, the message must be transparent in
the text; the more transparent it is, the easier it will be for the reader to
understand. In order to achieve message transparency, computational models of
text generation must have access to cognitively motivated text structuring rules
during the planning process. These rules are related to the psycholinguistic and
sociolinguistic factors that affect language processing. They belong to a text
grammar, whose role is to map the desired message onto a text plan. By proposing
the existence of a text plan as an intermediary stage between message and final
text, we argue for a 3-step approach to text generation and show that this
brings about many theoretical and computational advantages over other
approaches.
[MCC24/89]
HAEBERER, A.M.; VELOSO, P.A.S. On the inherent non-monotonicity of software
development: a formal justification. 15 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The software development process goes from a verbalization of the
requirements of a real problem to a final program, perhaps via a formal
specification. Its goal is that the virtual machine described by the program
behaves as an engineering model of the real problem (application concept). Here,
these objetcs, as well as some interconnections among them, are analyzed from a
theoretical standpoint by means of Carnap's Two-Level Theory of the Language of
Science and the Algebraic Theory of Problems. The relation "being-an-engineering-model"
is argued to be synthetic and a disposition, which has interesting consequences
for factorizations of the process. On the one hand, specification validation and
program testing are inevitable, but the latter must be preceded by some
correctness verification. On the other hand, the software process exhibits an
inherent non-monotonocity, both globally and locally. This formal framework
enables us to clarify the status of the objects involved and their
interconnections. We are able to state, and establish, in a precise way some
facts that are generally believed on intuitive grounds only.
[MCC25/89]
PEREZ ALCAZAR, J.J. Bancos de dados dedutivos temporais: uma revisão. 61 p.
Port. E-mail: bib-di@inf.puc-rio.br
Abstract: One of the objectives to intergrate logic programming and databases is
to provide more expressive
mechanisms for the construction and management of information systems. The
integration is particularly powerful if the temporal aspects is added. This
report examines a number of works on the subject, giving special attention to
the Event Calculus proposed by Kowalski.
[MCC26/89]
LEITE, J.C.S.P.; LUCENA, C.J.P. The Rio Workshop on the Software Process. 8 p.
Eng. E-mail: julio@inf.puc-rio.br
Abstract: The Departamento de Informatica of the Pontificia Universidade
Católica do Rio de Janeiro and the Instituto de Engenharia de Software of IBM
Brasil organized the Rio Workshop on the Software Process, to promote a
discussion about the different views of the software development process by
researchers in the area. These discussions were anchored on two presentations
about different approaches to the software development process. One approach
came from the "formal school", represented by Dr. Thomas Maibaum of the Imperial
College of Science and Technology, and the other from the "knowledge based
school", represented by Dr. Allen Goldberg of the Kestrel Institute. Several
researchers, with a formal background, as well as other with a more
praticioner-oriented experience were present at the workshop. The questions and
discussions that emerged during the two-day meeting reflect important practical
and theoretical points for the development of the software area.
[MCC27/89]
SCHWABE, D.; MIZUTANI, E.E. A knowledge-based browser to access complex
databases. 13 p. Eng. E-mail:
dschwabe@inf.puc-rio.br
Abstract:
[MCC28/89]
SILVA, W.T.; MILIDIU, R.L. Algoritmos para combinação de evidências. 43 p. Port.
E-mail: milidiu@inf.puc-rio.br
Abstract: This paper sumarizes all Dempster-Shafer Theory key concepts. It also
analises different ways to represent
belief functions, and shows some heuristics for belief function combination. An
algorithm to combine a bayesian belief function with a list of belief functions
is also described. Finally, Barnett's Algorithm and Shafer & Logan Algorithm are
reviewed, and some enhancements to this last algorithm are proposed.
[MCC29/89]
SILVA, W.T.; MILIDIU, R.L. Algoritmos para combinção de evidências em espaço
hierarquizado de proposições. 56 p.
Port. E-mail: milidiu@inf.puc-rio.br
Abstract: This paper describes a parallel and a sequential algorithm for
evidence combination on a hierarchical proposition space. We assume
Dempster-Shafer Theory approach to uncertainty modeling. Hence, we also
summarize all relevant aspects of this theory necessary on both algorithms
description. Some important properties of hierarchical proposition space are
shown in order to derive our computational schemes. The design of the algorithms
is object oriented.
[MCC30/89]
LEITE, J.C.S.P. Elicitation of application languages. 6 p. Eng. E-mail: julio@inf.puc-rio.br
Abstract: Domain modeling demands that the knowledge of what should be modeled
be available. Acquiring this knowledge or eleciting the domain is recognized to
be a very hard problem. Using the idea that a domain will be represented by a
special language, and using insights from the field of semiotics, we are
investigating the elicitation of application languages. An application language
is a special language aiming to capture the culture of a given social setting of
an application. An application language could be viewed as a restricted domain
language, since the main focus is to capture the observable knowledge in a given
social setting, instead of the knowledge that is valid across social settings.
Our approach to the elicitation of application languages is to empirically
search for a method of acquiring these languages. The objective of this report
is to give an idea of our ongoing research. First results and the problems
encoutered are reported.
[MCC31/89]
SOUZA, C.S. Speech acts in computer-human interfaces. 12 p. Eng. E-mail:
clarisse@inf.puc-rio.br
Abstract: Communication between users and intelligent systems involves a higher
degree of complexity if compared to conventional computer-human interaction (CHI),
specially in terms of the role language plays in the computations
performed by systems. This paper claims that intelligent systems are essentially
linguistic systems and that their
actions are, therefore, intrinsicly related to the notion of speech acts. Within
this frame, basic guidelines for interface design are discussed and an extension
to menu-driven natural language understanding systems is proposed as a means to
deal with speech acts in CHI.
------------------------------------------------------------------------------
1990
[MCC01/90]
CABRAL, R.H.B.; CAMPOS, I.M.; COWAN, D.D.; LUCENA, C.J.P. Interfaces as
specifications in the MIDAS user interface
development system. 15 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: This paper describes an evolving User Interface Development System
called MIDAS (for Merging Interface
Development with Application Specification) which allows interfaces/systems
designers to develop an application-specific user interface interactively, in a
prototyping-oriented environment, while refining the specification of the
intended application itself. The interface/systems designer receives expert
advice on both interface and application software design principles, emerging
from MIDAS' knowledge base, and can also animate the intended user dialogue with
the interface being designed via an extensive set of visual programming aids.
The generated interface can be further customized by the end-user, by flexibly
altering the default appearance of the dialogue scenarios. Furthermore, the
application-specific end-user interface is also knowledge based. Its domain
knowledge covers user modeling and the application domain, in order to adapt
itself dynamically to different degrees of user familiarity with the
application, from novice.
[MCC02/90]
VELOSO, P.A.S.; HAEBERER, A.M. Towards a formal analysis of the software process.
16 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract:
[MCC03/90]
SCHWABE, D.; FEIJÓ, B.; KRAUSE, W.G. Intelligent hypertext for normative
knowledge in Engineering. 11 p. Eng. E-mail: dschwabe@inf.puc-rio.br
Abstract: We present a system that combines hypertext with a semantic
representation of engineering norms. Since the representation is done via a
Prolog encoding of an And/Or Graph, it is possible to discuss the relation
between the execution of the (representation of the)norm and navigation in the
hypertext. The system incorporates an interpretation of the norm by experts, and
it is shown how this interpretation can be regarded also as an hyperview onto
the hypertext.
[MCC04/90]
BIGONHA, M.A.S. O papel da representação do conhecimento na construção de
sistemas especialistas. 38 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This text characterizes knowledge representation role in the context
of expert systems and the decisions to be taken to select the most adequate
representation for a peephole optimization. It presents a general aspects of the
most relevant topics in the development of Knowledge-Based Systems, such as,
techniques to represent knowledge, the methodology for data aquisition,
languages and tools. In addition, it shows, through an example, how the captured
knowledge from a code optimization expert can be represented using one
commercially available tool.
[MCC05/90]
CABRAL, R.H.B. O modelo de design do sistema MIDAS de desenvolvimento de
interfaces de usuários. 13 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstract:
[MCC06/90]
SILVA, S.B. Hierarquias de memoria. 35 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract:
[MCC07/90]
SILVA, S.B. Perfil de referências de um programa a memória. 33 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract:
[MCC08/90]
GUARANYS, P.Y.; LUCENA, C.J.P. New approach to user modelling based on double
stereotypes. 21 p. Eng. E-mail:
lucena@inf.puc-rio.br
Abstract: The quality of interactive computer systems can be evaluated on the
basis of the system's ability to adapt itself to specific users. The system must
be able to respond or react based on the knowledge it is capable of
acquiring-about a given user. A representation of the user's knowledge expressed
in a way which is appropriate to the systems use is called a user model. This
paper presents a new method for the construction of a user model which can be
used as part of a generic interactive system by a generic user. According to the
method, the user model is the result of dynamic transformations of a static
double stereotype. A first class of stereotypes represents the estimated
user's knowledge about concepts implemented by the system. A second class
structures the knowledge about system's concepts in such a way that it is
possible to make inferences about whether the user knows a given concept given
that he/she knows another concept. The level of knowledge used by both classes
is determined by means of an experiment. As the software gets to be used the
model for a specific user departs from the stereotypes and gets closer to a good
representation of the current user with whom it wants to carry on an adequate
interaction.
[MCC09/90]
HAEBERER, A.M. Analisis comparativo de la teoria sobre condicionales
contra-factuales. p. Esp. E-mail:
bib-di@inf.puc-rio.br
Abstract:
[MCC10/90]
RODRIGUEZ, N.R. Tratamento de exceções. 40 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: The word "exception" is used by many authors to describe certain
situations which arise during the execution of a program. In this report we
explore the different visions of the term which can be found in the literature
and the maun solutions proposed for the handling of these situations. The need
and role of linguistic machanisms specially defined for the handling of
exceptions is also discussed.
[MCC15/90]
MERÉ, M.C. Model of ptyxes for sum and empty types. 37 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In Chapter 12 of a forthcoming book, Girard presents the model of
Ptyxes of finite types as a model of a variant T"of Godel's T (a typed
Lambda-calculus with primitive recursion). In Pappinghaus this model is extended
to a typed lambda-calculus with ordinal structure (sup terms). In present paper
we show how to extend the model of Ptyxes of finite types to a typed
lambda-calculus which also includes sum and empty types.
[MCC12/90]
HAEBERER, A.M.; VELOSO, P.A.S. Partial relations for program derivations -
adequacy, inevitability, and expressiveness. 53 p. Eng. E-mail:bib-di@inf.puc-rio.br
Abstract: A framework for specifying, and reasoning about, problems and programs
is presented. This framework is based on partial binary relations (relations
together with two carriers sets) and underlies the semantics of any formalism
for reasoning about programs together with preconditions. An algebraic calculus
is developed and argued to be adequate for program derivation by means of formal
manipulation of expressions. Its expressive power is shown to encompass that of
first-order logic, thereby solving Tarski's problem on the expressiveness of his
calculus of binary relations. Although our problem-theoretic formalism is based
on partial binary relations, our considerations are perfectly general.
[MCC13/90]
BIGONHA, M.A.S. Otimização de código usando técnicas de Inteligência Artificial.
36 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: This technical report presents a proposal to develop a peephole
optimization generator based on Artificial Intelligence techniques. In this
paper, with the objective to provide a context for the problem for which we
propose to investigate a solution, an overview of the methodologies for compiler
construction is presented, and the role of the compiler generator systems in the
development of compilers discussed. This work stresses the important aspects of
the use of optimizers in the process of compilation and the current
status-of-the-art with respect to most recently
projected tools, giving emphasis on peephole optimization. It is also shown a
general overview of the Artificial
Intelligence Area and some of the current research trends in the development of
peephole optimization using A.I.
techniques and methodologies.
[MCC14/90]
BIGONHA, M.A.S. Linguagens para descrição de arquitetura de computador. 47 p.
Port. E-mail: bib-di@inf.puc-rio.br
Abstract: The subject of this paper is to present a comparative study of
different description languages for real computer architecture found in the
literature. This paper begins with the presentation of some code generation and
optimization systems that make use of machine architecture description. It also
presents a brief description of the most important issues in the MC68000, VAX e
PDP-11 architectures with the objective to make easier to follow the examples in
this paper. This work discusses the notation for register transfer used in the
instructions description in one of the approaches presented here, and shows how
this notation can be used to describe machine architecture. In addition, it is
presented and evaluated some other notations used in the description of
machines. The conclusion drawn from this work is that even though it is
difficult to achieve consensus about which language is the most adequate, some
characteristics of the language help in the selection process.
[MCC11/90]
de SOUZA, C.S.; NUNES, M.G.V. O componente de realização na geração automática
de textos: efeitos da conciliação.
14 p. Port. E-mail: clarisse@inf.puc-rio.br
Abstract:
[MCC16/90]
CABRAL, R.H.B. Interfaces inteligentes: conceituação, taxonomia e arquitetura de
suporte. 29 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: This work attempts to identify the components needed to characterize
an interface as intelligent. It focusses on the dialogue types and on the
sources of knowledge needed by an interface, while discussing some relevant
aspects on user interface management, through an analysis of the current
literature. Furthermore, it proposes a minimal architecture for intelligent
interfaces and a taxonomy, albeit incomplete, of systems and approaches found in
the literature.
[MCC17/90]
HAEBERER, A.M.; BORIA, J.L.; KVITCA, A.M.; COBO, H.; RIESCO; D.E.; ROQUE, L.E.;
MONTEJANO, G.A.; GRILO, S.B.; SCHUBERT, E.G. Micro-Ethos: an experimental
method-based environment generator. 11 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: We describe -ETHOS, an experimental environment generator which
supports the specification of method-based environments. We provide the
definitions for the different methods' parameters such as the external syntax of
tools, their inter-relationships and the rules governing the heuristic of their
application to an specific problem domain. The kernel of -ETHOS is a graphical
editor for graphs which allows for the definition of a semantic network for the
instantiation of editors. this is achieved through changes in definitions,
including those that support the relationships between tools. It is shown in
this paper that many interesting method-based environments can be produced
through the process embodied in -ETHOS. In particular the following environments
are built: data-flow diagrams, data-flow diagrams with abstractions,
control-flow diagrams, entity-relationship diagrams, state-transition diagrams,
office-automation semantic network, Petri-nets, text editors, execution graphs,
symbolic data-flow diagram processors,
symbolic Petri-nets processors, and a data-flow virtual machine for matrix
calculus.
[MCC18/90]
VELOSO, P.A.S.; HAEBERER, A.M. Towards a new algebra of first-order logic:
binary relations resumed. 11 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract:
[MCC19/90]
FISCHER, R.; FEIJÓ, B. Genesys - a new hybrid solid modeling system. 4 p. Eng.
E-mail: bruno@inf.puc-rio.br
Abstract: Solid modeling systems are always central modules of CAD systems. The
degree of robustness of this type of software depends on the principles
underlying its design. This work presents a short description of the
architecture and the modeling process of a new hybrid solid modeling system
called GeneSys. The concept of full perspective modeling is also presented.
[MCC20/90]
FEIJÓ, B.; FISCHER, R.; DREUX, M. Better criteria for the development of solid
modeling software. 9 p. Eng.
E-mail: bruno@inf.puc-rio.br
Abstract: The criteria underlying the design of a Hybrid Solid Modeling System,
called GeneSys, are presented. The
system's innovative aspect consists in adopting the criteria pointed out by the
recent research on Intelligent CAD (ICAD). The paper focuses on the question of
cognition and 3D perception. The criteria to measure the quality of the design
is also described. The experience with the development of GeneSys, the authors
belive, provides an extra insight into question of writing robust engineering
software.
[MCC21/90]
SCHWABE, D.; CALOINI, A.; GARZOTTO, F.; PAOLINI, P. Hypertext development using
a model-based approach. 37 p. Eng. E-mail: dschwabe@inf.puc-rio.br
Abstract: Hypertext development is still, for the most part, at the "handcrafting"
level, where each hypertext document must be hand-designed. We present a
compiler which takes hyperdocuments designed using a model-based approach and
generates stacks executable in HyperCard. This compiler is implemented is
standard SQL over a relational database representation of a hyperdocument
designed using the Hypermedia Design Model (HDM). The compiling approach, even
though illustrated with HDM, can be used with many "structured" design
methodology.
[MCC22/90]
GARZOTTO, F.; PAOLINI, P.; SCHWABE, D. HDM: a model-based approach to hypertext
application design. 53 p. Eng.
E-mail: dschwabe@inf.puc-rio.br
Abstract: Hypertext development should benefit from a systematic, structured,
development, especially in the case of large and complex applicatins. A
structured approach to hypertext development suggests the notion of
authoring-in-the-large, which allows the description of overall classes of
information elements and navigational structures of complex applications at a
high level of abstraction, without much concern with the contents of particular
nodes, and in a system-independent manner. This approach is based on the belief
that systematic and rational structural design decisions about a hypertext
application can and should be made before the actual hypertext is ever written,
so that coherent and expressive hypertext webs can be designed-in instead of
added-on. HDM (Hypertext Design Model) is a first step towards defining a
general purpose model for authoring in the large, being innovative in discussing
both static and dynamic hypertext modelling under this perspective, HDM
specifications can be either used only as a high level application requirement
specifications or as a basis for (semi) automatic generation of actual
applications. A formal definition and examples of usage of HDM are also included.
[MCC23/90]
GARZOTTO, F.; SCHWABE, D.; PAOLINI, P. New perspectives for hypertext
applications using model-based design. 33 p. Eng. E-mail: dschwabe@inf.puc-rio.br
Abstract: We describe a novel use of hypertext within hybrid application - those
involving the integration of formal and informal knowledge about an application
domain. This integration is achieved using a model-based approach to hypertext
application design; this model can be used even if no integration with formal
knowledge is needed. As a consequence of this approach, we also propose a
structured approach to hypertext application design that aims at defining the "structure"
of the hypertext before the actual contents of the nodes are defined.
-----------------------------------------------------------------------------------------------------------------------------------------
1991
[MCC01/91]
MAFFEO, B. ESML (Extended Systems Modeling Language) - uma revisão da
apresentação, estrutura, notação e conteúdo. 63 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: ESML (Extended Systems Modeling Language) has been reviewed, aiming at
a more clear, structured and systematic presentation of its concepts, as well as
the formation and execution rules of the Activities Schema (Transformation
Schema as is designated in ESML). We expect that the result of this effort may
increase the insigh of the professional who wants to employ this representation
language to model real-time systems. Some existing ambiguities in the original
presentation were removed and some important concepts, formely contained in the
Ward and Mellor previous publications, were explicitly represented. Special care
was exercised in reference to terminology.
[MCC02/91]
IERUSALIMSCHY, R. A method for object oriented specification with VDM. 28 p.
Eng. E-mail: roberto@inf.puc-rio.br
Abstract: This paper presents a new specification method for Object Oriented
Programming. The method is an extension of the method proposed by Jones, using
VDM. The main additions are mechanisms for inheritance and nesting of
specifications. Inheritance is used to achieve reusability, as supported by the
object oriented paradigm, while nesting allows a better modularization of the
state space of a system.
[MCC03/91]
IERUSALIMSCHY, R. The O=M programming language. 27 p. Eng. E-mail: roberto@inf.puc-rio.br
Abstract: O=M is an object oriented prograamming language designed to achieve
compatibility between Object Oriented Programming and Abstract Data Types. The
main characteristic of the language is a complete identification between the
concepts of Object and Module. This feature allows the language to have entities
which, like objects, are dynamically created and manipulated, have inheritance
and late-binding, and at the same time, like modules, can export types, have
separate specifications and implementations, and support nesting facilities.
Specifically, the dynamic manipulation of objects which export types gives the
language a high degree of polymorphism.
[MCC04/91]
KISCHINHEVSKY, M. A multilevel conjugate gradiente method. 23 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: This text discusses attempts to put together convenient properties of
Conjugate Gradient and Multigrid
Methods for the numerical solution of liner systems arising from the
discretization of certain partial differential equations. Some trials which one
finds in the literature are reviwed, and a new proposal is made that intends to
form a competitive alternative to the conventional solvers.
[MCC05/91]
BUCHSBAUM, A.V.; PEQUENO, T.H.C. Uma família de lógicas paraconsistentes e/ou
paracompletas com semânticas recursivas. 59 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: A family of paraconsistent and/or paracomplete calculi with recursive
semantics is presented. The families of calculi CI, PC and NAL are
reconstructions of the calculi C1, P1 and N1 of da Costa. They have been
developed to allow recursivity and more natural forms for explaining the
paraconsistent and/or paracomplete negation. The paraconsistent calculus CEI is
a monotonic basis suitable for the reasoning by defaults.
[MCC06/91]
VERVLOET, W.J. As tabelas de símbolos e as linguagens orientadas a objetos. 56
p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: Symbol tables (ST's) play an important role in the construction of
compilers, interpreters and other systems that parse source code. In this report
the requirements for ST's in object oriented environments are discussed, and ST
implementations for the programming language TOOL is presented. The use of
aggregate structures to simplify the implementation of some ST functions is also
shown. Performance considerations are presented.
[MCC07/91]
ANDRE, A.A.; MAFFEO, B. Projeto ("design") na área de métodos estruturados:
transformando redes em hierarquias.
34 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This work present a study in the Structured Methods Area which aims at
the design of systems. Strategies to transform a network schema to a
hierarchical schema are presented, as well as many criteria to the styructured
chart refinement. A major concern during this study was to indicate the
necessity of avoiding possible distortions when this transformation is made.
[MCC08/91]
SANCHEZ, M.L.A.; MAFFEO, B. Projeto ("design") orientado a encapsulamento de
dados e a troca de mensagens entre
subsistemas autônomos. 53 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This work presents a model of Software Design based on "Information
Hiding and Exchange of Messages between Independent Subsystems". This model is
top-down and permits the partitioning of a Complex System in more simple
Subsystems. One or more of these Subsystems can be reused by other systems that
have to perform similar functions. The Incremental Development Strategy is
facilitaded, allowing a lower response time by the development team. This
strategy permits the production of operational intermediate versions which may
be employed by end users and consequently generates a better interaction between
users/clients and developers. In general, the final version tends to better
satisfy the end user.
[MCC09/91]
SANCHEZ, M.L.A.; MAFFEO, B. Gerência de projetos ("design") orientado a
encapsulamento de dados e a troca de mensagens entre subsistemas autônomos. 39
p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: This work represents a proposal to what phases a Systems Development
Process should have, with focus on Software Development, and a management (Tean
Organization, Quality Assurance etc.) model to the applied at each step of the
process. We assumed that the management model of a project is strongly
influenced by the method used in the development model as a whole. The
management model is based on Design Oriented to Information Hiding and Exchange
of Messages between Independent Subsystems, and this facilitates the Reusability
of Subsystems previously developed and the Incremental Development Strategy.
[MCC10/91]
PRADO, A.F.; LUCENA, C.J.P.; LEITE, J.C.S.P. Registro de desisões e
justificativas de desenho em software projetado com a metodologia JSD. 14 p.
Port. E-mail: lucena@inf.puc-rio.br
Abstract: Design decisions are present everywhere in the software process, but
most of them is lost as the final artifact is delivered. This article describes
an integration of Pott's model of design decisions to a process oriented
description of Jackson System Development (JSD). The integration occurs in the
context of JSD/PUC, a case tool for JSD.
[MCC11/91]
RITTO, A.C.A.; MAFFEO, B. Definindo o problema a ser tratado por um sistema
computacional - o modelo do contexto. 101 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This work describes a set of instruments (tools and techniques),
developed in the area of Structured Methods, aiming at achieving of a complete
and precise specification of the requirements for a Computational System, that
is, a definition of the problem which must be solved by the system.
[MCC12/91]
FISCHER, R. Formas de representação para objetos tridimensionais. 163 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstract: The use of Solid Modeling Systems represents a major breakthrough in
the integration of digital systems into human living. Their power relies on the
ability of understanding the nature of physical objects when described by an
appropriate representation scheme. This work focusses on the development and
analysis of representation schemes for manifold objects in the context of Solid
Modeling Systems. The content of this work is organized into two parts. The
first major part, briefly presents a survey on geometric modeling systems field
and introduces a framework for the evaluation of representation schemes. The
second part uses that framework to describe and compare all the
well-known representations.
[MCC13/91]
VERVLOET, W.J. Um mapeamento de JSD para orientação a objetos. 31 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstract: Object oriented programming models are becoming increaseably popular
both in the academic and professional comunities. A mapping from the procedural
model proposed by Michael Jackson (JSD) into an object oriented model is shown.
The areas covered and the adequacy of both models are discussed.
[MCC14/91]
LUCENA, C.J.P.; LEITE, J.C.S.P.; FERNANDES, J.R.; GHEINER, M.; PRADO, A.F. JSD/PUC:
um ambiente de software experimental para estudo do processo de automacao de
desenvolvimento de software. 32 p. Port. E-mail: lucena@inf.puc-rio.br
Abstract: The present paper deals with the study of the automatization of the
software development process which is instatiated to the JSD methodology. The
environment's architecture is based upon a process program expressed in the
Osterweil style. This process program integrates the methods that constitute the
JSD methodology. The paper also adjusts Pott's generic model for design
representations to allow the record of decisions and the capture of the
reasoning of a specialist that uses the experimental environment. This last
feature aims at supporting reuse and maintenance practices in the JSD/PUC
environment.
[MCC15/91]
SILVA, M.T.M.P. Interação com sistemas de informação baseados em conhecimento.
25 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper gives a critic analysis of the ongoing tendencies on
application development environments, including those of Knowledge Based
Information Systems (KBIS). It analyses trade-offs among design options, in the
light of the present concepts of user centered design. The dependencies between
the internal structure and the user interface are enphasized. Natural Language
is advocated to be the ideal meta-language for system interaction in the working
environment.
[MCC16/91]
RICHTER, G.; MAFFEO, B. Towards a rigorous interpretation of ESML - Extended
Systems Modeling Language. 38 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A graphics-based language known as extended systems modeling language
(ESML), which is an extension of the data flow diagram notation for representing
control logic in models of real-time systems, is analysed and summarized aiming
at a rigorous interpretation of ESML symbols and their combinations. Based on
elementary and compact or "high-level" Petri nets (PN), for which a succint
introduction is given, formal foundations for ESML, in particular for its
transformation schema (TS) notation, are proposed. Translation principles as
well as examples of usual transformation and flow patterns are presented in TS
notation and PN notation. The obtained PN models can be executed due to their
formally defined "token game" which includes concurrency of events and values as
tokens. This permits a rigorous analysis of the dynamics of real-time systems
with signals, prompts and data flows of various kinds included in a single
formalism. The conclusions list general features of the approach relevant to its
application
and indicate further research tasks.
[MCC17/91]
COWAN, D.D.; IERUSALIMSCHY, R.; STEPIEN, T.M. Constructing composite interactive
documents from interactive components. 12 p. Eng. E-mail: roberto@inf.puc-rio.br
Abstract: Integration of Interactive applications is usually done by
cut-and-paste methods, importing documents from one application into another.
This paper proposes a new concept, called "hole", to achieve this integration,
through reuse of components of interactive applications. A hole is a part of a
document which is managed by an external program. Each hole has an associated
script, that coordinates the behavior of the hole and its connected application
program. The paper also discusses how programs should be structured to
facilitate this integration, and shows some examples of hole-scripts to solve
some typical integration problems. A prototype of a text editor supporting holes,
written in Smalltalk, is currently running in our laboratory.
[MCC18/91]
LUCENA, C.J.P.; TAKAHASHI, E.T. A anatomia de um ambiente de desenvolvimento de
software. 46 p. Port. E-mail:
lucena@inf.puc-rio.br
Abstract: This paper attempts to justify the role of software engineering
environments as the only alternative to the solution of the problem of software
productivity. The paper also presents the design of a sample environment called
ADES whose functionality and architecture are described at a level of detail
that allows the simulation of its operation. Software Engineering Environments
which are software systems at least as complex as operating systems are still
not familiar to the computer science community. The environment is simulated
while used to procedure a particular
application by a team of specialists that uses a realistic development
methodology. The text tries to convey the idea that the manageability provided
by environments such as the one described is the only conceivable solution to
the problem of effective production of software systems.
[MCC19/91]
KISCHINHEVSKY, M. On the numerical solution of ordinary differential equations
with cyclic methods. 15 p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract: This is a report on the development of an efficient implementation of
a numerical solver for cyclic methods of Adams type. It is built by means of
successive applications of strategies for implicit methods, row by row of a
systems of difference equations. Several Adams predictors are available and
adjustable step size is provided. Strategies for error estimation at each step
are also discussed, leading to a computationally inexpensive package,
which is tested for some low order methods.
[MCC20/91]
HAEBERER, A.M.; VELOSO, P.A.S.; MAIBAUM, T.S.E.; COELHO, H.P. Subsídios para a
formulação de um meta-modelo coerente do processo da programação. 32 p. Port.
E-mail: bib-di@inf.puc-rio.br
Abstract:
[MCC21/91]
CARVALHO, R.L.; VIEIRA, N.J. Linear resolution, definitions and functions. 19 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In this paper we analyse the use of definitions and functions in the
context of proof procedures based on the resolution principle (particularly
linear resolution). By leting the proof procedure "knowing" what formulas are
definitions and what predicates denote functional relations, it can take
advantage from this in order to improve its performance.
[MCC22/91]
CARVALHO, R.L.; VIEIRA, N.J.; OLIVEIRA, C.M.G.M. SAFO: an environment for logics.
17 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: SAFO is an environment for the programming of deductive systems. There
are two operational levels: (1) procedural level which consists of a logical
programming language, akin of PROLOG, and (2) a general theorem prover. The
interaction of this two levels, plus the existence of several bases, make
possible the definition of "reasoning agents", i.e. the definition of different
logics.
[MCC23/91]
CARVALHO, R.L. Abstract semantical systems. 36 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: In this work we introduce a new approach to the study of semantical
systems. traditionally the study of these systems have covered only those
semantical systems whose languages are formal and whose models are relational
structures. Here, both languages and models are classes, moreover there is no
dependency on foundational considerations. The concepts of "theory", "worlds",
"semantical consequences", "negation" and "completeness" are
presented from strictly semantical point of view. Some of the results obtained
subsume similar results found in the Theory of Models.
[MCC24/91]
FUKS, H. ACCORD: a framework for dialogue representation using commitment. 44 p.
Eng. E-mail: hugo@inf.puc-rio.br
Abstract: ACCORD, a framework for dialogue representation systems using
commitment is proposed as a means for representing some of the negotiation
aspects characteristic of cooperative work. A two-tiered framework comprising a
Commitment Calculus and a Dialogue Action Component is developed. The modelling
of each participant's range of
information about the dialogue, and its interaction with the others, is
represented by commitments generated during the conversation process. Each
participant has a commitment store where its commitments are placed. The
Commitment Calculus is developed for dealing with the consequences of having
commitments. The Dialogue Action Component dictates the dialogue's etiquette,
and the way that the conversation affects and updates the commitment stores. The
notions of cliches, scripts and patterns of cooperative reasoning for the
provision of conversation stereotypes are outlined.
[MCC25/91]
HAEUSLER, E.H. On the theorem prover based on game-theoretic semantics. 20 p.
Eng. E-mail: hermann@inf.puc-rio.br
Abstract: The Game-Theoretic approach for semantics was created with the purpose
of providing meaning to formulae where the traditional semantics have some
drawbacks. Hintikka, however, used this approach to provide an alternative
semantics w.r.t. the traditional one. The nice feature of this semantics is its
quasi-algorithmic specification. This feature has raised some ideas around
theorem provers construction. This report describes a theorem prover based on
game-theorectic semantics and shows its soundness. However, as a conclusion of
this work some proof-theoretic reasons are pointed out in order to show the
inherent incompleteness of this kind of theorem provers when they implement
fully the symmetry of the game, that is, the power of proving either the
formulae or its negation without submiting each of them (only the formulae is
submited).
[MCC26/91]
HAEUSLER, E.H.; PEREIRA, L.C.P.D. A denotational semantics for an arbitrary
level typed Lambda-Calculus. 30 p. Eng. E-mail: hermann@inf.puc-rio.br
Abstract: The aim of this work is to provide a denotational semantics for an
arbitrary level Lambda-Calculus, i.e., a typed Lambda-Calculus which has rules
as types. This systems is shown to be Curry-Howard isomorphic to a Natural
Deduction system, where not only assumptions, but rules, can be discharged.
[MCC27/91]
RITTO, A.C.A.; MAFFEO, B. Funções do gerente de desenvolvimento de sistemas -
algumas reflexões. 14 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: The managerial activity requires the consideration of several aspects
which not only has a high subjective content but may also be conflicting. This
work, related to the case of Informatics, presents some ideas concerning the
function of the manager. Some relevant characteristics, common to other
productive areas, are highlighted and it is pointed out that their managerial
difficulties are treated under the scope of Administration Theory. It is
indicated that more practical Research and Development efforts concerning the
Product and the Process of Informatics are needed,
aiming at bringing this area, as the traditional Engineering disciplines were
brought, to profit from the more recent achievements associated to the theory
and practice of the Administration of Projects area.
[MCC28/91]
LEITE, J.C.S.P.; PRADO, A.F. Design recovery a multi-paradigm approach. 13 p.
Eng. E-mail: julio@inf.puc-rio.br
Abstract: One of the reutilization aspects that is major concern is how to get
old code and turn it into a reusable asset. Our article proposes and analyzes a
multi-paradigm approach to the problem of Design Recovery. Design Recovery is
the first step in turning old code into a resuable product. Our aproach is being
used in a special kind of old code, the Draco Prototype, a system that
implements the concept of reusable components to the point of achicving
reusability of Analysis, Design and Code. In recovering the Draco design, we
have used Inspections, JSD, and Prototyping. The combination of those different
paradigms is analyzed in detail and the results are reported.
[MCC29/91]
LUCENA, C.J.P.; LEITE, J.C.S.P.; SCHWABE, D.; FUKS, H. A research agenda on
software design. 8 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: The present report describes the joint research interests of the
authors in the form of a research agenda that refers to topics that are current
research projects of their graduate students. Their common investigation centers
on the upstream design of software system that requires the representation of a
diverse network of design information. This network encompasses all data
relevant to the design process including postulated alternatives, their
resolution through decisions and rationale that ultimately leads to commitments.
Attention to the upstream has a significant impact on representation
requirements and the ideas developed about general aspects of the design process
are evaluated experimentally in environments that suport different design
representations. The design process representation is itself a research topic
since it cannot be easily decoupled from the policies and procedures within the
environment in which it is embedded. Four aspects of the software design problem
are addressed by the author's research agenda: knowledge about design, the
design product, design history and design justification and cooperative design.
------------------------------------------------------------------------------------------------------------------------------------------
1992
[MCC01/92]
LAUFER, C.C.; FUKS, H.; SCHWABE, D. ACCORD: representação de clichês de
conversação para cooperação. 15 p. Port. E-mail:hugo@inf.puc-rio.br
Abstract: Cliches - conversation stereotypes - are state transition machines
that control the sequencing of dialogu events in a conversation between two
participants. The notion of contract - mapped to Winograd's Conversation for
Action diagram - is presented as an example of the framework's ability for
representing conversation cliches for cooperative work.
[MCC02/92]
RIDOLFI, L.F.G.G.M.; FUKS, H.; SCHWABE, D. ACCORD - máquina básica. 30 p. Port.
E-mail: hugo@inf.puc-rio.br
Abstract: This work presents the basic machine of ACCORD - a framework for
dialogue representation using commitment. ACCORD comprises a Dialogue Action
Component (DAC) and a Commitment Calculus (CC). DAC is involved-with dialogue
control and with commitment storage and manipulation. CC deals with the
consequences of having commitments, inferring new commitments from the ones
assumed as the dialogue evolves. The basic machine was developed within a rule
based system, implemented in prolog.
[MCC03/92]
BATISTA, T.V.; SANTOS, H.R.A.; FUKS, H. Cooperatividade na manipulação de
documentos multimídia. 20 p. Port. E-mail: hugo@inf.puc-rio.br
Abstract: A Conversation Management System is proposed for coordinating the
conversation flow among the participants of a teleconference. It is a menu based
environment, modeled on a negotiation cliche. The system uses ACCORD's dialog
primitives, which provides it with a dialog structure and keeps track of the
commitments generated during the negotiation process.
[MCC04/92]
DUARTE, R.C.; FUKS, H.; LUCENA, C.J.P. Software design cooperativo: um estudo de
caso. 18 p. port. E-mail: hugo@inf.puc-rio.br
Abstract: Software design is a typical cooperative activity. A software team
consists of a group of people, performing different functions, each one with its
specific responsibilities, communicating and cooperating with the other members
of the group. This work points out some of the cooperative aspects of a software
team at work. They were observed
and recorded during software design sessions. A technique for observation and
analysis was developed and applied to a case study.
[MCC05/92]
MATHIAS, A.G.; FUKS, H. Resolução de conflitos e trabalho em grupo. 29 p. Port.
E-mail: hugo@inf.puc-rio.br
Abstract: Initially, some conflict detection resolution methods are presented.
Then is shown the importance of a better understanding of conflict for software
engineering. Finally, some conflict resolution models are presented.
[MCC06/92]
CARVALHO, S.S.; FUKS, H. Groupware: a incorporação de aspectos sociais ao
software. 23 p. Port. E-mail: hugo@inf.puc-rio.br
Abstract: Group interaction - especially its sociological aspects - and the
possibilities and consequences of using groupware in the context of
organizations are presented. The social processes that such kind of software has
to incorporate are studied.
[MCC07/92]
SILVA, S.D.; FUKS, H. Sistemas de informação de escritório usando Redes de Petri.
31 p. Port. E-mail: hugo@inf.puc-rio.br
Abstract: Offices are Open Systems. Office activities demand cooperative
oriented information systems. Cooperative systems and the desired aspects of
intelligent man-machine dialogues are investigated. Petri Nets are used to
represent the dynamic aspects of the interaction process in a cooperative
environment.
[MCC08/92]
TRALES, P.R. Tópicos especiais sobre os sistemas de computação algébrica. 219 p.
Port. E-mail: bib-di@inf.puc-rio.br
Abstract: In this work a critical study is performed on the computer algebra
systems implemented in Lisp and C most widely in use. Besides disseminating the
area, the motivations is contributing to the best use of available software
capabilities and potentialities. Generations and families of this kind of
software are presented, together with
specific habilities, sintax forms, equipments, problems and bugs among other
comparative analyses. Moreover topics about other systems and sugestions for
their applications according to users interest are considered.
[MCC09/92]
BIGONHA, M.A.S. Esquemas de escalonamento de instruções para a arquitetura RISC/6000.
33 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: Well-designed instruction-scheduling algorithms are essential to the
performance of optimizing compilers. They are used to reduce possible run-time
delays for the compiled code. The goal of this paper is to present techniques
for instruction-scheduling within the scope of and beyond basic blocks, i.e.,
straight-line sections of code. In order to establish the proper context in
which these techniques are applied, this paper presents a description of
the architecture and machine design of the IBM RISC System/6000* processor. The
text presentes an overview of the most important projected decisions related to
this matter as described in the january 1990 edition of the IBM Journal of
Research and Development. The paper also presents the machine organization,
programs, and storage facilities that characterize this new family of
superscalar RISC workstations and servers.
[MCC10/92]
BIGONHA, M.A.S. Geração e otimização de código: levantamento dos problemas e
restrições impostas pelas arquiteturas RISC e indicativos de soluções. 26 p.
Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This paper presents important problems related with RISC architectures
that directly affect the generation of code generator systems and discusses the
approaches proposed to solve them. Among these problems, we have the question
about the interdependence between register allocation and instruction scheduling,
the branch instruction, the restrictions imposed by pipelined processors and the
phase ordering problems. This text concludes showing the
disadvantages and advantages of RISC machine, and then compares the RISC and
CISC architectures.
[MCC11/92]
SANCHEZ, M.L.A.; PLEHWE, A.K.v. Modelo de implementação de um terminal tático
inteligente. 72 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This work presents the Implementation Model of an Intelligent Tactical
Console. This model considers the system as a group of services executed by
Independent Subsystems which interact exchanging messages.
[MCC12/92]
IERUSALIMSCHY, R. A denotational approach for type-checking in object-oriented
programming languages. 28 p. Eng. E-mail: roberto@inf.puc-rio.br
Abstract: This paper proposes a method to check type safety in object-oriented
programming languages. Our first step is a formal definition for "type safety".
Following the object-oriented tradition, we assume that the only visible part of
an object is its interface, that is, the operations it exports. This leads us to
define type error as the sending of a message to an object that has no method
for it. A type safe language is one that can ensure, at compile time, the
absence of such errors during the execution of a correct program. Our next step
is the definition of an illustrative language, called School. School has
multiple inheritance, recursive types, late-binding, etc. Moreover, it has
separate hierarchies for types and classes: subtyping means compatible
signatures, while subclassing means code reuse. Following an informal
description, we present a complete denotational semantics for our language. The
main section of the paper is a formal proof that correct School programs run
without type errors, that is, School is a type safe language. We start defining
correct memories, which are memories where all variables have objects with
appropriate types, and proceed showing that correct expressions and methods
preserve memory correctness. Together with this, we prove that, in a correct
memory, an object always has methods to handle the messages it can receive.
Although we have applied the method in an illustrative language, it can as well
be applied to most OOPLs in the Simula tradition, like C++ or Eiffel. Obviously,
as such languages are not well typed, the complete proof would be impossible.
Nevertheless, the formalization of those concepts can bring light to many hidden
aspects of a language.
[MCC13/92]
PEREZ ALCAZAR, J.J.; LACERDA, M.; LANZELOTTE, R.S.G.; MELO, R.N. Uma extensão de
uma linguagem para bancos de dados funcionais LBF+. 64 p. Port. E-mail: rubens@inf.puc-rio.br
Abstract: This report presents a data base programming language based on the
DAPLEX language. It is an extension of the functional data base language called
LBF, with some characteristics of the object-oriented database systems
defined by Atkinson et all.. In this report we also point out the advantages of
the functional model and, specifically, the Shipman proposal and some of the
function model extensions to non-standard aplications are revised. The LBF+
language mixes characteristics from other systems such as IRIS, PDM e O2. The
idea of this proposal is to show a language which allows the user, in a concise
and uniform way, to criate, operate and update his/her database and application
programs.
[MCC14/92]
SILVA, S.D.; MAFFEO, B. Modelagem conceitual de bancos de dados com Redes de
Petri - um estudo de caso. 40 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: The Entity-Relationship model has been used as a tool for the
conceptual modeling of static properties during the process of designing
database. New applications of database, which require the modeling of dynamic
aspects in addition to the aspects traditionally considered, have motivated the
research of models with the capability of representing concepts such as entities,
their atributes and relationships and the rules and events which affect them or
are affected by them. This work evaluates the use of Petri Nets for the
representation of rules and events at the
conceptual level, as an extension to the Entity-Relationship Model. An
alternative representation is considered which employs Compact Petri Nets to
model both the static and dynamic properties which are relevant in the universe
of discourse. This alternative is presented in a case study format demonstrating
the generation of a homogeneous model for data and functions, with a formalism
which facilitates the mapping of the concepts onto the lower representation
levels.
[MCC15/92]
MERE, M.C.; VELOSO, P.A.S. Runs, conditions and problems: an algebraic approach.
28 p.Port. E-mail: bib-di@inf.puc-rio.br
Abstract: The purpose of this paper is to analyze the algebraic structure of
sets of functional complete subproblems of relations. The motivation was due to
the fact that these functions correspond to the runs of a virtual machine when
fed with data belonging to an application domain. We also discuss the
relationship between the presented structure
and the algebraic structure of partial relations.
[MCC16/92]
BARBOSA, L.F.D.J.; LUCENA, C.J.P. Um prototipador e gerador de interfaces
gráficas por manipulação direta: um modelo baseado em eventos. 31 p. Port.
E-mail: lucena@inf.puc-rio.br
Abstract: Software developers have come to realize that the user interface
paradigm is itself a kind of specification notation that expresses the user's
intent and desires in terms of images, as opposesd to words. The user interface
implicitly defines most of the functional requirements, i.e., specifying the
user interface often suffices to obtain an almost complete system specification.
An environemt is proposed to support this goal, using an event-based methodology
to specify the asynchronous dialogues that exist in an environment that uses
direct manipulation with rapid prototyping. To test the environment an interface
prototyper and generator system was constructed using direct manipulation based
in events.
[MCC17/92]
VELOSO, P.A.S. On the modularisation theorem for logical specifications: its
role and proof. 23 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: This paper examines the role played by the Modularisation Property and
presents a proof of the Modularisatio Theorem for logical specification, i.e.
those presented by a set of first-order sentences of a (possibly many-sorted)
language. The importance of (some version of) the Modularisation Property in
this context has been noted by several researchers, for it may be regarded as
involving the preservation of modular structure under refinements. The
Modularisation Theorem amounts to a basic logical tool guaranteeing this
preservation, in particular providing both composite implementations and
instantiated specifications in a natural and direct manner. The proof of the
Modularisation Theorem presented here is based on two central ideas: Craig's
Interpolation Lemma from logic and the concept of kernel of an interpretation.
[MCC18/92]
HAEBERER, A.M.; VELOSO, P.A.S.; MAIBAUM, T.S.E. Towards formal coherent
meta-models for the software development process. 15 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A theoretical basis and a unifying conceptual framework are essential
for a coherent model of the processes involved in software development. Here we
analyse basic needs of such formal coherent meta-models, which lead to several
levels, for distinct objects and for relating them. These needs stem from formal
reasons, epistemological considerations and heuristic convenience. The formal
reason arise from a precise analysis of the goal of software
development, the epistemological considerations are connected to
non-reductionistic explications, and the heuristic convenience has to do with
instantiating the meta-model to cover various paradigms. We also outline a
multidimensional meta-model of the software development process, which is based
on these general ideas and
centred around logical concepts, such as interpretations between theories, and
an extended cauculus of binary relations.
[MCC19/92]
VELOSO, P.A.S.; HAEBERER, A.M.; BAUM, G. On formal program construction within
an extended calculus of binary relations. 45 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Research reported herein is part of an on-going effort in using
relational formalisms for formal program construction. This paper emphasizes
three main points: first, the distinction among specification and programming
languages and derivation formalisms (as illustrated by the role of intersection):
second, that the construction of a theory of the application, and its expression,
involved in formal program development can, and perhaps should, be distributed
and interwined along the process: third, how derivation insights and rationales
can be captured within a formalism with the goal of reusing them and automating
their applications. Our formalism is based on an extended version of Tarski's
calculus of binary relations, amounting to the addition of relativized
identities and a couple of new operations, rendered natural because the universe
is now structured. This extended calculus has the expressive power of
first-order logic, which makes it appropriate for expressing, and reasoning
about, programs as well as strategies and design decisions. The give a truly
coherent framework, based on the single unifying concept of input-output
relations over structured universes, covering the entire derivation spectrum,
from specifications to programs, both of which viewed as relational terms.
[MCC20/92]
POUBEL, H.W. Adjuncões e a extensão da dedução natural. 31 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: Schroeder-Heister's Natural Extension of Natural Deduction, where not
only formulas but also rules can be discharged, presents a framework for the
treatment of arbitrary n-ary sentential operators. This work shows that the
abstract rules of Schroeder-Heister's Natural Natural Deduction define
adjunctions between cartesian closed categories with finite coproducts where the
objects are rules and morfisms are deductions. More precisely, if is an operator
with in introduction rules, the left adjunct is defined by the sun of these
introduction rules and the comutativity of the adjuntion diagram represent the
Inversion Principle.
[MCC21/92]
STAA, A.v.; LUCENA, C.J.P.; COWAN, D.D. Establishing a precise relationship
between a software developmen environment and software process models. 18 p.
Eng. E-mail: arndt@inf.puc-rio.br
Abstract: Recent research has indicated that software development processes can
be programmed or formally specified. Thus, it should be possible to build a
software development meta environment or shell which can be adapted to specific
process models. Building such a shell presents a technological challenge because
the process
programming language and underlying database or repository must support multiple
software process paradims. This paper presents an outline of Talisman, one
approach to establising a relationship between the software process and the
software environment. Talisman is a software development meta environment which
can be adapted to several process models including the prototype, operational,
transformational and successive refinement or "waterfall" paradigms.
[MCC22/92]
MATICH, G.H.; CARVALHO, S.E.R. Mecanismos de herança em linguagens de programaão:
variedade, evolução e proposta. 30 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This report presents an overview of inheritance discussing also its
relationship to polimorphism, reusability
and incremental modification. In this discussion inheritance topics are
classified in different definition levels. This
classification helps in the understanding of the existing variety of approaches
to inheritance. The evolution of the
inheritance concept and important related questions are also considered. Finally,
a methodology for systems development is proposed, considering several
inheritance alternatives to express the system, from an experimental phase to a
static, optimized phase.
[MCC23/92]
CARVALHO, S.E.R. Exception handling in object oriented languages: a proposal. 13
p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: A mechanism for exception handling in object oriented languages is
proposed. Initially the languge model chosen is described, particularly its "class"
concept. The proposed mechanism combines naturally the semantics of classes with
the semantics of exceptions in conventional languages. The resulting familiarity
is important to conventional programmers trying to embrace object orientation.
[MCC24/92]
COELHO, O.P.; CARVALHO, S.E.R. O uso de classes como unidade de paralelismo. 18
p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: An extension of the class mechanism for the handling of paralelism is
presented. In extended classes, the behaviour of objects operating in parallel
is modeled not only by common synchronous calls (methods), but also by
asynchronous events. The use of generic event destinations further increases the
encapsulation and abstraction properties of extended classes, allowing the free
composition of object with context-free behaviour.
[MCC25/92]
CARVALHO, S.E.R. Tool: a short description. 9 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 platforms. The current
version runs above Microsoft Windows. In this report the programming language
component of the system is summarized. This is an object and event oriented
language, designed to be easily understood by conventional language programmers.
[MCC26/92]
DANTAS, M.A.R.; GHEINER, M.; SARMENTO, A.; CARVALHO, S.E.R. X-NET: uma
linguagem, tres paradigmas. 18 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: X-NET is an object oriented programming language coveering also the
modular (conventional) and distributed programming paradigms. This report
summarized the main language features designed to support those three paradigms.
In particular, the programming units program, model, class and script are
described.
[MCC27/92]
IERUSALIMSCHY, R. A formal specification for a hierarchy of collections. 20 p.
Eng. E-mail: roberto@inf.puc-rio.br
Abstract: This paper presents a formal specifications for a hierarchy of types
similar to the Collection hierarchy
presented by the Smalltalk language. The specification method is an extension of
VDM that supports inheritance
of specifications, with the property that subtypes are behavior compatible with
their parents. this formalism
gives us a clear concept of behavior compatibility, that is used to justify our
hierarchy structure and to compare
inheritance of specifications, adopted here, with inheritance of implementations
adopted in Smalltalk.
[MCC28/92]
KISCHINHEVSKY, M. A direct domain decomposition procedure for elliptic problems.
15 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: This report describes a new parallel solver for linear systems of
equations airsing from the discretization of certain elliptic partial
differential equations. A domain decomposition procedure is generated making use
of the statistical solution of partial differential equations. The new solver is
very well suited for implementation on a loosely coupled parallel environment.
An implementation and an analysis of the algorithm proposed are described for
the case a conjugate gradient solver is used on the subproblems. Numerical
results confirm effectiveness of the procedure.
[MCC29/92]
BARBOSA, E.; MAFFEO, B. Modelagem da essência de um sistema de controle para uma
area de linhas de engarrafamento. 69 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: This work constitutes an application of conceptual tools and
techniques for semi-formal modelling aiming at the construction of the Essential
Model of a real-time system for monitoring and controlling a bottling lines area.
It employs extensions, proposed for the treatment of real-time systems, to
widely used tools and techniques for the conceptual modelling of conventional
socio-technical systems. These extensions were introduced in order to cope
rigorously with the aspects related to a complex systems dynamics while assuring
an easily understandable conceptual model.
[MCC30/92]
COWAN, D.D.; BARBOSA, L.F.; IERUSALIMSCHY, R.; LUCENA, C.J.P.; OLIVEIRA, S.B.
Program design using abstract data views - an illustrative examples. 12 p. Eng.
E-mail: roberto@inf.puc-rio.br
Abstract: Creating new applications by integrating user interface and
application components is a relatively new idea which is currently of wide
interest. A significant part of this problem is clearly defining the separation
between user interface and application components. This paper uses an example to
illustrate a new design methodology based on
the concept of an abstract data view (ADV), a structuring method which cleanly
defines this separation. Both the design and a Smalltalk implementation of the
example are described. Prototypes of this example and several others which use
the ADV concept are currently running in our laboratory.
[MCC31/92]
DURAN, J.E.; BAUM, G.A.; HAEBERER, A.M. A collection of smooth program
calculations using the fork-extended relational algebra. p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract:
[MCC32/82]
BAUM, G.A.; HAEBERER, A.M. On solving universally quantified relational
expressions. p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract:
[MCC33/92]
DUARTE, C.H.C.; IERUSALIMSCHY, R.; LUCENA, C.J.P. On the modularization of
formal specifications: the NDB example revisited. 22 p. Eng. E-mail: roberto@inf.puc-rio.br
Abstract: In this paper we study the formal specification of a DBMS formally
based on the entity-relationship concept. We use the Norman's Database (NDB)
example which has been explored by several authors in the recent literature. The
system's operations and structure are described, by means of techniques, which
extend VDM through nesting
and inheritance. The extensions to the method and the resulting specification
are presented. The advantages of the new approach are justified in the
conclusion.
[MCC34/92]
LEITE, J.C.S.P. A case study on requirements recovery from structured
specifications. 8 p. Eng. E-mail: julio@inf.puc-rio.br
Abstract: Requirements recovery is a process to produce software requirements
from specifications. In order to test a proposed method for requirements
recovery we conducted an experience involving six systems analysts and ten
structured analysis specifications. The data already available several aspects
of both the specifications and the
recovered requirements. We include the raw data in this report.
[MCC35/92]
LEITE, J.C.S.P.; PRADO, A.F.; SANT'ANNA, M. DRACO-PUC: a case study on software
re-engineering. 14 p. Eng. E-mail: julio@inf.puc-rio.br
Abstract: Software engineering is a new approach to software maintenance.
Instead of working on the source code of systems, we work on high level
abstractions and from them 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. This article reports on a domain oriented
re-engineering method and its use in re-engineering Draco, a machine that
produces software by component assembly.
[MCC36/92]
GARCIA, L.S. Interfaces em linguagem natural orientadas por Menus: uma análise
crítica do ambiente. 17 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: In the context of the increasing explanatory demand knowledge-based
systems imposes over interface languages, the natural language appears as an
adequate option. Restricting the input subset through a natural language menus
interface, it is intended to show that building an environment of this kind that
verifies the caracteristics associated with a good interface is possible. In
this article the interface of natural language menus is analyzed at the ligh of
concepts and guidelines of interfaces design.
[MCC37/92]
CARVALHO, S.E.R. Decoupling interface and implementation: the TOOL solution. 24
p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: It is expected that a large portion of the software systems to be
constructed in this decade will involve object orientation, message passing and
graphical user interfaces. Design methodologies for such systems are now being
studied. A typical goal pursued in these methodologies is the separation between
the interface and the implementation of an application. In this report a design
approach providing a high interface-implementation decoupling degree is proposed.
This approach takes full advantages of object orientation, by considering the
handling of asynchronous messages as part of object behavior. The existence of
TOOL, a programming system containing asynchronism at this high level, suggests
the construction of mechanisms for automatic design-program translation.
[MCC38/92]
MERE, M.C.; VELOSO, P.A.S. On extensions by sorts. 18 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: The process of implementing a formal specification on another one is
very important in formal software development and can be described in terms of
simple logical concepts as an interpretation into a conservative extension. An
extension consists of the addition of new symbols and axioms, a simple, but
important, special case being the so-called extensions by definitions. The new
symbols to be introduced correspond to sorts, functions or predicates.
Extensions by the addition of function and predicate symbols are well stidied in
the literature. Our
purpose here is to analyse conservative extensions that introduce new sorts.
This is of importance because it occurs often in implementing formal
specifications, when new sorts are "constructed" from the concrete ones. We
specify and analyse some well-Known sort introduction constructs akin to those
found in programming languages, namely cartesian product, discriminated union,
subsort and quotient. In each case the extension is shown to have unique, up to
isomorphism, expandability and to be conservative; moreover the new sort is
shown to exhibit the desired
behaviour. Also, the new sort is connected to the old ones by means of
conversion functions. Some derived properties are also established.
[MCC39/92]
POUBEL, H.W.; VELOSO, P.A.S. Tipos de dados parametrizados: especificação,
interpretação e implementação. 16 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: Specifications are considered as theory presentations, that is,
theories in many-sorted first-order logic defined by a set of axioms. We present
a proof of the Modularisation Theorem, a theorem that plays a fundamental role
in the process of program development. In this proof, we introduce the notion of
quotient theory induced by a interpretation. The categories of parameterised
specification and parameterised interpretation are defined.
[MCC40/92]
VELOSO, P.A.S.; POUBEL, H.W. On quotients of formal specifications. p. Eng.
E-mail: bib-di@inf.puc-rio.br
Abstract:
[MCC41/92]
PORTO, S.C.C.; CARVALHO, S.E.R. Introducing iterators in TOOL. 14 p. Eng. E-mail:
bib-di@inf.puc-rio.br
Abstract: TOOL is an object-oriented, event-driven programming system, designed
to simplify the task of building application programs for Windows and similar
environments. Its class construct has been designed to allow the definition of
behaviours of different natures for the modelled objects. In this report we
propose the inclusion of iterators in TOOL, as coroutine-like operators, which
provide the programmer with the ability of using control loop objects of any
class.