Monografias em Ciência da Computação



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

Last update: 24/APRIL/2009



SILVA, R.C.B. Conversion from BNF to syntax-graph, and syntax-graph reduction. 24 p. Eng. E-mail:

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.

MASON, J.; SANTOS, J.R.R. An iterative computer solution for the equations of elastic wall-girders. 18 p. Eng. E-mail:

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.

FURTADO, A.L.; FREIRE, F. Formula manipulation in the Fletcher and Powell optimization method. 13 p. Eng. E-mail:

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.

FURTADO, A.L. Solution of ordinary differential equations by the Taylor series method using formula manipulation. 4 p. Eng. E-mail:

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.

CARVALHO, S.E.R. On the Brooker-Morris expression recognition routine. 5 p. Eng.

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.

LUCENA, C.J.P. A software writing system. 14 p. Eng. E-mail:

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.

CARVALHO, R.L. A slip application: the construction of turing machines. 7 p. Eng. E-mail:

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.

CARVALHO, S.E.R. A recognizer for a precedence grammar. 20 p. Eng. E-mail:

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.

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:

Abstract: abstract not provided.

FRANCISS, F.O.; PUCCINI, A.L. Seepage in Earth dams with horizontal filter. 6 p. Eng. E-mail:

Abstract: This paper consists basicaly of a FORTRAN IV program to determine analitically the flow net in an earth dam with an horizontal filter.

SANTOS, J.R.R.; RIGAL, A.; BORDENAVE, M. Discretisation et resolution numérique de l'equation des ondes. 34 p. French. E-mail:

Abstract: This work aims at the discretisation and the numerical solution of the wave equation by the relaxation method.

SANTOS, J.R.R.; MASON, J. A finite element computer program for plane elasticity with consideration of thermal effects. 16 p. Eng. E-mail:

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.



FURTADO, A.L. A two-level Newton method for function optimization. 9 p. Eng. E-mail:

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).

PUCCINI, A.L. A Fortran program to solve the assignment problem. 18 p. Eng. E-mail:

Abstract: The basic proposition of this report is to present a Fortran program, recently developed, that solves the assignment problem.

CHAITIN, G.J. Computational complexity and Godel's incompleteness theorem and to a mathematical definition of 'Life'. 21 p. Eng. E-mail:

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.

FURTADO, A.L. A low-level mathematical pattern - matching algorithm. 37 p. Eng. E-mail:

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.

STAA, A.v. Basic functions for handling binary trees. 56 p. Eng. E-mail:

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.

SALIM, C.S.; SALIM, H.K. The Sparse system. 16 p. Eng. E-mail:

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.

SANTOS, S.M. Transformational grammars as models for natural languages. 14 p. Eng. E-mail:

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.

STAA, A.v. The COMCOM - software writing system. 18 p. Eng. E-mail: E-mail:

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.

KERSCHBERG, L.; HAPP, W.W. Eigenfunction propagation in interconnected systems. 8 p. Eng. E-mail:

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.

LUCENA, C.J.P. An approach for mapping abstract information structures on digital computer memories. 11 p. Eng. E-mail:

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.

FURTADO, A.L. Recursive techniques in dynamic programming. 20 p. Eng. E-mail:

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.

CARVALHO, R.L. On the use of pushdown automata for the parsing of sentences of context-Free languages. 11 p. Eng. E-mail:

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.



MARTINS, L.C. Preventive maintenance scheduling on an equipment.  p. Eng. E-mail:

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.

FURTADO, A.L. PUCMAT - A programming module for arithmetic pattern-matching. 28 p. Eng. E-mail:

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.

QUINTELLA, H.M. Diophantine systems and applications. p. Eng. E-mail:

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.

BROWN, M.P. A comparative study of symbol tables. 73 p. Eng. E-mail:

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.

KERSCHBERG, L.; SKANDERA, R. Urban traffic under computer control: a logical-mathematical view. 15 p. Eng. E-mail:

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.

CARVALHO, R.L.; MILLAN, M.R. On the construction and minimization of finite state automata. p. Eng. E-mail:

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.

RIBEIRO, M.T.; FURTADO, A.L.; PFEFFER, A.S.; MEDEIROS, A.T. Graph - Processing with LISP. 29 p. E-mail:

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.

HESS, L.A. Process of reducing figures into graphic structures: minimization and continuity of graph paths. p. Eng. E-mail:

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.

LUCENA, C.J.P.; CUNHA, L.F.A. A modelling technique in programming. 13 p. Eng. E-mail:

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.

PASSOS, E.P.L. Introduction to mechanical theorem proving. p. Eng. E-mail:

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).

CHAVES, T.F. An approach to predictors experiments and determination of better methods. 13 p. Eng. E-mail:

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.

MACEDO, L.T. A set of programs to test and parse LL(K) type languages. 14 p. Eng. E-mail:

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.


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:

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.

SOUSA, F.P. A taxonomic information handling system. 20 p. Eng. E-mail:

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.

BAUER, J.C.P.; FURTADO, A.L. Extending the control structures of PL/I. 22 p. Eng. E-mail:

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.

FURTADO, A.L. A canonical form for minimum state finite automata. 21 p. Eng. E-mail:

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.

BOVET, D.P. On the use of models employing both simulation and analytical solutions for scheduling computing centers. 13 p. Eng. E-mail:

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.

GALDA, K.; PASSOS, E.P.L. Applications of quantifier elimination to mechanical theorem proving. 17 p. Eng. E-mail:

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.

FURTADO, A.L. Algebraic concepts in data structures. 62 p. Eng. E-mail:

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.

SANTOS, S.M.; MILLAN, M.R. Automatic proofs for theorems on predicate calculus. 22 p. Eng. E-mail:

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.

KERSCHBERG, L. The primal factorization of complete graphs. 16 p. Eng. E-mail:

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.

TEIXEIRA, S.R.P.; CUNHA, L.F.A. On the reduction of the size of transition matrices. 26 p. Eng. E-mail:

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.

SANTOS, C.S.; FURTADO, A.L. G/PL/I - Extending PL/I for graph processing. 24 p. Eng. E-mail:

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.

TEIXEIRA, S.R.P.; NUNES, D.J. SDM - a Syntax Directed Macro-Processor. 9 p. Eng. E-mail:

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.



HARTMANN, C.R.P.; KERSCHBERG, L. A characterization of algebraic functions whose solutions are Nth roots of unity. 14 p. Eng. E-mail:

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.

CHAVES, R.N.M. The use of learning algorithms in non-minimax solutions of games. 25 p. Eng. E-mail:

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.

KERSCHBERG, L. The characteristic polynomial of graph products. 18 p. Eng. E-mail:

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.



FURTADO, A.L.; PFEFFER, A.S. Pattern matching for structured programming. 13 p. Eng. E-mail:

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.

PASSOS, E.P.L.; SILVEIRA, G.F.G. Applications of quantifier elimination to mechanical theorem proving - implementation. 19 p. Eng. E-mail:

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.

TEIXEIRA, S.R.P. Time-Varying languages. 18 p. Eng. E-mail:

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.

LUCENA, C.J.P. On the synthesis of programs and reliability. 21 p. Eng. E-mail:

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.

FURTADO, A.L. Characterizing sets of data structures by the connectivity relation. 23 p. Eng. E-mail:

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.



MYLOPOULOS, J.; FURTADO, A.L. Using graph grammars for the definition of sets of digraphs. 34 p. Eng. E-mail:

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.

CARVALHO, S.E.R. An efficient way of selecting lexical types. 15 p. Eng. E-mail:

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.

CARVALHO, S.E.R. On the generation of improved intermediate language for a class of arithmetic expressions. 28 p. Eng. E-mail:

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.

LUCENA, C.J.P.; SCHWABE, D.; BERRY, D. Issues in data type construction facilities. 26 p. Eng. E-mail:

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.

STAA, A.v.; LUCENA, C.J.P. On the implementation of data generality. 13 p. Eng. E-mail:

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.

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:

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.

CARVALHO, S.E.R. On type definition facilities in very high level programming languages. 8 p. Eng. E-mail:

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.

NOVOA, M.A.A.; CARVALHO, S.E.R. On the use of pointers and the teaching of disciplined programming. 27 p. Eng. E-mail:

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.

FURTADO, A.L.; SCHWABE, D. An incremental extension for recursive programs and structures in FORTRAN. 16 p. Eng. E-mail:

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.

SCHWABE, D.; LUCENA, C.J.P. Specification and uniform reference to data structures in PL/I. 12 p. Eng. E-mail:

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.

FURTADO, A.L. Semantic aspects of the relational model - a research outline. 11 p. Eng. E-mail:

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.

STAA, A.v. On the design of languages for a disciplined use of references. 10 p. Eng. E-mail:

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.



MELO, R.N.; SCHWABE, D. Extending the control structures of FORTRAN via a macro-generator. 13 p. Eng. E-mail:

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.

KERSCHBERG, L.; PACHECO, J.E.S. A functional data base model. 24 p. Eng. E-mail:

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.

STAA, A.v. On monitoring the use of data. 14 p. Eng. E-mail:

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.

STAA, A.v. Generator functions in modular programming. 17 p. Eng. E-mail:

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.

LAUTERBACH, C.H.; STAA, A.v. On the tree organization of abstract data types. 14 p. Eng. E-mail:

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.

FURTADO, A.L. Formal aspects of the relational model. 27 p. Eng. E-mail:

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

FURTADO, A.L.; BRODIE, M.L. A data structure for fast relational algebra operations. 20 p. Eng. E-mail:

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.

MELO, R.N. Suspension of JOBS in the IBM-1130. 11 p. Eng. E-mail:

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.

MELO, R.N. Implementing character strings in FORTRAN. 20 p. Eng. E-mail:

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.

FURTADO, A.L.; KERSCHBERG, L. An algebra of quotient relations - (DRAFT). 23 P. Eng. E-mail:

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.

RUAS, V. Some results on the curved plate bending problem solved with non-conforming finite elements. 23 p. Eng. E-mail:

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.

BARROSO, P.B.; FURTADO, A.L. Implementing a data definition facility driven by graph grammars. 20 p. Eng. E-mail:

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.

MAGALHAES, G.C.; FURTADO, A.L. A linear time sort algorithm applicable to data base management. 16 p. Eng. E-mail:

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.

SCHWABE, D.; LUCENA. C.J.P. Design and implementation of a data abstraction definition facility. 19 p. Eng. E-mail:

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.



GONNET, G.H. Average lower bounds for open-addressing hash - coding. 7 p. Eng. E-mail:

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.

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:

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.

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:

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.

FURTADO, A.L.; LUCENA, C.J.P. An incremental approach to the construction of data base software. 14 p. Eng. E-mail:

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.

FURTADO, A.L. Towards the design of data base interfaces for non-programmers. 10 p. Eng. E-mail:

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.

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:

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.

QUINTELLA, H.M.; SANTIMATEO, D.; PASCHOA, A. Computer kinetic modelling of radionuclide accumulation in marine organisms. 13 p. Eng. E-mail:

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.

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:

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.

CHALLIS, M.F. Integrity techniques in the Jackdaw database package. 15 p. Eng. E-mail:

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.

MAIBAUM, T.; LUCENA, C.J.P. Higher order data types. 36 p. Eng. E-mail:

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.

PASSOS, E.P.L. Efeitos de erros no cálculo de zeros de polinômios. 40 p. Port. E-mail:

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.

VELOSO, P.A.S. Characterizing the regular prefix codes. 11 p. Eng. E-mail:

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.

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:

Abstract: The basic concepts of the Lambda calculus are defined. Two applications in the area of programming languages semantics are presented.

MELO, R.N.; LELLIS, L. O mapeamento da especificacao conceitual em banco de dados gerenciado pelo TOTAL. 23 p. Port. E-mail:

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.

GOTLIEB, C.C.; FURTADO, A.L. Data schemata based on directed graphs. 67 p. Eng. E-mail:

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.

STAA, A.v. Especificacao do projeto COMCOM2. 11 p. Port. E-mail:

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.

CARVALHO, R.L.; FURTADO, A.L.; PEREDA BORQUEZ, A. A relational model towards the synthesis of data structures. 25 p. Eng. E-mail:

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.

SILVEIRA, A.M.; LUCENA, C.J.P. Geracao de dados de teste baseada nos aspectos estruturais de programas. 28 p. Port. E-mail:

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.

GONNET, G.H.; ROGERS, L.D. An algorithmic and complexity analysis of the heap as a data structure. 44 p. Eng. E-mail:

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.

CASTILHO, R.T.L. Pesquisas em andamento em Ciência da Computação. 68 p. Port. E-mail:

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.

GONNET, G.H.; ROGERS, L.D. The interpolation-sequential search algorithms. 5 p. Eng. E-mail:

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.

GONNET, G.H. Expected longest probe sequence in hash code searching. 16 p. Eng. E-mail:

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.

GONNET, G.H. Notes on the derivation of asymptotic expressions from summations. 13 p. Eng. E-mail:

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.

CHAHON, J.A.; MENDES, J.A.F.; SOLEY, N. Fatores humanos na programação. 21 p. Port. E-mail:

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.

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:

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.

SEVCIK, K.C.; FURTADO, A.L. Complete and compatible sets of update operations. 22 p. Eng. E-mail:

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.

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:

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. 



GOTLIEB, C.C. Programs for Data Processing and Computer Science in two-years colleges. 34 p. Eng. E-mail:

Abstract: This report examines the two-years program in Computer Science ("Project 15") in Brazil and its counterpart in Canada.

FURTADO, A.L.; SEVCIK, K.C. Permitting updates through views of data bases. 44 p. Eng. E-mail:

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.

FURTADO, A.L. A view construct for the specification of external schemas. 31 p. Eng. E-mail:

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.

VELOSO, P.A.S. Characterizations for the regular prefix codes and related families. 18 p. Eng. E-mail:

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.

TOMPA, F.W. A practical example of the specification of abstract data types. 36 p. Eng. E-mail:

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.

CHALLIS, M.F. Database consistency and integrity in a multi-user environment. 39 p. Eng. E-mail:

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.

GONNET, G.H. Open addressing hashing with unequal-probability keys. 14 p. Eng. E-mail:

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.

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:

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.

BOLCH, G.R.H. A heavy traffic model of a multiprogramming system. 24 p. Eng. E-mail:

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.

MELO, R.N. A arquitetura do REDAS (um sistema de gerência de banco de dados). 20 p. Port. E-mail:

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.

FURTADO, A.L.; STAA, A.v. Diretório de dados: utilidade e especificação. 19 p. Port. E-mail:

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.

ARSAC, J.J. A puzzle. 9 p. Eng. E-mail:

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.

STEINBRUCH, P.L.; MELO, R.N. Normas de programação e documentação: versão 1. 1 v. Port. E-mail:

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.

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:

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.

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:

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.

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:

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.

CHALLIS, M.F. Jackdaw II - Preliminary specification; part 2: Structural description. 31 p. Eng. E-mail:

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.

CHALLIS, M.F. Jackdaw II - Preliminary specification; part 3: the definition language. 45 p. Eng. E-mail:

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.

MELO, R.N.; STEINBRUCH, P. FORTS: um preprocessador para FORTRAN-IV estruturado. 32 p. Port. E-mail:

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.



AKONTEH, A.N. Microprogramming part 0: Theoretical evolution of the microprogram concept. 13 p. Eng. E-mail:

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.

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:

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.

MENASCÉ, D.A. Selective reloading of very large databases. 11 p. Eng. E-mail:

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.

AKONTEH, A.N. Microprogramming: principles and developments. 19 p. Eng. E-mail:

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.

AKONTEH, A.N. Microprogramming part II: developments in microprogramming languages. 9 p. Eng. E-mail:

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.

AKONTEH, A.N. Microprogramming part III: trends in emulation technology. 23 p. Eng. E-mail:

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.

MELO, R.N.; LELLIS, L. O mapeamento da especificação conceitual em banco de dados gerenciado pelo ADABAS. 22 p. Port. E-mail:

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.

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:

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.

STAA, A.v. Desenvolvimento estruturado de sistemas automatizados. 73 p. Port. E-mail:

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.

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:

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.

RUAS, V. A direct method for solving two-dimensional one phase Stefan problem. 21 p. Eng. E-mail:

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.

CARVALHO, R.L.; PASSOS, E.P.L.; LANZELOTTI, R. MTD-conversational system oriented for topology. p. Eng. E-mail:  (report not available)

Abstract: abstract not provided.

RUAS, V. Introdução aos problemas variacionais. 129 p. Port. E-mail:

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.

NAKANISHI, T.; RUAS, V.  Elementos de análise funcional aplicada. 150 p. Port. E-mail:

Abstract: This work aims at presenting, briefly and objectively, basic concepts of applied functional analysis.



HONIG, G.; HIRDES, U. A method for the numerical inversion of Laplace transforms. 28 p. Eng. E-mail:

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: (report not available)

Abstract: abstract not provided.

MENASCÉ, D.A.; NAKANISHI, T. Optimistic versus pessimistic concurrency control mechanisms in database management systems. 19 p. Eng. E-mail:

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.

MENASCÉ, D.A.; LANDES, O.E. On the design of a reliable storage component for distributed database management systems. 36 p. Eng. E-mail:

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.

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:

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: (report not available)

Abstract: abstract not provided.

LOBEL, R.E.; MELO, R.N. Um estudo de sistemas de dicionário de dados. 34 p. Eng. E-mail:

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.

CASTILHO, J.M.V.; FURTADO, A.L.; VELOSO, P.A.S. Algebraic specification of data base applications. 13 p. Eng. E-mail:

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.



REMY, J.L.; VELOSO, P.A.S. Comparing abstract data type specifications via their normal forms. 21 p. Eng. E-mail:

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.

CASANOVA, M.A.; BERNSTEIN, P.A. On the construction of database schedulers based on conflict-preserving serializability. 44 p. Eng. E-mail:

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.

CASANOVA, M.A. The theory of functional and subset dependencies over relational expressions. 31 p. Eng. E-mail:

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.

FURTADO, A.L.; VELOSO, P.A.S.; CASTILHO, J.M.V. Verification and testing of simple entity-relationship representations. 26 p. Eng. E-mail:

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.

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:

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.

FURTADO, A.L.; MAIBAUM, T.S.E. An informal approach to formal specifications. 21 p. Eng. E-mail:

Abstract: abstract not provided

VELOSO, P.A.S. Methodical specification of abstract data types via rewriting systems. 41 p. Eng. E-mail:

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.

FURTADO, A.L.; VELOSO, P.A.S. On multi-level specifications based on traces. 34 p. Eng. E-mail:

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.

MENDES, I.A. Redes de computadores: protocolos na rede de comunicações de dados. 94 p. Port. E-mail:

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.

NAKANISHI T.; MENASCE, D.A. Correctness and performance evaluation of a two-phase commit based protocol for DDBs. 52 p. Eng. E-mail:

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.

CASANOVA, M.A.; CASTILHO, J.M.V.; FURTADO, A.L. Properties of conceptual and external database schemas. 31 p. Eng. E-mail:

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.

CASANOVA, M.A. A theory of data dependencies over relational expressions. 60 p. Eng. E-mail:

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.

FURTADO, A.L. Horizontal decomposition to improve a non-BCNF scheme. 4 p. Eng. E-mail:

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.

SANTOS, C.S.; MAIBAUM, T.S.E.; FURTADO, A.L. Conceptual modelling of data base operations. 17 p. Eng. E-mail:

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.

ANDRADE, D.A.; VERAS, A.F.; MELO, R.N. Um estudo comparativo de metodologias de programação. 102 p. Port. E-mail:

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.

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:

Abstract: Catalogue of thesis and dissertations presented to the Departamento de Informática of PUC/RJ, 1969-1981.

STAA, A.v. LASO - Laboratório de Software. 24 p. Port. E-mail:

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



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:

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.

CASTILHO, R.T.L. Catálogo das publicações do Departamento de Informática 1968-1982. 114 p. Port. E-mail:

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.

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:

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.

CASTILHO, J.M.V.; CASANOVA, M.A.; FURTADO, A.L. A temporal framework for database specifications. 29 p. Eng. E-mail:

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.

MOURA, C.M.O.; CASANOVA, M.A. Design-by-example (preliminary report). 19 p. Eng. E-mail:

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.

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:

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.

VELOSO, P.A.S.; MAIBAUM, T.S.E. Specifying abstract data types via series rewriting systems. 13 p. Eng. E-mail:

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.

RUAS, V. On the solvability of asymmetric quasilinear finite element approximate problems in nonlinear incompressible
elasticity. 57 p. Eng. E-mail:

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.

FURTADO, A.L. A W-grammar approach to data bases. 14 p. Eng. E-mail:

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.

RUAS, V. Quasilinear finite elements for the stokes problem in R3. 28 p. Eng. E-mail:

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.

STAA, A.v. DSAC: desenvolvimento de software apoiado em computador. 22 p. Port. E-mail:

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.

PESSOA, F.E.P.; VELOSO, P.A.S. Introdução à programação com tipos abstratos de dados. 60 p. Port. E-mail:

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.

STAA, A.v. Metodologias para desenvolvimento de sistemas automatizados: a proposta de desenvolvimento. 64 p. Port. E-mail:

Abstract: Presents a guideline to write and evaluate automated systems development proposals.

VELOSO, P.A.S. Outlines of a mathematical theory of problems. 26 p. Port. E-mail:

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.



VELOSO, P.A.S. Problem solving via divide-and-conquer and abstract data types. 16 p. Eng. E-mail:

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.

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:

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.

VELOSO, P.A.S. A methodology for the sound and complete specification of abstract data types. 9 p. Eng. E-mail:

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.

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:

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.

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:

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.

RUAS, V. A convergent finite element method for solving dynamic problems with consistent diagonalized mass matrix. 14 p. Eng. E-mail:

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.

STAA, A.v.; ROCHA, A.R.C. Towards a model for evaluating specifications. 19 p. Eng. E-mail:

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.

VELOSO, P.A.S.; FURTADO, A.L. On some view constructs for the specification and design of external schemas. 20 p. Eng. E-mail:

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.

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:

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.

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:

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.

TUCHERMAN, L.; FURTADO, A.L.; CASANOVA, M.A. A pragmatical approach to structured database design. 51 p. Eng. E-mail:

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.

ALBRECHT, P. Numerical treatment of ordinary differential equations: the theory of A-methods. 47 p. Eng. E-mail:

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.

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:

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.

VELOSO, P.A.S. On the logic of namable models. 15 p. Eng. E-mail:

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.

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:

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.

VELOSO, P.A.S. On the role of additivity and linearity in mathematical systems theory. 15 p. Eng. E-mail:

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.

RUAS, V. Análise aplicada. 175 p. Eng. E-mail:

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.

RUAS, V. Automatic generation of tetrahedral meshes with application to finite element solution of Stefan problem.
20 p. Eng. E-mail:

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.

VELOSO, P.A.S.; MARTINS, R.C.B. On some notions of reduction among general problems. 15 p. Eng. E-mail:

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.

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:

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.

MAIA, A.C.P. Um estudo em compressão de dados. 30 p. Port. E-mail:

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.



VELOSO, P.A.S.; CASANOVA, M.A.; FURTADO, A.L. Formal data base specification - an ecletic perspective. 48 p. Eng. E-mail:

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.

RUAS, V. Finite element solution of 3D Viscous flow problems using nonstandard degrees of freedom. 27 p. Eng. E-mail:

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.

ALVARENGA, C.; TANAKA, A.K.; MELO, R.N. Padronização de sistemas gráficos. 82 p. Port. E-mail:

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.

TAVARES, O.L. Manual de implementação do protocolo de transferência de arquivos da REDPUC. 114 p. Port. E-mail:

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.

FURTADO, A.L.; MOURA, C.M.O. Expert helpers to data-based information systems. 17 p. Eng. E-mail:

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.

RUAS, V. Métodos de elementos finitos mistos: pt.1- Introdução aos fundamentos matemáticos. p. Port. E-mail: (report not available)

Abstract: abstract not provided.

MELO, R.N.; SILVA, S.D. DBTGinho: uma implementação da proposta CODASYL. 48 p. Port. E-mail:

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).



VELOSO, P.A.S. On the concept of problem - solving method. 22 p. Eng. E-mail:

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.

VELOSO, P.A.S. What do you mean by "Here is a problem related to yours..."? 21 p. Eng. E-mail:

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.

RUAS, V. Uma introdução a teoria matemática dos métodos de elementos finitos mistos. 42 p. Port. E-mail:

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.

VELOSO, P.A.S. Programme development as theory manipulations. 30 p. Eng. E-mail:

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.

ALBRECHT, P. A new theoretical approach to Runge-Kutta methods. 29 p. Eng. E-mail:

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.

VELOSO, P.A.S. On the role of (data) abstraction in program development and problem solving. 26 p. Eng. E-mail:

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.

STAA, A.v. Projeto MOSAICO: definição do projeto. 31 p. Port. E-mail:

Abstract: MOSAIC aims at supporting software lifecycle, including the development and maintenance of all its eventual prototypes.

STAA, A.v. MOSAICO - estruturado: requisitos. 30 p. Port. E-mail:

Abstract: In this report are defined: the objectives, architecture and the environment requirements to support the MOSAIC structured programming system project.



RUAS, V. A quadratic finite element method for solving biharmonic problems in IRn. 16 p. Eng. E-mail:

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.



HAEUSLER, E.H. Automatic theorem proving: an attempt to improve readability of proofs generated by resolution. 15 p. Eng. E-mail:

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.

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:

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.

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:

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.

IERUSALIMSCHY, R. Abstração de dados em linguagens de programação: tipos e objetos. 15 p. Port. E-mail:

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.



MENASCE, D.A.; ALMEIDA, V.A.F. On the investigation of supercomputer architectures in multiprogramming environments using analytic models. 23 p. Eng. E-mail:

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.

RUAS, V. Approximation of the vector potential for viscous incompressible flow via the constant stress finite elements. 24 p. Eng. E-mail:

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.

BITTEL, O.; ALENCAR, P.S.C. Towards a tableau-based intuitionistic theorem prover. 30 p. Eng. E-mail:

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.

VELOSO, P.A.S.; HAEBERER, A.M. A problem-theoretic analysis and (meta-)model of the software development process. 46 p. Eng. E-mail:

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.

PESSOA, T.E.C. Existe logica em redes semanticas? 29 p. Port. E-mail:

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.

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:

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).

FURTADO, A.L.; VELOSO, P.A.S. Iteration for applicative languages: a proposal. 9 p. Eng. E-mail:

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.

SOARES, J.F.; GUARANYS, P.Y. Extensoes propostas sobre o monitor para apoio a programacao em logica. 24 p. Port. E-mail:

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.

SOARES, J.F.; GUARANYS, P.Y. Um monitor para apoio a programação em lógica. 20 p. Port. E-mail:

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.

NUNES, M.G.V. Deep generation in a crime knowledge-based system. 54 p. Eng. E-mail:

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.

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:

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.

SILVA, J.R.; LUCENA, C.J.P. Um novo paradigma para o problema de reutilização de software. 15 p. Port. E-mail:

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".

SCOTT, D.R.; SOUZA, C.S. Conciliatory planning for extended descriptive texts. 15 p. Eng. E-mail:

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.

LUCENA, C.J.P.; SILVA, J.R. An approach to software reuse based on a formal theory of metaphors. 9 p. Eng. E-mail:

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.

GUARANYS, P.Y.; LUCENA, C.J.P. PUC: a knowledge based environment for planned user communication. 18 p. Eng. E-mail:

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.

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: (report not available)

Abstract: abstract not provided.

FERNANDES, C.T. Um algoritmo de hifenização multilíngue. 25 p. Port. E-mail:

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.

HAEUSLER, E.H. Intuitionistic type theory and general problem theory: a relationship. 52 p. Eng. E-mail:

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.

FERNANDES, C.T.; RANGEL NETTO, J.L.M. Otimização de código utilizando gramáticas de atributos. 41 p. Port. E-mail:

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.

BRAZ, M.H.B. O desenvolvimento de interfaces. 41 p. Port. E-mail:

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.

BRAZ, M.H.B. Interfaces inteligentes. 40 p. Port. E-mail:

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".



NUNES, M.G.V. Lettera: um gerador de textos. 28 p. Port. E-mail:

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.

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:

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.

GUARANYS, P.Y. S.O.S. - Sistema orientado a socorrer. 35 p. Port. E-mail:


SILVA, W.T.; RICHTER, G. Formalização da abordagem orientada a objetos em redes de Petri. 29 p. Port. E-mail:

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.

LISANDRE, B.; SANTOS FILHO, H.N. Um gerador automático de interfaces homem - máquina. 16 p. Port. E-mail:

Abstract: English abstract not provided.

VARGAS, D.A.; HAEBERER, A.M. Formal theories of problems. 65 p. Eng. E-mail:

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.

HAEBERER, A.M.; VELOSO, P.A.S. On the requirement - specification - program triangle: a theoretical analysis.
30 p. Eng. E-mail:

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.

de SOUZA, C.S.; SCOTT, D.R.; NUNES, M.G.V. Enhancing text quality in question answering systems. 12 p. Eng. E-mail:

Abstract: English abstract not provided.

de SOUZA, C.S.; CARVALHO, E.B.S. Aspects of natural language queries to database revisited. 9 p. Eng. E-mail:

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.

SOUZA, C.S. Gramáticas de determinação: uma abordagem metodológica. 15 p. Port. E-mail:

Abstract: English abstract not provided.

MATICH, G.H.; CARVALHO, S.E.R. Principios e polêmicas sobre "orientação a objetos". 37 p. Port. E-mail:

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.

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:

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.

LIMA, F.S. Estabilidade e convêrgencia do método da projeção. 51 p. Port. E-mail:

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.

LIMA, F.S. Fórmulas de Green para operadores lineares relacionadas com uma ou duas integrais de contorno.
35 p. Port. E-mail:

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.

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:

Abstract: English abstract not provided.

FERNANDES, C.T. A denotational model of types. 18 p. Eng. E-mail:

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.

FERNANDES, C.T. Uma taxonomia para ambientes de software. 32 p. Port. E-mail:

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.

REZENDE, M.A.M. HIER - Highly Interactive Expert Resolver: uma ferramenta para sistemas especialistas. 53 p. Port.

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.

HAEBERER, A.M.; VELOSO, P.A.S.; ELUSTONDO, P.M. Towards a problem-oriented relational calculus for software
construction. 22 p. Eng. E-mail:

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.

FURTADO, A.L. Some extension to Warren's plan-generation algorithm. 17 p. Eng. E-mail:

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.

FURTADO, A.L. Treating workspace and SQL facts uniformily in PROLOG. 12 p. Eng. E-mail:

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.

ALENCAR, P.S.C. Uma abordagem lógica para sistemas evolutivos de software. 38 p. Port. E-mail:


SCOTT, D.R.; de SOUZA, C.S. Getting the message across: a computational grammar of text. 21 p. Eng. E-mail:

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.

HAEBERER, A.M.; VELOSO, P.A.S. On the inherent non-monotonicity of software development: a formal justification. 15 p. Eng. E-mail:

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.

PEREZ ALCAZAR, J.J. Bancos de dados dedutivos temporais: uma revisão. 61 p. Port. E-mail:

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.

LEITE, J.C.S.P.; LUCENA, C.J.P. The Rio Workshop on the Software Process. 8 p. Eng. E-mail:

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.

SCHWABE, D.; MIZUTANI, E.E. A knowledge-based browser to access complex databases. 13 p. Eng. E-mail:


SILVA, W.T.; MILIDIU, R.L. Algoritmos para combinação de evidências. 43 p. Port. E-mail:

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.

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:

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.

LEITE, J.C.S.P. Elicitation of application languages. 6 p. Eng. E-mail:

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.

SOUZA, C.S. Speech acts in computer-human interfaces. 12 p. Eng. E-mail:

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.



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:

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.

VELOSO, P.A.S.; HAEBERER, A.M. Towards a formal analysis of the software process. 16 p. Eng. E-mail:


SCHWABE, D.; FEIJÓ, B.; KRAUSE, W.G. Intelligent hypertext for normative knowledge in Engineering. 11 p. Eng. E-mail:

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.

BIGONHA, M.A.S. O papel da representação do conhecimento na construção de sistemas especialistas. 38 p. Port. E-mail:

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.

CABRAL, R.H.B. O modelo de design do sistema MIDAS de desenvolvimento de interfaces de usuários. 13 p. Port.


SILVA, S.B. Hierarquias de memoria. 35 p. Port. E-mail:


SILVA, S.B. Perfil de referências de um programa a memória. 33 p. Port. E-mail:


GUARANYS, P.Y.; LUCENA, C.J.P. New approach to user modelling based on double stereotypes. 21 p. Eng. E-mail:

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.

HAEBERER, A.M. Analisis comparativo de la teoria sobre condicionales contra-factuales. p. Esp. E-mail:


RODRIGUEZ, N.R. Tratamento de exceções. 40 p. Port. E-mail:

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.

MERÉ, M.C. Model of ptyxes for sum and empty types. 37 p. Eng. E-mail:

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.

HAEBERER, A.M.; VELOSO, P.A.S. Partial relations for program derivations - adequacy, inevitability, and expressiveness. 53 p. Eng.

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.

BIGONHA, M.A.S. Otimização de código usando técnicas de Inteligência Artificial. 36 p. Port. E-mail:

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.

BIGONHA, M.A.S. Linguagens para descrição de arquitetura de computador. 47 p. Port. E-mail:

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.

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:


CABRAL, R.H.B. Interfaces inteligentes: conceituação, taxonomia e arquitetura de suporte. 29 p. Port. E-mail:

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.

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:

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.

VELOSO, P.A.S.; HAEBERER, A.M. Towards a new algebra of first-order logic: binary relations resumed. 11 p. Eng.


FISCHER, R.; FEIJÓ, B. Genesys - a new hybrid solid modeling system. 4 p. Eng. E-mail:

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.

FEIJÓ, B.; FISCHER, R.; DREUX, M. Better criteria for the development of solid modeling software. 9 p. Eng.

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.

SCHWABE, D.; CALOINI, A.; GARZOTTO, F.; PAOLINI, P. Hypertext development using a model-based approach. 37 p. Eng. E-mail:

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.

GARZOTTO, F.; PAOLINI, P.; SCHWABE, D. HDM: a model-based approach to hypertext application design. 53 p. Eng.

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.

GARZOTTO, F.; SCHWABE, D.; PAOLINI, P. New perspectives for hypertext applications using model-based design. 33 p. Eng. E-mail:

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.



MAFFEO, B. ESML (Extended Systems Modeling Language) - uma revisão da apresentação, estrutura, notação e conteúdo. 63 p. Port. E-mail:

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.

IERUSALIMSCHY, R. A method for object oriented specification with VDM. 28 p. Eng. E-mail:

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.

IERUSALIMSCHY, R. The O=M programming language. 27 p. Eng. E-mail:

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.

KISCHINHEVSKY, M. A multilevel conjugate gradiente method. 23 p. Eng. E-mail:

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.

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:

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.

VERVLOET, W.J. As tabelas de símbolos e as linguagens orientadas a objetos. 56 p. Port. E-mail:

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.

ANDRE, A.A.; MAFFEO, B. Projeto ("design") na área de métodos estruturados: transformando redes em hierarquias.
34 p. Port. E-mail:

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.

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:

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.

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:

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.

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:

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.

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:

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.

FISCHER, R. Formas de representação para objetos tridimensionais. 163 p. Port. E-mail:

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.

VERVLOET, W.J. Um mapeamento de JSD para orientação a objetos. 31 p. Port. E-mail:

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.

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:

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.

SILVA, M.T.M.P. Interação com sistemas de informação baseados em conhecimento. 25 p. Port. E-mail:

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.

RICHTER, G.; MAFFEO, B. Towards a rigorous interpretation of ESML - Extended Systems Modeling Language. 38 p. Eng. E-mail:

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.

COWAN, D.D.; IERUSALIMSCHY, R.; STEPIEN, T.M. Constructing composite interactive documents from interactive components. 12 p. Eng. E-mail:

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.

LUCENA, C.J.P.; TAKAHASHI, E.T. A anatomia de um ambiente de desenvolvimento de software. 46 p. Port. E-mail:

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.

KISCHINHEVSKY, M. On the numerical solution of ordinary differential equations with cyclic methods. 15 p. Eng.

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.

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:


CARVALHO, R.L.; VIEIRA, N.J. Linear resolution, definitions and functions. 19 p. Eng. E-mail:

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.

CARVALHO, R.L.; VIEIRA, N.J.; OLIVEIRA, C.M.G.M. SAFO: an environment for logics. 17 p. Eng. E-mail:

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.

CARVALHO, R.L. Abstract semantical systems. 36 p. Eng. E-mail:

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.

FUKS, H. ACCORD: a framework for dialogue representation using commitment. 44 p. Eng. E-mail:

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.

HAEUSLER, E.H. On the theorem prover based on game-theoretic semantics. 20 p. Eng. E-mail:

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).

HAEUSLER, E.H.; PEREIRA, L.C.P.D. A denotational semantics for an arbitrary level typed Lambda-Calculus. 30 p. Eng. E-mail:

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.

RITTO, A.C.A.; MAFFEO, B. Funções do gerente de desenvolvimento de sistemas - algumas reflexões. 14 p. Port. E-mail:

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.

LEITE, J.C.S.P.; PRADO, A.F. Design recovery a multi-paradigm approach. 13 p. Eng. E-mail:

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.

LUCENA, C.J.P.; LEITE, J.C.S.P.; SCHWABE, D.; FUKS, H. A research agenda on software design. 8 p. Eng. E-mail:

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.



LAUFER, C.C.; FUKS, H.; SCHWABE, D. ACCORD: representação de clichês de conversação para cooperação. 15 p. Port.

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.

RIDOLFI, L.F.G.G.M.; FUKS, H.; SCHWABE, D. ACCORD - máquina básica. 30 p. Port. E-mail:

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.

BATISTA, T.V.; SANTOS, H.R.A.; FUKS, H. Cooperatividade na manipulação de documentos multimídia. 20 p. Port. E-mail:

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.

DUARTE, R.C.; FUKS, H.; LUCENA, C.J.P. Software design cooperativo: um estudo de caso. 18 p. port. E-mail:

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.

MATHIAS, A.G.; FUKS, H. Resolução de conflitos e trabalho em grupo. 29 p. Port. E-mail:

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.

CARVALHO, S.S.; FUKS, H. Groupware: a incorporação de aspectos sociais ao software. 23 p. Port. E-mail:

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.

SILVA, S.D.; FUKS, H. Sistemas de informação de escritório usando Redes de Petri. 31 p. Port. E-mail:

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.

TRALES, P.R. Tópicos especiais sobre os sistemas de computação algébrica. 219 p. Port. E-mail:

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.

BIGONHA, M.A.S. Esquemas de escalonamento de instruções para a arquitetura RISC/6000. 33 p. Port. E-mail:

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.

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:

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.

SANCHEZ, M.L.A.; PLEHWE, A.K.v. Modelo de implementação de um terminal tático inteligente. 72 p. Port. E-mail:

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.

IERUSALIMSCHY, R. A denotational approach for type-checking in object-oriented programming languages. 28 p. Eng. E-mail:

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.

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:

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.

SILVA, S.D.; MAFFEO, B. Modelagem conceitual de bancos de dados com Redes de Petri - um estudo de caso. 40 p. Port. E-mail:

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

MERE, M.C.; VELOSO, P.A.S. Runs, conditions and problems: an algebraic approach. 28 p.Port. E-mail:

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.

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:

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.

VELOSO, P.A.S. On the modularisation theorem for logical specifications: its role and proof. 23 p. Eng. E-mail:

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.

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:

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.

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:

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.

POUBEL, H.W. Adjuncões e a extensão da dedução natural. 31 p. Port. E-mail:

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.

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:

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.

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:

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.

CARVALHO, S.E.R. Exception handling in object oriented languages: a proposal. 13 p. Eng. E-mail:

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.

COELHO, O.P.; CARVALHO, S.E.R. O uso de classes como unidade de paralelismo. 18 p. Port. E-mail:

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.

CARVALHO, S.E.R. Tool: a short description. 9 p. Eng. E-mail:

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.

DANTAS, M.A.R.; GHEINER, M.; SARMENTO, A.; CARVALHO, S.E.R. X-NET: uma linguagem, tres paradigmas. 18 p. Port. E-mail:

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.

IERUSALIMSCHY, R. A formal specification for a hierarchy of collections. 20 p. Eng. E-mail:

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.

KISCHINHEVSKY, M. A direct domain decomposition procedure for elliptic problems. 15 p. Eng. E-mail:

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.

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:

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.

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:

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.

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:


BAUM, G.A.; HAEBERER, A.M. On solving universally quantified relational expressions. p. Eng. E-mail:


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:

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.

LEITE, J.C.S.P. A case study on requirements recovery from structured specifications. 8 p. Eng. E-mail:

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.

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:

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.

GARCIA, L.S. Interfaces em linguagem natural orientadas por Menus: uma análise crítica do ambiente. 17 p. Port. E-mail:

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.

CARVALHO, S.E.R. Decoupling interface and implementation: the TOOL solution. 24 p. Eng. E-mail:

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.

MERE, M.C.; VELOSO, P.A.S. On extensions by sorts. 18 p. Eng. E-mail:

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.

POUBEL, H.W.; VELOSO, P.A.S. Tipos de dados parametrizados: especificação, interpretação e implementação. 16 p. Port. E-mail:

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.

VELOSO, P.A.S.; POUBEL, H.W. On quotients of formal specifications. p. Eng. E-mail:


PORTO, S.C.C.; CARVALHO, S.E.R. Introducing iterators in TOOL. 14 p. Eng. E-mail:

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.