Summary: We present the detailed description of an EGOLib function library built on the system X for manipulating graphic objects, which provides facilities for updating such objects while modifying attributes. Although the library xlib provides functions for this purpose, it is desirable to be able to allow the user a higher level access to modifications of such attributes and in a uniform manner.

EGOLib's objective is to provide these functions to the user in a homogeneous way, allowing the creation of much more elegant code than is possible using purely xlib.

This document presents a reference manual for this library, consisting of a detailed description of the graphic objects and their attributes.

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 behavior 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 reactive 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 (excluding or) is still open.

Abstract: We describe a Computational Geomeasurement 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, ie 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 behavior 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 (eg, 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.

Summary: Heterogeneous Database Systems (SBDHs) are systems that integrate, in a cooperative environment, autonomous and heterogeneous database systems (SBDs), with respect to the semantics of your data and / or to the characteristics of your DBMS (model of data manipulation languages ​​and implementation aspects). A desirable property in these systems is the transparency of models, which allows the user to see and manipulate the data located in different SBDs, through the model and the data manipulation language he used in his local SBD, before it was incorporated into the SBDH . The property in question is achieved through the mapping between the data and operations of the component SBDs. This work presents methodologies for converting schematics into SBDHs built to integrate SBDs that use the network data model or the relational data model. These methodologies are important for achieving model transparency.

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 (ie, 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 modeling 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 modeling 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 (Didactic System for the OSI Model - 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.

Summary: The present work presents some specific techniques, which can be applied, together with the traditional ones, for the reduction of energy consumption in equipment based on microprocessors, whose operation characteristic is activity cycles separated by waiting cycles without any work useful to be carried out. These techniques were applied in the development of a meteorological data acquisition system, enabling the use of batteries in long-term experiments in remote locations without electricity.

Summary: Advances in digital technology already allow for several applications employing the transmission of digital video images. However, there are some problems that arise when it comes to transmitting digital images in real time. Due to limitations imposed by the bandwidth of most local networks, it is usually impossible to transmit all the large amount of information necessary to represent the images. Therefore, it is necessary to develop a fast method of image compression, which is capable of achieving high compression rates, maintaining a sufficiently good quality in the reproduced images.

This article proposes a method of compressing image sequences that combines vector quantization with strategies for the detection of movement and progressive transmission. A classification scheme is also introduced which aims to give a better representation to the edges of images reproduced by vector quantization. Some variations of the method are described and some experimental results are listed and analyzed.

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 provides the soundness of such logic.

Summary: While the relevance of human-computer interfaces in interactive systems is recognized, including commercially, the corresponding software is difficult to build. Several tools have been proposed to automate the generation of code from an interface. Most of these tools are state based and use state transition diagrams (DTEs) to specify the dialog control. However, these diagrams have drawbacks that make them unfeasible for specifying complex dialogues.

Stadograms (statecharts) show signs of being adequate to describe this type of behavior. They extend DTEs and eliminate the drawbacks of the latter. Although its use has been suggested in several works for the specification of dialog control, the results of experiments in using this notation for this particular job (as in other areas) are not discussed in the literature.

The use of statograms in the development of a real interface allowed to identify changes that make these diagrams more appropriate for this specific use, as well as limitations of this notation. Among the suggested adaptations are additional constructions to allow the specification of the presentation of an interface. The observation of the code generated by a tool used in this work, which implements statograms, still allowed to identify desirable elements regarding the structure of the code to be produced. This text reports the suggested changes and limitations of this notation obtained from the analysis of this empirical development. It also includes comments about desirable elements in the code structure to be produced by an implementation of this notation.

Summary: This document presents a database management system that was developed in order to allow the study of cooperative interfaces. The system adopts the relational model, using the resources of the PROLOG language to implement the relationships that make up the database and perform the evaluation of queries, which can be built interactively, making it unnecessary to know a formal language for accessing the bank. of data. The transformation of the user's query into a set of equivalent PROLOG goals involves an optimization process, which takes into account the state of the database and isolates the evaluation of independent parts of the query. The cooperative feature of the system is its ability to identify false user assumptions and to develop responses that correct them.

Summary: This work presents the design and implementation of a Cooperative Processing Management System (SGPC). The use of SGPC facilitates the exploitation of the parallelism capacity inherent to a local network. An Processing Server and a package of routines that serve as an interface for the server.

The system can be used in one of two levels: following the Client / Server model through Remote Procedure Calls (RPC's) directly to the server, or through library subroutines that are responsible for generating the RPCs and provide the user with a friendlier environment.

At both levels, remote executions are carried out with remote selection of the host machine and the transparency of these operations is guaranteed to system users. The choice of destination machines for migrations is based on the level of idleness of their CPUs.

The system aims to facilitate the development of low-cost parallel applications, to increase the overall processing speed of such applications, allowing the use of idle station resources.

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 click 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 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 modeling and generation of reactive systems.

The modeling is based on statecharts, an extension of conventional state transition diagrams, which favors 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 need description facilities of subtle behavioral aspects, punctual action definitions to be carried out in specific contexts and the capability of automatically transforming specifications into programs.