Technical Reports Published in 1995

  • DCC-95-27 pdf bib
    Workflow modeling.
    Paulo Barthelmess and Jacques Wainer.
    December 1995. In English, 14 pages.

    Abstract: A discussion of workflow models and process description languages ​​is presented. The relationship between data, function and coordination aspects of the process is discussed, and a claim is made that more than one model view (or representation) is needed in order to grasp the complexity of process modeling.

    The basis of a new model is proposed, showing that more expressive models can be built by supporting asynchronous events and batch activities, matched by powerfull run-time support.

  • DCC-95-26 pdf bib
    WorkFlow systems: A few definitions and a few suggestions.
    Paulo Barthelmess and Jacques Wainer.
    December 1995. In English, 14 pages.

    Abstract: This paper hopes to make a contribution on three aspects of workflow systems: we stress the fact that there is a broken symetry between the level of the specification of the procedures and the level of their enactment; we propose some ways of classifying activities and exceptions; and we propose some run-time functionalities to help users deal with exceptions.

  • DCC-95-25 pdf bib
    Multiware platform: Some issues about the middleware layer.
    Edmundo R. M. Madeira.
    December 1995. In English, 10 pages.

    Abstract: This paper presents the conceptual and implementation models to the Middleware Layer of the Multiware Platform that is under development at UNICAMP - University of Campinas, Brazil. This platform combines ideas from both the RM-ODP (Reference Model for Open Distributed Processing) and existent products, like ANSAware and CORBA (Common Object Request Broker Architecture). The platform offers functionalities to support and facilitate the development, use and management of cooperative applications, like group decision support systems for GIS (Geographical Information Systems).

  • DCC-95-24 pdf bib
    ATIFS: A testing environment based on software fault injection.
    Elaine Martins.
    December 1995. In Portuguese, 32 pages.

    Summary: One of the difficulties in the development of fault-tolerant systems concerns their validation. This difficulty comes from the fact that the testing of these systems requires the consideration of abnormal situations, which activate the mechanisms for handling errors and failures existing in such systems.

    A technique that has been widely used for this purpose is fault injection, which consists of introducing errors / failures in a system, in a controlled manner, and observing its behavior.

    This text presents ATIFS, a Test Environment based on Fault Injection by Software, which provides support for the development and execution of tests of fault tolerant systems, as well as for the analysis of the results obtained in the tests. An important feature of ATIFS is that it allows the use of a formal model of the system, which can serve as a basis both for the automated generation of the tests to be applied and for obtaining a reference to be used in the analysis of the results. For the choice of test entries, ATIFS offers the user the possibility to define statistical tests, based on the distribution of probabilities associated with the input domain. The performance of statistical tests based on the system model allows ATIFS to provide support both for the verification of the system's behavior in the presence of failures, and for the evaluation of measures of the efficiency of its error detection / recovery mechanisms, a characteristic that sets it apart from most fault injection test environments.

  • DCC-95-23 pdf bib
    Calculation of the structure of a text in a natural language processing system.
    Horacio Saggion and Ariadne MB R. Carvalho.
    December 1995. In Spanish, 13 pages.

    Summary: Calculating the linguistic structure of a text is fundamental in any natural language processing system. For this, phenomena but all of the sentence's barrier must be considered. In particular, the studies should be addressed in the processing of a text: textual cohesion and textual coherence. In this work we define a representation for the structure of a summary in Portuguese language considered as a linguistic phenomenon. The representation was obtained from the study of real summaries and the verification of relationships between sentences in the text. We believe that this type of representation can be used for other texts, which is defined in terms of cohesion and coherence relationships. The main aspect considered in this work for the construction of the textual structure is the cohesion through the resolution of defined anaphors both pronouns and defined nominal phrases. We present examples of real text and their treatment within the proposed theoretical framework.

  • DCC-95-22 pdf bib
    Text structure aiming at machine translation.
    Horacio Saggion and Ariadne MB R. Carvalho.
    December 1995. In English, 13 pages.

    Abstract: Machine translation relies on the existence of a meaning representation which must be able to capture the semantic content of the original text. The work presented here is concerned with the automatic generation of such a representation, to be used by a machine translation system. We have used as source text scientific abstracts in Portuguese. The emphasis of the work is on the determination of the text structure of such abstracts, making use of the notions of cohesion and coherence. The main cohesion phenomena considered here is definite anaphora.

  • DCC-95-21 pdf bib
    A linear time algorithm for binary phylogeny using PQ-trees.
    João Meidanis and Erasmo G. Munuera.
    December 1995. In English, 6 pages.

    Abstract: The Binary Phylogeny Problem is to reconstruct a tree reporting the evolutionary history of a group of taxa for which a binary matrix of characteristics is given. Gusfield presented an $ O (mn) $-time algorithm for this problem with $ n $ rate and $ m $ characteristics. This bound is tight if the input is given as an $ n \ times m $ matrix. In this paper we show that a linear time algorithm is possible provided the input is given as a list of the `` 1 '' positions in the matrix. The PQ-trees introduced by Booth and Leuker are used here. More precisely, we show that a binary phylogeny exists if and only if the input admits a PQ-tree without Q nodes. This immediately gives a linear time algorithm for the problem.

  • DCC-95-20 pdf bib
    John von Neumann: Your contributions to computing.
    Tomasz Kowaltowski.
    December 1995. In Portuguese, 18 pages.

    Summary: John von Neumann, one of the greatest scientists of the XNUMXth century, made important contributions to various areas, with emphasis on his work in Mathematics, Applied Mathematics, Physics, Meteorology, Economics and Computing. In several cases, their contributions went far beyond solving problems proposed by others, opening up new areas of research and launching new problems. The objective of this work is to show von Neumann's contributions to Computing and, in particular, to digital computer architecture, computer programming and computer theory.

    This work was prepared for the lecture given during the meeting The Work and Legacy of John von Neumann, organized by the Institute of Advanced Studies of the University of São Paulo and by the Brazilian Academy of Sciences, on November 14, 1995, at the Institute of Mathematics and Statistics of the University of São Paulo.

  • DCC-95-19 pdf bib
    wxWindows: An introduction.
    Carlos Neves Jr., Tallys H. Yunes, Fábio N. de Lucena, and Hans K. E. Liesenberg.
    December 1995. In Portuguese, 27 pages.

    Summary: The text consists of a tutorial that provides the user, with basic notions of object-oriented programming in C ++, an explanatory introduction to programming based on the `` toolkit '' wxwindows. This package is a public domain tool, with cross-platform implementations (ftp.aiai.ed.ac.uk:pub/packages/wxwin).

    The tutorial deals exclusively with the programming interface of wxwindows and how it can be used in the construction of human-computer interfaces. Several examples are provided.

  • DCC-95-18 pdf bib
    Asynchronous Teams: A multi-algorithm approach for solving combinatorial multiobjective optimization problems.
    Rosiane F. Rodrigues and Pedro S. de Souza.
    November 1995. In English, 11 pages.

    Abstract: The fundamental question in solving multi-objective function problems lays in the determination of solutions that would best meet all the objectives involved. The aim of this work is to present Asynchronous Teams (Or A-Teams) as an appropriate method to detect this set of solutions for combinatorial problems. A-Teams basic principle is the asynchronous cooperation among a set of heuristic algorithms in order to produce better solutions than those obtained using each algorithm separately. As an example of a combinatorial multiobjective function problem we propose a generalization of the classical Traveling Salesman Problem for several distance matrices, named Multi-Distance Traveling Salesman Problem (Or MDTSP).

  • DCC-95-17 pdf bib
    Proceedings of the II National Workshop on Combinatorial Problems: Theory, Algorithms and Applications.
    Marcus V. S. Poggi de Aragon and Cid C. de Souza (eds.).
    November 1995. Partly in English, partly in Portuguese, 58 pages.

    Abstract: This report contains the Proceedings of the II National Workshop on Combinatorial Problems: Theory, Algorithms and Applications (II ON ProComb). The workshop was held November 15-17, 1995 at the Computer Science Department (DCC-IMECC) of the State University of Campinas (UNICAMP), Campinas, SP, Brazil.

    The event was part of the ProComb project, comprising combinatorics researchers from USP (DCC-IME), UNICAMP (DCC-IMECC), PUC-RJ and UFRJ (DI and DEE). The project is sponsored by CNPq though its Multi-institutional Thematic Program in Computer Science (ProTeM-CC-II).

    • A pretty class of perfect graphs. Frédéric Maffray, Oscar Porto, and Myriam Preissman.
    • A scalable parallel algorithm for list ranking. Frank Dehne and Siang W. Song.
    • The homogeneous set sandwich problem. Hazel Everett, Celina M. H. Figueiredo, Sulamita Klein, and Márcia Cerioli.
    • Local conditions for edge-coloring. Celina M. H. Figueiredo, João Meidanis, and Célia P. de Mello.
    • An adaptation of the Edmonds pairing algorithm for running in parallel. Carlos F. Bella Cruz and João Carlos Setubal.
    • Upper bounds for minimum covering codes by tabu-search. Walter A. Carnielli, Emerson L. do Monte Carmelo, Marcus V. S. Poggi de Aragon and Cid C. de Souza.
    .

  • DCC-95-16 pdf bib
    Replicating agents and echo algorithms.
    Marcos J. C. Euzébio.
    October 1995. In Portuguese, 9 pages.

    Summary: Echo algorithms form a class of simple, versatile and efficient distributed algorithms used to obtain global information in a decentralized way. Usually these algorithms are implemented using the message exchange paradigm, although their description follows the metaphor of replicating agents. In this article the execution environment will be presented, which offers the infrastructure for the execution of replicating agents, as well as the description of some initial experiences obtained in the programming of replicating agents, including the implementation of an instance of the echo algorithms.

  • DCC-95-15 pdf bib
    NP-hardness results for tension-free layout.
    Cândido F. X. de Mendonça Neto, Peter Eades, Cláudio L. Lucchesi, and João Meidanis.
    August 1995. In English, 11 pages.

    Abstract: A tension-free layout of a weighted graph $ G $ is an embedding of $ G $ in the plane such that the Euclidean distance between adjacent nodes is equal to the edge weight. Very few weighted graphs admit such a layout. However, any graph can be made into a tension-free graph by repeated application of an operation called vertex splitting, or by removing edges. In this paper we show that computing the minimum number of such operations that yield a tension-free graph is NP-hard.

  • DCC-95-14 pdf bib
    Vertex splitting and tension-free layout.
    Peter Eades and Cândido F. X. de Mendonça Neto.
    August 1995. In English, 11 pages.

    Abstract: In this paper we discuss the `` vertex splitting '' operation. We introduce a kind of `` spring algorithm '' which splits vertices to obtain better drawings. We report some experience with the technique.

  • DCC-95-13 pdf bib
    Parallel computing models and algorithm design.
    Ronaldo P. de Menezes and João C. Setubal.
    August 1995. In Portuguese, 12 pages.

    Summary: The PRAM model has been the main model for the design and analysis of parallel algorithms for over 15 years. Its simplicity makes it a model that is not very true to reality, which motivated the appearance of extensions and other models, among which BSP (Valiant, 1990) and LogP (Culler et al., 1993). We present a brief description of these 3 models and show the different levels of abstraction in which they are located. The advantages and disadvantages of each one are presented, particularly with regard to the design and analysis of algorithms. The relevance of each one to the current panorama of parallel machines is discussed, concluding that the LogP model, despite being of a lower level, is the one most likely to spread in practical situations.

  • DCC-95-12 pdf bib
    Computational models for digital image processing in parallel architectures.
    Neucimar J. Leite.
    August 1995. In Portuguese, 12 pages.

    Abstract: In this paper we present some computational models for iterative cellular automaton for image processing applications. We introduce some concepts such as memory splitting, conditional functions, dynamic neighborhood and supervisor automaton. The models defined lead to a parallel language structure that can express low-level image processing in a clear and concise way. The language allows a transparent description of the algorithms and can be easily expandable to reflect the needs of people working in different branches of image processing.

  • DCC-95-11 pdf bib
    Neighborhood processor for morphological filtration.
    Ilka M. Barros, Roberto A. Lotufo, and Neucimar J. Leite.
    August 1995. In Portuguese, 12 pages.

    Summary: This work presents a systolic architecture for the implementation of mathematical morphology operations (morphological filters). This architecture called SAMM (Systolic Architecture for Mathematical Morphology) implements the expansion and erosion operations with a planar structuring element. It has two levels of modularity, the first resulting from the implementation on the same hardware of numerical and binary operations, the other due to the systolic character of its processing. Taking into account factors such as performance, operations execution time and architecture, some processors were chosen that implement mathematical morphology filters for functional and complexity comparison with the developed architecture.

  • DCC-95-10 pdf bib
    A highly reconfigurable neighborhood image processor based on functional programming.
    Neucimar J. Leite and Marcelo A. de Barros.
    August 1995. In English, 10 pages.

    Abstract: A special purpose cellular processor, based on the Functional Programming approach, is proposed for image processing applications. The basic data flow graph of the processor is defined according to the data structure of a class of nonlinear filters very useful in image processing.

    The cells of the processor are quite simple and support a certain degree of programmability that allows, for instance, a logical reconfiguration of the network. This flexibility contributes to the execution of a multitude of standard low-level image processing algorithms on the same basic structure.

  • DCC-95-09 pdf bib
    Basis for the matching lattice of matching covered graphs.
    Cláudio L. Lucchesi and Marcelo H. Carvalho.
    July 1995. In English, 7 pages.

    Abstract: This article contains a brief introduction to the theory of matching covered graphs: ear-decompositions, the matching lattice and the most important results of the theory. Its last section contains rather recent results and a conjecture relating the minimum number of double ears of any ear-decomposition of a matching covered graph and the number of bricks and bricks isomorphic to the Petersen graph in any brick decomposition of the same graph.

  • DCC-95-08 pdf bib
    A direct manipulation user interface for querying geographic databases.
    Juliano L. de Oliveira and Claudia M. B. Medeiros.
    June 1995. In English, 15 pages.

    Abstract: This paper presents an architecture for a direct manipulation user interface for browsing and querying geographic data. This interface provides users with a high level object oriented conceptual view of the underlying database, independent of the database's native data model. It lets users manipulate different representations of a single georeferenced entity, thereby adding a new degree of flexibility to querying facilities.

  • DCC-95-07 pdf bib
    Xchart-based complex dialogue development.
    Fábio N. de Lucena and Hans K. E. Liesenberg.
    June 1995. In English, 11 pages.

    Abstract: Xchart is a research software system that provides tools and facilities for the development of computer human interfaces. Control aspects of distributed reactive system (computer human interface) can be modeled through the use of constructs of the Xchart specification language. In this particular domain, greater attention is devoted to the subclass of multi-thread dialogues. Some of the constructs of the language have been tailored for this particular class of dialogue. By means of various tools, the environment supports different development stages ranging from diagram construction in the specification phase, to their execution. A simple example is used to illustrate Xchart's main features.

  • DCC-95-06 pdf bib
    Guaranteeing full fault coverage for UIO-based methods.
    Ricardo O. Anido and Ana Cavalli.
    June 1995. In English, 20 pages.

    Abstract: This paper presents an analysis of the fault coverage provided by the UIO-based methods for testing communications protocols. Formal analysis of the fault coverage for the non-optimized method and for some of its optimized versions are presented. A test is said to provide full coverage if no erroneous implementation can pass the test. In the case of optimizations based on the Rural Chinese Postman Tour [1] it is shown that unless certain conditions are met the method does not guarantee full fault coverage, even when, as suggested in [3], the uniqueness of UIO sequences (or Partial UIO sequences) are verified in the implementation. The result of the analysis suggests how the existing methods for generating test sequences should be changed in order to guarantee full fault coverage.

  • DCC-95-05 pdf bib
    Protocols for maintaining consistency of replicated data.
    Ricardo O. Anido and Nabor C. Mendonça.
    June 1995. In English, 33 pages.

    Abstract: Data replication is a useful technique for improving the performance and availability in distributed database systems. Most of the protocols proposed in the literature to control the access to the replicated data use some form of voting for maintaining the data consistent, and follow a pessimistic approach, in the sense that they prevent possibly unsafe changes to the replicated data. In this paper several of those protocols are described and compared. Some optimistic protocols, and some protocols not based on voting are also briefly presented.

  • DCC-95-04 pdf bib
    A greedy method for edge-coloring odd maximum degree doubly chordal graphs.
    Celina M. H. de Figueiredo, João Meidanis, and Célia P. de Mello.
    June 1995. In English, 7 pages.

    Abstract: We describe a greedy vertex coloring method which can be used to color optimally the edge set of certain chordal graphs. This new heuristic yields an exact edge-coloring algorithm for odd maximum degree doubly chordal graphs. This class includes interval graphs and strongly chordal graphs. This method shows that any such graph $ G $ can be edge-colored with maximum degree $ \ Delta (G) $ colors, ie, all these graphs are Class $ $ 1🇧🇷 In addition, this method gives a simple $ \ Delta (G) + 1 $ edge-coloring for any doubly chordal graph.

  • DCC-95-03 pdf bib
    W3 in undergraduate education?
    Hans K. E. Liesenberg.
    March 1995. In Portuguese, 8 pages.

    Summary: An experience of a paradigm shift in the teaching of undergraduate courses at Unicamp based on the W3 service on the Internet is reported. Instead of the traditional class, where the student plays a more passive role, a more exploratory character was given to the classes, which required a more active role on the part of the students. A preliminary assessment of the experience is presented here.

  • DCC-95-02 pdf bib
    Adaptive enumeration of implicit surfaces with affine arithmetic.
    Luiz H. de Figueiredo and Jorge Stolfi.
    March 1995. In English, 16 pages.

    Abstract: We discuss adaptive enumeration and rendering methods for implicit surfaces, using octrees computed with affine arithmetic, a new tool for range analysis. Affine arithmetic is similar to standard arithmetic interval, but takes into account correlations between operands and sub-formulas, generally providing much tighter bounds for the computed quantities. The resulting octrees are accordingly much smaller, and the rendering faster. We also describe applications of affine arithmetic to intersection and ray tracing of implicit surfaces.

  • DCC-95-01 pdf bib
    Paradigms of algorithms in solving multidimensional search problems.
    Pedro J. de Rezende and Renato Fileto.
    January 1995. In Portuguese, 17 pages.

    Summary: In this work, we describe some search problems in subspaces (range search) and solutions found in the literature, from which two paradigms of algorithms are identified: partition trees and linearization. These paradigms lead to some of the asymptotically optimal solutions and to generalized solutions to certain types of subspace search problems. The adopted approach allows a general and comprehensive view of the techniques involved, facing several different solutions as variations of the same basic concept. We also highlight possibilities of application and open questions, raising the possible impacts of the evolution of research regarding multidimensional searches.


  • Instituto de Computação :: State University of Campinas
    PO Box 6176 • Av. Albert Einstein, 1251 - Cidade Universitária • CEP 13083-970 • Campinas / SP - Brazil • Phone: [19] 3521-5838