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).
Summary: One of the difficulties in the development of fault-tolerant systems concerns their validation. This difficulty comes from the fact that the testing of these systems requires the consideration of abnormal situations, which activate the mechanisms for handling errors and failures existing in such systems.
A technique that has been widely used for this purpose is fault injection, which consists of introducing errors / failures in a system, in a controlled manner, and observing its behavior.
This text presents ATIFS, a Test Environment based on Fault Injection by Software, which provides support for the development and execution of tests of fault tolerant systems, as well as for the analysis of the results obtained in the tests. An important feature of ATIFS is that it allows the use of a formal model of the system, which can serve as a basis both for the automated generation of the tests to be applied and for obtaining a reference to be used in the analysis of the results. For the choice of test entries, ATIFS offers the user the possibility to define statistical tests, based on the distribution of probabilities associated with the input domain. The performance of statistical tests based on the system model allows ATIFS to provide support both for the verification of the system's behavior in the presence of failures, and for the evaluation of measures of the efficiency of its error detection / recovery mechanisms, a characteristic that sets it apart from most fault injection test environments.
Summary: Calculating the linguistic structure of a text is fundamental in any natural language processing system. For this, phenomena but all of the sentence's barrier must be considered. In particular, the studies should be addressed in the processing of a text: textual cohesion and textual coherence. In this work we define a representation for the structure of a summary in Portuguese language considered as a linguistic phenomenon. The representation was obtained from the study of real summaries and the verification of relationships between sentences in the text. We believe that this type of representation can be used for other texts, which is defined in terms of cohesion and coherence relationships. The main aspect considered in this work for the construction of the textual structure is the cohesion through the resolution of defined anaphors both pronouns and defined nominal phrases. We present examples of real text and their treatment within the proposed theoretical framework.
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
rate 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.
Summary: John von Neumann, one of the greatest scientists of the XNUMXth century, made important contributions to various areas, with emphasis on his work in Mathematics, Applied Mathematics, Physics, Meteorology, Economics and Computing. In several cases, their contributions went far beyond solving problems proposed by others, opening up new areas of research and launching new problems. The objective of this work is to show von Neumann's contributions to Computing and, in particular, to digital computer architecture, computer programming and computer theory.
This work was prepared for the lecture given during the meeting The Work and Legacy of John von Neumann, organized by the Institute of Advanced Studies of the University of São Paulo and by the Brazilian Academy of Sciences, on November 14, 1995, at the Institute of Mathematics and Statistics of the University of São Paulo.
Summary: The text consists of a tutorial that provides the user, with basic notions of object-oriented programming in C ++, an explanatory introduction to programming based on the `` toolkit '' wxwindows. This package is a public domain tool, with cross-platform implementations (ftp.aiai.ed.ac.uk:pub/packages/wxwin).
The tutorial deals exclusively with the programming interface of wxwindows and how it can be used in the construction of human-computer interfaces. Several examples are provided.
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.
- An adaptation of the Edmonds pairing algorithm for running in parallel. 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 Aragon and Cid C. de Souza.
Summary: Echo algorithms form a class of simple, versatile and efficient distributed algorithms used to obtain global information in a decentralized way. Usually these algorithms are implemented using the message exchange paradigm, although their description follows the metaphor of replicating agents. In this article the execution environment will be presented, which offers the infrastructure for the execution of replicating agents, as well as the description of some initial experiences obtained in the programming of replicating agents, including the implementation of an instance of the echo algorithms.
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 report some experience with the technique.
Summary: The PRAM model has been the main model for the design and analysis of parallel algorithms for over 15 years. Its simplicity makes it a model that is not very true to reality, which motivated the appearance of extensions and other models, among which BSP (Valiant, 1990) and LogP (Culler et al., 1993). We present a brief description of these 3 models and show the different levels of abstraction in which they are located. The advantages and disadvantages of each one are presented, particularly with regard to the design and analysis of algorithms. The relevance of each one to the current panorama of parallel machines is discussed, concluding that the LogP model, despite being of a lower level, is the one most likely to spread in practical situations.
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.
Summary: This work presents a systolic architecture for the implementation of mathematical morphology operations (morphological filters). This architecture called SAMM (Systolic Architecture for Mathematical Morphology) implements the expansion and erosion operations with a planar structuring element. It has two levels of modularity, the first resulting from the implementation on the same hardware of numerical and binary operations, the other due to the systolic character of its processing. Taking into account factors such as performance, operations execution time and architecture, some processors were chosen that implement mathematical morphology filters for functional and complexity comparison with the developed architecture.
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 modeled 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 coloring method which can be used to color optimally the edge set of certain chordal graphs. This new heuristic yields an exact edge-coloring 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-colored with maximum degree
colors, ie, all these graphs are Class
🇧🇷 In addition, this method gives a simple
edge-coloring for any doubly chordal graph.
Summary: An experience of a paradigm shift in the teaching of undergraduate courses at Unicamp based on the W3 service on the Internet is reported. Instead of the traditional class, where the student plays a more passive role, a more exploratory character was given to the classes, which required a more active role on the part of the students. A preliminary assessment of the experience is presented here.
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 arithmetic interval, 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.
Summary: In this work, we describe some search problems in subspaces (range search) and solutions found in the literature, from which two paradigms of algorithms are identified: partition trees and linearization. These paradigms lead to some of the asymptotically optimal solutions and to generalized solutions to certain types of subspace search problems. The adopted approach allows a general and comprehensive view of the techniques involved, facing several different solutions as variations of the same basic concept. We also highlight possibilities of application and open questions, raising the possible impacts of the evolution of research regarding multidimensional searches.
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 |