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 plataform: 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: Um ambiente de testes baseado em injeção de falhas por software.
    Eliane Martins.
    December 1995. In Portuguese, 32 pages.

    Resumo: Uma das dificuldades no desenvolvimento de sistemas tolerantes a falhas diz respeito à sua validação. Essa dificuldade vem do fato de que os testes destes sistemas requerem a consideração de situações anormais, que ativem os mecanismos de tratamento de erros e de falhas existentes em tais sistemas.

    Uma técnica que vem sendo muito utilizada para este fim é a injeção de falhas, que consiste em introduzir erros/falhas em um sistema, de maneira controlada, e observar o seu comportamento.

    Neste texto é apresentado o ATIFS, um Ambiente para o Teste baseado em Injeção de Falhas por Software, que provê suporte para o desenvolvimento e execução de testes de sistemas tolerantes a falhas, bem como para a análise dos resultados obtidos nos testes. Uma importante característica do ATIFS é que ele permite o uso de um modelo formal do sistema, o qual pode servir de base tanto para a geração automatizada dos testes a serem aplicados quanto para a obtenção de uma referência a ser empregada na análise dos resultados. Para a escolha das entradas de teste, o ATIFS oferece ao usuário a possibilidade de definir testes estatísticos, baseados na distribuição de probabilidades associada ao domínio de entrada. A realização de testes estatísticos baseados no modelo do sistema permite que o ATIFS forneça suporte tanto para a verificaçã do comportamento do sistema em presença de falhas, quanto para a avaliação de medidas da eficiência dos seus mecanismos de detecção/recuperação de erros/falhas, característica que o diferencia da maioria dos ambientes de testes por injeção de falhas.

  • DCC-95-23 pdf bib
    Cálculo de la estructura de un texto en un sistema de procesamiento de lenguaje natural.
    Horacio Saggion and Ariadne M. B. R. Carvalho.
    December 1995. In Spanish, 13 pages.

    Resumen: Calcular la estructura lingüística de un texto es fundamental en cualquier sistema de procesamiento de lenguaje natural. Para eso, fenómenos mas allá de la barrera de la sentencia deben ser considerados. En particular, dos estudios deben ser abordados en el procesamiento de un texto: la cohesión textual y la coherencia textual. En este trabajo definimos una representación para la estructura de un resumen en lengua portuguesa considerado como un fenómeno lingüístico. La representación fue obtenida a partir del estudio de resúmenes reales y de la verificación de relaciones entre sentencias en el texto. Consideramos que este tipo de representación puede ser utilizada para otros textos, ya que es definida en función de relaciones de cohesión y coherencia. El principal aspecto considerado en este trabajo para la construcción de la estructura textual es la cohesión a través de la resolución de anáforas definidas tanto pronominales como frases nominales definidas. Presentamos ejemplos de texto reales y su tratamiento en el marco teórico propuesto.

  • DCC-95-22 pdf bib
    Text structure aiming at machine translation.
    Horacio Saggion and Ariadne M. B. 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$ taxa 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: Suas contribuições à computação.
    Tomasz Kowaltowski.
    December 1995. In Portuguese, 18 pages.

    Resumo: John von Neumann, um dos maiores cientistas do Século XX, fez importantes contribuições a várias áreas, destacando-se os seus trabalhos em Matemática, Matemática Aplicada, Física, Meteorologia, Economia e Computação. Em vários casos, as suas contribuições foram muito além de solução de problemas propostos por outros, desbravando novas áreas de pesquisa e lançando novos problemas. O objetivo deste trabalho é mostrar as contribuições de von Neumann à Computação e, em particular, à arquitetura de computadores digitais, à programação de computadores e à teoria da computação.

    Este trabalho foi preparado para a palestra proferida durante o encontro A Obra e o Legado de John von Neumann, organizada pelo Instituto de Estudos Avançados da Universidade de São Paulo e pela Academia Brasileira de Ciências, no dia 14 de novembro de 1995, no Instituto de Matemática e Estatística da Universidade de São Paulo.

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

    Resumo: O texto consiste de um tutorial que fornece ao usuário, com noções básicas de programação orientada a objetos em C++, uma introdução elucidativa à programação baseada no ``toolkit'' wxWindows. Este pacote é uma ferramenta de domínio público, com implementações para várias plataformas (ftp.aiai.ed.ac.uk:pub/packages/wxwin).

    O tutorial trata exclusivamente da interface de programação do wxWindows e como ela pode ser usada na construção de interfaces homem-computador. Vários exemplos são fornecidos.

  • 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
    Anais da II Oficina Nacional em Problemas Combinatórios: Teoria, Algoritmos e Aplicações.
    Marcus V. S. Poggi de Aragão 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.
    • Uma adaptação do algoritmo de emparelhamento de Edmonds para execução em paralelo. 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 Aragão and Cid C. de Souza.
    .

  • DCC-95-16 pdf bib
    Agentes replicantes e algoritmos de eco.
    Marcos J. C. Euzébio.
    October 1995. In Portuguese, 9 pages.

    Resumo: Os algoritmos de eco formam uma classe de algoritmos distribuídos simples, versáteis e eficientes utilizados para a obtenção de informações globais de uma forma descentralizada. Normalmente estes algoritmos são implementados utilizando-se o paradigma de troca de mensagens, ainda que sua descrição siga a metáfora de agentes replicantes. Neste artigo será apresentado o ambiente de execução, que oferece a infra-estrutura para a execução de agentes replicantes, assim como a descrição de algumas experiências iniciais obtidas na programação de agentes replicantes, incluindo a implementação de uma instância dos algoritmos de eco.

  • 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 relate some experience with the technique.

  • DCC-95-13 pdf bib
    Modelos de computação paralela e projeto de algoritmos.
    Ronaldo P. de Menezes and João C. Setubal.
    August 1995. In Portuguese, 12 pages.

    Resumo: O modelo PRAM vem sendo já há mais de 15 anos o modelo principal para projeto e análise de algoritmos paralelos. A sua simplicidade o torna um modelo pouco fiel à realidade, o que motivou o aparecimento de extensões e de outros modelos, dentre os quais BSP (Valiant, 1990) e LogP (Culler et al., 1993). Apresentamos uma descrição sucinta desses 3 modelos e mostramos os diferentes níveis de abstração em que se situam. São apresentadas as vantagens e desvantagens de cada um, particularmente com relação ao projeto e análise de algoritmos. A relevância de cada um frente ao panorama atual de máquinas paralelas é discutida, concluindo-se que o modelo LogP, apesar de ser de mais baixo nível, é o que tem mais chance de se disseminar em situações práticas.

  • DCC-95-12 pdf bib
    Modelos computacionais para processamento digital de imagens em arquiteturas paralelas.
    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
    Processador de vizinhança para filtragem morfológica.
    Ilka M. Barros, Roberto A. Lotufo, and Neucimar J. Leite.
    August 1995. In Portuguese, 12 pages.

    Resumo: Este trabalho apresenta uma arquitetura sistólica para implementação de operações de morfologia matemática (filtros morfológicos). Esta arquitetura denominada SAMM (Systolic Architecture for Mathematical Morphology) implementa as operações de dilatação e erosão com um elemento estruturante planar. Ela apresenta dois níveis de modularidade, o primeiro decorrente da implementação no mesmo hardware de operações numéricas e binárias, o outro devido ao caráter sistólico do seu processamento. Levando-se em conta fatores como desempenho, tempo de execução de operações e arquitetura, foram escolhidos alguns processadores que implementam filtros de morfologia matemática para comparação funcional e de complexidade com a arquitetura desenvolvida.

  • 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
    Bases 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 modelled 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-colouring 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 colouring method which can be used to colour optimally the edge set of certain chordal graphs. This new heuristic yields an exact edge-colouring 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-coloured with maximum degree $\Delta(G)$ colours, i.e., all these graphs are Class $1$. In addition, this method gives a simple $\Delta(G) + 1$ edge-colouring for any doubly chordal graph.

  • DCC-95-03 pdf bib
    W3 no ensino de graduação?
    Hans K. E. Liesenberg.
    March 1995. In Portuguese, 8 pages.

    Resumo: É relatada uma experiência de uma mudança de paradigma no ensino de disciplinas de graduação na Unicamp calcada no serviço W3 da Internet. Ao invés da aula tradicional, onde o aluno exerce um papel mais passivo, imprimiu-se um caráter mais exploratório às aulas que exigiu uma atuação mais ativa por parte dos alunos. Uma avaliação preliminar da experiência é aqui apresentada.

  • 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 interval arithmetic, 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
    Paradigmas de algoritmos na solução de problemas de busca multidimensional.
    Pedro J. de Rezende and Renato Fileto.
    January 1995. In Portuguese, 17 pages.

    Resumo: Neste trabalho, descrevemos alguns problemas de busca em subespaços (range search) e soluções encontradas na literatura, a partir das quais são identificados dois paradigmas de algoritmos: árvores de partição e linearização. Estes paradigmas levam a algumas das soluções assintoticamente ótimas e a soluções generalizadas para determinados tipos de problemas de busca em subespaços. A abordagem adotada possibilita uma visão geral e abrangente das técnicas envolvidas, encarando diversas soluções distintas como variações de uma mesma concepção básica. Realçamos ainda possibilidades de aplicação e questões abertas, levantando os possíveis impactos da evolução das pesquisas a respeito de buscas multidimensionais.


  • Instituto de Computação :: Universidade Estadual de Campinas
    Caixa Postal 6176 • Av. Albert Einstein, 1251 - Cidade Universitária • CEP 13083-970 • Campinas/SP - Brasil • Fone: [19] 3521-5838