Technical Reports Published in 1994

  • DCC-94-12 pdf bib
    An asynchronous team specification methodology.
    Hélvio P. Peixoto and Pedro S. de Souza.
    November 1994. In Portuguese, 8 pages.

    Summary: Asynchronous Teams (A-Teams) make up a new problem solving technique based on the simultaneous use of several heuristic algorithms, which cooperate synergistically, finding optimal or almost optimal solutions, which would not be found by the algorithms in isolation. As it is a recent technique, the specifications of A-Teams so far they have occurred empirically. This article describes a methodology for specifying A-Teams, facilitating its use in solving Combinatorial Optimization problems.

  • DCC-94-11 pdf bib
    Matching covered graphs and subdivisions of $ K_4 $ and $ \ overline {C_6} $.
    Marcelo H. Carvalho and Cláudio L. Lucchesi.
    December 1994. In English, 5 pages.

    Abstract: We give a very simple proof that every non-bipartite matching covered graph contains a nice subgraph that is an odd subdivision of $ K_4 $ or $ \ overline {C_6} $. It follows immediately that every brick different from $ K_4 $ and $ \ overline {C_6} $ has an edge whose removal preserves the matching covered property. These are classical and very useful results due to Lovász.

  • DCC-94-10 pdf bib
    Introduction to statograms.
    Fábio N. de Lucena and Hans K. E. Liesenberg.
    November 1994. In Portuguese, 17 pages.

    Summary: Stadogram it is a notation aimed at modeling the complex behavior of reactive systems. This text describes its characteristics as language (its lexicon, its syntax and, informally, its semantics), its origins (reactive and objective systems), jobs and tools that use it. We sought to provide a comprehensive and didactic view, including those already familiar with this notation. There is also an extensive list of relevant references.

  • DCC-94-09 pdf bib
    A Prolog morphological analyzer for Portuguese.
    Jacques Wainer and Alexandre Farcic.
    October 1994. In English, 10 pages.

    Abstract: This paper describes a morphological analyzer for Portuguese written in Prolog. It understands about the standard declinations for noun, adjectives, and regular verbs and it also understands about prefixes and suffixes. The system is not only able to recognize a word if its root is in the dictionary, but also to infer (or rather guess) the lexical classes of words whose roots are not in the dictionary by using its knowledge of declinations and suffixes.

  • DCC-94-08 pdf bib
    Reasoning about another agent through empathy.
    Jacques Wainer.
    September 1994. In English, 9 pages.

    Abstract: This paper formalizes the idea of ​​reasoning about the knowledge of another agent by `` putting oneself on the other's shoes, '' and then attributing to the other agent the conclusions that follows from that. We call this form of reasoning empathy. We formalize empathy for monotonic knowledge and show that the same principles would apply to nonmonotonic knowledge, that is reasoning about the knowledge of nonmonotonic agents.

  • DCC-94-07 pdf bib
    Human-computer interfaces: A first introduction.
    Fábio N. de Lucena and Hans K. E. Liesenberg.
    September 1994. In Portuguese, 29 pages.

    Summary: Increasing emphasis has been placed on human-computer interfaces. This text presents evidence to justify this fact. The content of this work aims to serve as an initial reading on the subject with an emphasis on computational aspects. More specifically, how the topic relates to the area of ​​software engineering. However, contributions from other areas are cited for this multidisciplinary topic. Some fundamental concepts are defined, techniques, models, life cycle and other relevant issues are presented. Although the text is succinct, we hope that the bibliography presented indicates other sources with more information.

  • DCC-94-06 pdf bib
    Asynchronous Teams: A new technique for the flow shop problem.
    Hélvio P. Peixoto and Pedro S. de Souza.
    July 1994. In English, 19 pages.

    Summary: This article presents the description of A-Teams for the task scheduling problem called Flow Shop Problem. A-Teams make up a new problem solving technique based on the simultaneous use of several heuristic algorithms, which cooperate synergistically, finding optimal or almost optimal solutions, which would not be found by the algorithms in isolation. The results obtained are compared with the results provided by the most significant heuristics found in the literature.

  • DCC-94-05 pdf bib
    Using versions in GIS.
    Claudia M. B. Medeiros and Geneviève Jomier.
    June 1994. In English, 22 pages.

    Abstract: Geographic information systems GIS have become important tools in public planning activities (eg, in environmental or utility management). This type of activity requires the creation and management of alternative scenarios, as well as analysis of temporal data evolution. Existing systems provide limited support for these operations, and appropriate tools are yet to be developed.

    This paper presents a solution to this problem. This solution is based on managing temporal data and alternatives using the DBV version mechanism. It provides efficient handling and storage of versions, and supports the creation of alternatives for decision-making activities.

    A reduced version of this report appeared in the Proceedings of the DEXA'94 Conference - 5th International Conference on Database and Expert Systems Applications, Athens, Greece.

  • DCC-94-04 pdf bib
    On edge-coloring indifference graphs.
    Celina M. H. de Figueiredo, João Meidanis, and Célia P. de Mello.
    June 1994. In English, 23 pages.

    Abstract: Vizing's theorem states that the chromatic index $ \ chi '(G) $ of the graph $ G $ is either the maximum degree $ \ Delta (G) $ or $ \ Delta (G) + 1 $. A graph $ G $ is called overfull if $ \ vert E (G) \ vert> \ Delta (G) \ lfloor {\ vert V (G) \ vert / 2} \ rfloor $. A sufficient condition for $ \ chi '(G) = \ Delta (G) + 1 $ is that $ G $ contains an overfull subgraph $ H $ With $ \ Delta (H) = \ Delta (G) $. Plantholt proved that this condition is necessary for graphs with a universal vertex. In this paper, we conjecture that, for indifference graphs, this is also true. As supporting evidence, we provide this conjecture for general graphs with three maximal clicks and with no universal vertex, and for indifference graphs with odd maximum degree. For the latter subclass, we prove that $ \ chi '= \ Delta $.

  • DCC-94-03 pdf bib
    The KMP algorithm using automata.
    Marcus V. A. Andrade and Cláudio L. Lucchesi.
    April 1994. In English, 13 pages.

    Summary: In this article we present a description of the KMP algorithm through automata that makes understanding this algorithm quite simple. In addition, this approach also facilitates considerably the complexity analysis of the algorithm, to the point that we can easily obtain a real-time version of it, as presented in the article.

  • DCC-94-02 pdf bib
    Incorporation of time in an object-oriented DBMS.
    Ângelo R. A. Brayner and Claudia M. B. Medeiros.
    April 1994. In English, 25 pages.

    Summary: This paper describes the Time Management Layer, a time management subsystem implemented for the O2 object-oriented database. This subsystem allows the definition of temporal schemes and the manipulation (queries and updates) of objects in those schemes. These commands are translated by the subsystem into programs and queries executed by the underlying database. The presented work contributes to the discussion about the implementation of object-oriented temporal systems, little explored in the literature.

  • DCC-94-01 pdf bib
    A statechart engine to support implementations of complex behavior.
    Fábio N. de Lucena and Hans K. E. Liesenberg.
    March 1994. In English, 26 pages.

    Abstract: The statechart notation was devised for specifying complex behavior of reactive systems. The gap between a behavior described in terms of statecharts and its implementation, however, is still very large due to its intricate semantics and its main purpose as specification language. In order to overcome this gap we propose a new technique which frees the programmer from the subtle and error-prone activity of mapping a specification into an implementation. The technique is centered upon a reactive kernel.

    The reactive kernel consists of an invariant engine which interprets statechart specifications. Actions are supplemented in terms of a set of subroutines in C. The engine invokes these subroutines at proper instants during the application execution as a reaction to particular events. The reactive kernel implementation is the major issue of this paper. In order to exemplify our proposal the behavior of a toy application is employed.


  • 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