Resumo: Apresentamos a descrição detalhada de uma biblioteca de funções EGOLib construída sobre o sistema X para manipulação de objetos gráficos, que provê facilidades para atualização de tais objetos enquanto modificações de atributos são realizadas. Embora a biblioteca xlib proveja funções para esta finalidade, é desejável que se possa permitir ao usuário um acesso de mais alto nível a modificações de tais atributos e de maneira uniforme.

O objetivo da EGOLib é prover tais funções ao usuário de forma homogênea, permitindo a criação de código muito mais elegante do que é possível usando-se puramente funções de xlib.

Neste documento é apresentado um manual de referência desta biblioteca, constando de uma descrição detalhada dos objetos gráficos e de seus atributos.

Abstract: This paper presents a technique to implement control of complex user interface dialogues. It is based on event-driven control flow specifications described by a deterministic statechart dialect. With the aid of this technique the dialogue control is expressed in terms of a statechart. This statechart is then converted into tables handled by a run-time commented in greater detail. The execution of the run-time driven by those tables is equivalent to the behaviour specified by the underlying statechart. The resulting system calls specific application functions in response to user interactions mapped to events by the presentation component. The application is seen as a set of subroutines which can be invoked during the interaction with the user. The use of the proposed technique frees the programmer from the implementation of complex control aspects. The way of how to construct these statechart dependent tables, their use by the run-time, and the way semantic actions are attached are illustrated by a small example of a reative system which highlights mainly dialogue control aspects.

Abstract: Motivated by very similar characterizations given in the literature for chordal, interval, and indifference graphs we introduce a way of defining classes of graphs in terms of boolean functions of two variables. Each such function originates a class of graphs. Denoting the variables by and , the functions , , and originate the classes of chordal, interval, and indifference graphs, respectively. In this paper we study the classes corresponding to all other boolean functions, as well as general properties of these classes. A satisfactory identification of the class corresponding to function (exclusive or) is still open.

Abstract: We describe a Computational Geometry Laboratory which we developed as a programming environment for implementation, testing and animation of geometric algorithms. GeoLab was conceived to be a tool for the working researcher or a group of them, since at its root lie the use of shared libraries of algorithms and an incremental approach to aggregating new types of geometric objects, data structures and extensions accessed through dynamic linking.

Abstract: We describe various forms of algorithm animation which have been studied, presentation techniques and programming environments developed for this purpose in recent years. We present a description of the environment AnimA, which we designed and implemented with the goal of aiding in the process of production of algorithm animation providing users with facilities for the production of animations of any algorithm in a systematic way, by means of congregating in a single environment tools for animation support such as: uniform graphical interface, preprocessing system, automatic maintenance of libraries, reusability of shared libraries and dynamic linking.

Abstract: We present a description of a library of functions (EGOlib) built on the X-Window system for the manipulation of graphics objects, which provides facilities for the update of such objects while modifications of attributes of the objects are made. This library constitutes a level above the xlib library, allowing the user a higher level access to modifications of various attributes on a homogeneous and uniform way, resulting in more elegant code than is possible using purely xlib functions.

The concept of class hierarchy, present in object oriented languages, is used for creating the classes of graphics objects, from some simple ones up to composed objects such as binary trees.

Applications of EGOlib are abundant, and in particular, this library has been used for the implementation of algorithm animations.

Abstract: DNA fragment assembly (FA) is an important problem in molecular biology. It appears in large-scale DNA sequencing tasks. Research related to the FA problem has mainly focused into two approaches: (1) development of software tools useful in practice but using heuristic methods difficult to analyze formally, and (2) formal modeling through theoretical problems, which captures some but not all of the real issues in FA. Our goal is to hybridize these two approaches by building a software tool that is useful to the biologists and has well-understood formal properties.

Abstract: Finite automata used to represent large vocabularies of natural languages are quite sparse in the following sense: for the vast majority of states, almost all transitions lead to the rejecting state. This suggests a representation of the automaton in which each state is a small list of transitions entering non rejecting states. It is then possible to factor parts of those lists, thereby saving further space. Depending on the order in which the transitions appear on the lists, the degree of saving varies. This leads to the problem of minimizing such representations. This problem is interesting from a theoretical point of view and quite useful from a practical point of view, as the experimental results presented herein indicate.

Abstract: Finite acyclic automata can be used as a very versatile tool in many applications involving natural language vocabularies. This work describes some experiments in ``debugging'' semi-automatically such vocabularies, i.e. suggesting non-existent and missing words. Partial statistics are shown for Portuguese, Italian and English vocabularies.

Abstract: The process of software development of human-computer interfaces is complex and expensive. Many tools to automate the interface code generation have been proposed. The majority of these tools defines the behaviour of a system in terms of states and use conventional state transition diagrams (STDs) in order to describe dialogue control aspects. The statechart notation extends STDs to overcome some of their drawbacks. This paper shows the results gained from experiences of the use of statecharts in the development of user interfaces. These experiences led to the identification of improvements and additional constructs which are needed in order to make them more adequate for this specific usage in the even broader domain of distributed environments.

Abstract: This paper discusses the use of VHDL as a language for modeling, simulating, and synthesizing integrated circuits, and the language suitability to each of these tasks. It also discusses the problems related to the transition between different levels of abstraction to obtain a synthesizable VHDL model.

Abstract: Production rules in database systems have been used mostly for integrity-related issues (e.g., derived data maintenance, authority checking and constraint verification). This paper analyzes the need for using production rules in geographic information systems, for a special family of applications--utility management systems. This framework is applied to a real life large scale application--the development of an integrated database system for the maintenance and expansion of the telephone network in Brazil.

Resumo: Sistemas de Bancos de Dados Heterogêneos (SBDHs) são sistemas que integram, num ambiente cooperativo, sistemas de bancos de dados (SBDs) autônomos e heterogêneos entre si, com relação à semântica dos seus dados e/ou às características dos seus SGBDs (modelo de dados, linguagens de manipulação de dados e aspectos de implementação). Uma propriedade desejável nesses sistemas é a transparência de modelos, que permite ao usuário enxergar e manipular os dados localizados em diferentes SBDs, através do modelo e da linguagem de manipulação de dados que ele utilizava no seu SBD local, antes do mesmo ser incorporado ao SBDH. A propriedade em questão é conseguida através do mapeamento entre os dados e operações dos SBDs componentes. Este trabalho apresenta metodologias para conversão de esquemas em SBDHs construídos para integrar SBDs que utilizam o modelo de dados rede ou o modelo de dados relacional. Essas metodologias são importantes para obtenção da transparência de modelos.

Abstract: This is the preliminary version of the reference manual for the language designed for easy interfacing with complex libraries and testing of algorithms written in a natural way, avoiding complexities of typical system programming languages. Generality is achieved through the fact that the language is completely object-oriented. It provides traditional syntax and extended semantics for its declarations, statements and expressions. Some of the most common data types and data structuring mechanisms are provided within the language, but it is expected that most of them will be defined through application oriented interfaces.

Abstract: In large distributed computing systems, where copies of the same logical data are stored at many different sites, the replica control protocol must reduce communication costs when forming the quorums required at each access to the replicated data, in order to improve the system response time. An interesting way to achieve this reduction is to organize the copies into some logical structure, like a grid or a tree, and then to use this structure to form smaller quorums. Another example of a structure used to form smaller quorums is a generic tree in which only the leaves correspond to copies of the replicated data.

This paper presents a new replica control protocol that logically organizes the copies as leaves of a generic tree, but introduces the blind-write as another operation (besides the traditional read and write) defined over the replicated data. With this third operation, the proposed protocol turns out to be a generalization of the traditional voting scheme and others existing protocols that use a symmetrical logical structure (i.e., a structure in which the responsibility for controlling the replicated data is equally shared by all copies) to form the access quorums. The proposed protocol also makes possible to achieve better relations between quorums size and the total number of copies, even under high availability requirements.

Abstract: This paper presents a new approach for modelling and querying temporal object oriented databases. The model presented in this paper extends previous work in the area, by supporting the evolution of all object properties through time (inheritance, composition and behavior), and allowing temporal schema evolution. A prototype of this model is being implemented as a time-managing layer on top of the O2 object-oriented database system. In order to manipulate our temporal objects, we have extended the O2 query language with temporal constructs, which we also discuss in the paper.

Abstract: Geographic information systems demand the processing of complex data using specialized operations, not available in traditional database systems. Even though there exist commercial systems that provide some of these facilities, there is a lack of proper support, which should cover not only the implementation but also the design stage. This paper answers this latter need, discussing the steps for modelling databases for geographic information systems using the paradigm of object orientation.

Abstract: Consider a set of logical sentences together with probabilities that they are true. These probabilities must satisfy certain conditions for this system to be consistent. It is shown that an analytical form of these conditions can be obtained by enumerating the extreme rays of a polyhedron. We also consider the cases when: (i) intervals of probabilities are given, instead of single values; (ii) best lower and upper bounds on the probability of an additional logical sentence to be true are sought. Enumeration of vertices and extreme rays is used. Each vertex defines a linear expression and the maximum (minimum) of these defines a best possible lower (upper) bound on the probability of the additional logical sentence to be true. Each extreme ray leads to a constraint on the probabilities assigned to the initial set of logical sentences. Redundancy in these expressions is studied. Illustrations are provided in the domain of reasoning under uncertainty.

Abstract: This technical report presents a structure for a modular implementation of application contexts from the RM-OSI/ISO (Reference Model--Open Systems Interconnection / International Organization for Standardzation) in which the TP (Transaction Processing) protocol participates. This protocol provides services to support the execution of distributed atomic transactions in the OSI environment. The structure presented influences the implementation of other application contexts.

In this text it is also shown the way the upper layers protocols are being implemented in a didactic communication system called SISDI-OSI (Sistema Didático para o Modelo OSI--Didactic System for the OSI Model) in terms of process configuration and interprocess communication mechanisms. The experiences with protocol implementations for this system are then commented.

Resumo: O presente trabalho apresenta algumas técnicas especificas, que podem ser aplicadas, em conjunto com as tradicionais, para a redução de consumo de energia em equipamentos baseados em microprocessadores, que tenham como característica de operação ciclos de atividades separados por ciclos de espera sem que algum trabalho útil seja realizado. Estas técnicas foram aplicadas no desenvolvimento de um sistema de aquisição de dados meteorológicos, possibilitando o uso de baterias em experimentos de longa duração em locais remotos não providos de energia elétrica.

Resumo: Avanços na tecnologia digital já permitem várias aplicações empregando a transmissão de imagens digitais de vídeo. Entretanto, existem alguns problemas que surgem quando se trata de transmissão de imagens digitais em tempo real. Devido a limitações impostas pela largura de banda da maioria das redes locais, normalmente é impossível transmitir toda a grande quantidade de informação necessária para representar as imagens. Portanto, é necessário que se elabore um método rápido de compressão de imagens, que seja capaz de atingir altas taxas de compressão, mantendo uma qualidade suficientemente boa nas imagens reproduzidas.

Neste artigo é proposto um método de compressão de seqüências de imagens que combina quantização vetorial com estratégias de detecção de movimento e transmissão progressiva. Também é introduzido um esquema de classificação que tem o objetivo de dar uma melhor representação às arestas de imagens reproduzidas por quantização vetorial. São descritas algumas variações do método e são listados e analisados alguns resultados experimentais.

Abstract: This paper develops the formal aspects of a new apporach to reasoning about the knowledge of other agents. It is based on the principles of introspection, by which an agent is aware of the inferences he makes, and projection, by which an agent assumes that other agents have the same inference abilities as himself. The paper develops a logic that incorporates these principles and proves the soundness of such logic.

Resumo: Enquanto é reconhecida a relevância de interfaces homem-computador em sistemas interativos, inclusive comercialmente, o software correspondente é difícil de ser construído. Várias ferramentas têm sido propostas para automatizar a geração de código de uma interface. Grande parte destas ferramentas são baseadas em estados e usam diagramas de transição de estados (DTEs) para especificação do controle de diálogo. Contudo, estes diagramas apresentam inconvenientes que os tornam inviáveis para a especificação de diálogos complexos.

Estadogramas (statecharts) apresentam indícios de serem adequados para descrever este tipo de comportamento. Estendem os DTEs e eliminam inconvenientes dos últimos. Embora seu emprego seja sugerido em vários trabalhos para a especificação de controle de diálogo, os resultados de experiências na utilização desta notação para este emprego particular (como ocorre em outras áreas) não são discutidos na literatura.

O uso dos estadogramas no desenvolvimento de uma interface real permitiu identificar mudanças que tornam estes diagramas mais apropriados para este emprego específico bem como limitações desta notação. Entre adaptações sugeridas encontram-se construções adicionais para permitir a especificação da apresentação de umainterface. A observação do código gerado por uma ferramenta utilizada neste trabalho, que implementa estadogramas, ainda permitiu identificar elementos desejáveis quanto a estrutura do código a ser produzida. Este texto relata as mudanças sugeridas e limitações desta notação obtidos da análise deste desenvolvimento empírico. Ainda inclui comentários acerca de elementos desejáveis na estrutura do código a ser produzida por uma implementação desta notação.

Resumo: Este documento apresenta um sistema de gerenciamento de bancos de dados que foi desenvolvido com o objetivo de permitir o estudo de interfaces cooperativas. O sistema adota o modelo relacional, utilizando os recursos da linguagem PROLOG para implementar as relações que compõem o banco de dados e realizar a avaliação de consultas, que podem ser construídas de forma interativa, tornando desnecessário o conhecimento de uma linguagem formal de acesso ao banco de dados. A transformação da consulta do usuário num conjunto de metas PROLOG equivalentes envolve um processo de otimização, que leva em conta o estado do banco de dados e isola a avaliação de partes independentes da consulta. A característica cooperativa do sistema está em sua capacidade de identificar falsas pressuposições do usuário e elaborar respostas que as corrijam.

Resumo: Este trabalho apresenta o projeto e a implementação de um Sistema Gerenciador de Processamento Cooperativo (SGPC). A utilização do SGPC facilita a exploração da capacidade de paralelismo inerente a uma rede local. Foram desenvolvidos um Servidor de Processamento e um pacote de rotinas que serve de interface para o servidor.

A utilização do sistem apode ser feita em um de dois níveis: seguindo o modelo Cliente/Servidor através de Chamadas Remotas de Procedimentos (RPC's) diretamente ao servidor, ou através de subrotinas de biblioteca que se encarregam de gerar as RPCs e fornecem ao usuário um ambiente mais amigável.

Em ambos os níveis se realizam execuções remotas com seleção remota da máquina hospedeira e garante-se a transparência destas operações para os usuários do sistema. A escolha das máquinas de destino das migrações baseia-se no nível de ociosidade de suas CPUs.

O sistema visa facilitar o desenvolvimento de aplicações paralelas de baixo custo de implementação, aumentar a velocidade de processamento global de tais aplicações, permitindo o aproveitamento dos recursos de estações ociosas.

Abstract: Interval graphs are the intersection graphs of families of intervals in the real line. If the intervals can be chosen so that no interval contains another, we obtain the subclass of proper interval graphs. In this paper, we show how to recognize proper interval graphs with one lexBFS. This algorithm runs in linear time, and produces as a by-product the clique partition of the input graph.

Abstract: The matching problem in graphs consists in determining matchings, that is, vertex disjoint sets of edges of the graph. In particular, we are interested in finding maximum matchings, that is, matchings of maximum cardinality. There are many variations around this problem, the graph can be: bipartite or not, weighted or not.

In this work we describe briefly the most important algorithms for solving the problem of maximum matching, weighted or not, in bipartite graphs. At the end of the article we give a table which describes briefly the most important algorithms for solving the general problem, in which the graph is not necessarily bipartite.

Abstract: Voting is the traditional mechanism used for maintaining the consistency of replicated data in distributed systems. One of the problems involved in voting mechanisms is the size of the quorums needed on each access to the data. To reduce the quorum size needed for voting, some protocols for copy consistency organize the copies into some logical structure, and use the this structure during the voting process.

We present two new protocols for maintaining copy consistency. Both protocols organize the copies into a ring structure, and use the adjacency property to reduce the read and write quorums. The flat ring protocol uses one single ring and achieves a read quorum of two copies (constant), and a write quorum equal to the majority of copies. The hierarchical ring protocol is a generalization of the flat ring protocol and uses a multi-level ring structure. The read quorum in the hierarchical ring protocol is independent on the total number of copies, and the write quorum is, in general, smaller than the majority of the copies. Both protocols are tolerant to multiple failures and do not need any special reconfiguration procedures when failures occur.

Abstract: This paper describes an environment and associated techniques which support the modelling and generation of reactive systems.

The modelling is based on statecharts, an extension of conventional state transition diagrams, which favours event-driven control aspects related to context swappings which can become very complex in non-trivial reactive systems. Contexts are defined incrementally and thus a more structured specification approach is encouraged. Semantics is aggregated in terms of attributes of statechart elements expressed as functions in C code.

At a second stage, a translation of a model into a functionally equivalent program in C takes place. Special emphasis is given to the invariant part of the generated code, referred to as the statechart engine, and to the binding of logical events to events recognized by the underlying kernel driving input/output devices.

The major advantages brought by the environment are precise description facilities of subtle behavioural aspects, punctual action definitions to be carried out in specific contexts and the capability of automatically transforming specifications into programs.