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.

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.

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).

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.

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.

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.

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 -time algorithm for this problem with taxa and characteristics. This bound is tight if the input is given as an 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.

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.

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.

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).

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.

.

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.

Abstract: A tension-free layout of a weighted graph is an embedding of 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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 can be edge-coloured with maximum degree colours, i.e., all these graphs are Class . In addition, this method gives a simple edge-colouring for any doubly chordal graph.

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.

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.

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.