Abstract: A three-dimensional complex is a partition of a three-dimensional manifold into simple cells, faces, edges and vertices. We consider here the problem of automatically producing a ``nice'' geometric representation (in , for ) of an arbitrary 3D complex, given only its combinatorial description. The geometric realization is chosen by optimizing certain aesthetic criteria, measured by certain ``energy functions.''.

Resumo: Alur et al. apresentaram um algoritmo para o problema de verificação de processos de tempo real probabilísticos contra especificações dadas por autômatos temporais; e levantaram a questão da verificação de especificações dadas por autômatos não determinísticos. Nesse artigo, nós damos uma resposta parcial para a questão, extendendo o método de tal forma que processos, com uma restrição aceitável, podem ser testados contra qualquer autômato temporal. Entre esses processos, por exemplo, incluem-se modelos de circuitos digitais onde a propriedade principal é que as distribuições dos atrasos possuem limite inferior diferente de zero.

Abstract: Alur et al. presented an algorithm for the problem of verifying deterministic timed automata specifications of probabilistic real-time systems given as generalized semi-Markov processes; and posed the question of the verification of nondeterministic specifications. We give a partial answer to the question, extending their method so that processes, with a fairly acceptable restriction, can be tested against any timed automaton. These include, for instance, real-time models of digital circuits where the key property is that the delay distributions have non-zero lower bounds.

Resumo: Sistemas de Informação Geográfica têm experimentado avanços importantes motivados pelas novas tecnologias de informação, que também têm ampliado seu potencial de uso para além dos especialistas no domínio. Nesse sentido, os SIGs deveriam considerar a familiaridade do usuário com a Cartografia e sua forma tradicional de representação dos fenômenos naturais ou construídos pelo homem. Entendendo a construção e interpretação de mapas como atividades de comunicação, este trabalho visa avaliar o poder de expressão de SIGs no que se refere à representação de elementos cartográficos, a partir da abordagem Semiótica. Resultados obtidos da comparação dos sistemas semióticos da Cartografia e dos SIGs constatam uma grade diferença no potencial de comunicação em cada um dos domínios.

Abstract: Several improvements are noticed on Geographic Information Systems, motivated by the general trends in information technologies, expanding their potential uses to domain experts. In that sense, GIS should consider the user's familiarity with Cartography and its traditional way of representing natural phenomena. Understanding the construction and interpretation of maps as communication activities, this paper evaluates the expression power of GIS relatively to their cartographic elements, based on a Semiotic approach. Results obtained from the comparison between Cartographic and GIS semiotic systems show a great difference in the potential for communication for each one of the domains.

Abstract: The Cube Packing Problem (CPP) is defined as follows. Find a packing of a given list of (small) cubes into a minimum number of (larger) identical cubes. We show first that the approach introduced by Coppersmith and Raghavan for general online algorithms for packing problems leads to an online algorithm for CPP with asymptotic performance bound 3.954. Then we describe two other offline approximation algorithms for CPP: one with asymptotic performance bound 3.466 and the other with 2.669. A parametric version of this problem is defined and results on online and offline algorithms are presented. We did not find in the literature offline algorithms with asymptotic performance bounds as good as 2.669.

Abstract: Reassembling unknown broken objects from a large collection of fragments is a common problem in archaeology and other fields. Computer tools have recently been developed, by the authors and by others, which try to help by identifying pairs of fragments with matching outline shapes. These tools have been succesfully tested on small collections of fragments; here we address the question of whether they can be expected to work also for practical instances of the problem ( to fragments). To that end, we describe here a method to measure the average amount of information contained in the shape of a fracture line of given length. This parameter tells us how many false matches we can expect to find for that fracture among a given set of fragments. In particular, the numbers we obtained for ceramic fragments indicate that fragment outline comparison should give useful results even for large instances.

An optimal algorithm to construct all Voronoi diagrams for nearest neighbor search in .

Abstract: In this paper, we generalize to the oriented projective plane an algorithm for constructing all order Voronoi diagrams in the Euclidean plane. We also show that, for fixed and for a finite set of sites, an order Voronoi diagram in has an exact number of regions. Furthermore, we show that the order Voronoi diagram of a set of sites in is antipodal to its order Voronoi diagram, .

Abstract: A recovery line is the most recent consistent global checkpoint from which a distributed computation can be restarted after a failure. This paper presents a new quasi-synchronous checkpointing protocol where processes propagate their local knowledge about the recovery line, named PRL.

Protocols that enforce rollback-dependency trackability (RDT) are domino-effect free and are usually based on vector clocks. Protocols that avoid the domino effect without enforcing RDT are usually index-based. The protocol proposed by Baldoni, Quaglia, and Ciciani (BQC) was the first non-RDT domino-effect free protocol to use a vector clock. In BQC, each process keeps and propagates a matrix of of integers, where is the number of processes in the computation. PRL is also vector-clock based, domino-effect free, and non-RDT, but lowers the complexity of the required control information from to . We present theoretical and simulation results giving evidence that PRL reduces the number of induced checkpoints in comparison with BQC.

Abstract: Distributed computing often gives rise to complex concurrent and interacting activities. In many cases, several concurrent activities may be working together, i.e., cooperating, to solve a given problem; in other cases the activities may be independent but sharing common system resources for which they should compete. In practice, different kinds of concurrency might coexist in a complex application which thus will require a general supporting mechanism for controlling and coordinating complex concurrent activities. Many difficulties and limitations occur when the object and action model is used to support cooperating activities. This paper discuss some of these difficulties and limitations and then presents an alternative model for constructing fault-tolerant distributed systems based on the concept of Coordinated Atomic (CA) actions which provides uniform support for both cooperative and competitive concurrency.

Abstract: We present a fast, synchronous, cryptographic protocol by means of which Alice can send Bob a stream B, with assurance of non-repudiation of reception of B or any prefix of it by Bob. Bob, on the other hand, can prove to any third party the origin of B or any prefix of it. While the protocol's synchronous nature may prevent its use in some broadcast-type applications, its speed and mutual non-repudiation capabilities make it well suited for several e-commerce applications.

Resumo: Neste texto, problemas de grande porte para escalonamento de mão-de-obra são abordados e diversas estratégias de solução são descritas. Tais problemas são reconhecidos como problemas difíceis em Otimização Combinatória e foram resolvidos até a otimalidade. Soluções ótimas comprovadas para instâncias reais e de grande porte são obtidas utilizando-se uma abordagem híbrida que integra técnicas de Programação Matemática e Programação por Restrições. Um ambiente de programação declarativa foi utilizado para se desenvolverem os modelos baseados em restrições. A natureza declarativa deste ambiente mostrou-se valiosa durante a modelagem de restrições complexas do problema e, particularmente, ao se explorar, de forma eficiente, o enorme espaço de soluções viáveis. O código foi testado em instâncias reais do problema oriundas da operação diária de duas linhas de ônibus de uma empresa brasileira de transporte urbano que serve uma grande região metropilitana. Algumas dessas instâncias contêm um número de entradas superior a e puderam ser resolvidas até a otimalidade em um microcomputador pessoal típico, em um tempo de computação aceitável.

Abstract: We consider several strategies for computing optimal solutions to large scale crew scheduling problems, which are known to be notoriously difficult combinatorial optimization problems. Provably optimal solutions for very large real instances of such problems were computed using a hybrid approach that integrates mathematical and constraint programming techniques. A declarative programming environment was used to develop the constraint based models. The declarative nature of such an environment proved instrumental when modeling complex problem restrictions and, particularly, in efficiently searching the very large space of feasible solutions. The code was tested on real problem instances, stemming from the operation of two bus lines of a typical Brazilian transit company that serves a major urban area. Some of those instances contained an excess of entries and could be solved to optimality in an acceptable running time when executing on a typical desktop PC.

Resumo: O objetivo desse trabalho é a aplicação de técnicas de especificação formal para modelar sistemas distribuídos realistas. Os modelos formais são baseados em autômatos híbridos. O sistema alvo desse trabalho são segmentos de via de uma malha metroviária. A análise e a verificação do modelo considerado, bem como a síntese de certos parâmetros importantes do modelo, são auxiliadas por ferramentas semi-automáticas. Dessa forma, obteve-se de maneira automática a validação do comportamento do sistema descrito, bem como a síntese de parâmetros críticos para a operação da malha.

Abstract: The aim of this work is to apply formal specification techniques to model real-time distributed systems. The formal models are based on hybrid automata. The target systems of this work are segments of subway network. Semi-automatic tools aid in the analysis and verification of the model. The model is also used to synthesize some important parameters of the system under consideration.

Resumo: Tolerância a falhas é um importante requisito no desenvolvimento de sistemas computacionais modernos. Entretanto, a contrução de sistemas tolerantes a falhas é uma atividade complexa especializada durante todo o ciclo de desenvolvimento do sistema. Além disso, idealmente a provisão de tolerância a falhas deveria ser feita de forma estruturada e não-intrusiva. Neste contexto, propomos um conjunto de padrões (decisões de projetos) que auxiliam o desenvolvimento de sistemas orientados a objetos tolerantes a falhas. Estes padrões são baseados no modelo de componente tolerante a falhas ideal. O conceito de reflexão computacional é utilizado objetivando a obtenção de uma separação explícita entre o comportamento normal e anormal dos componentes. As atividades normais, que implementam os requisitos funcionais da aplicação, são implementados no nível base, enquanto as atividade anormais, que implementam os mecanismos de tolerância a falhas, são implementados no meta-nível, através de meta-objetos. Os padrões representam decisões de projeto que devem ser tomadas no desenvolvimento de sistemas orientados a objetos tolerantes a falhas objetivando a obtenção de um projeto estruturado, onde a introdução dos mecanismos de tolerância a falhas é feita de forma controlada e consistente.

Abstract: Fault tolerance represents a major challenge to design of moderns computing systems. However, the construction of fault-tolerant systems is not a simple task. It requires the use of appropriate techniques during the whole software development cycle. Besides, ideally fault-tolerance mechanisms should be incorporated to the original system in a structured and non-intrusive manner. In this context, we propose a set of patterns (design decisions) that make easier the task of building fault-tolerant object-oriented systems. This patterns are based on idealised fault-tolerant component model. The computacional reflection concept is used aiming a clear separation of the normal activity from the abnormal activity of a software component. The normal activities, that implement the functional requirements, are implemented by base-level objects, while the abnormal activities, that implement the fault tolerance mechanisms, are implemented by meta-level objects. The patterns are design choices that should be taken during the software development cycle aiming a structured design, where the fault-tolerance mechanisms is incorporated to the original system in a structured and controlled manner.

Resumo: Este trabalho explora mobilidade no contexto de gerenciamento de serviços distribuídos abertos. Um conjunto de agentes é definido para explorar o ambiente gerenciado utilizando uma abordagem de detalhamento sucessivo de potenciais problemas. A implementação considera sistemas distribuídos baseados em objetos segundo OMG/CORBA. Uma extensão do trabalho é proposta para o ajuste do sistema gerenciado, utilizando o balanceamento dos recursos computacionais com o auxílio de um serviço de disponibilidade.

Abstract: This paper explores the mobility paradigm in the context of management of open distributed services. A pool of agents is defined in order to explore the managed environment based on the zooming of potential problems. The implementation considers an open distributed environment based on OMG/CORBA objects. An extension is presented for adjusting the managed system based on the balancing of the computational resources with the help of an availability service.

The vertex deletion number and splitting number of a triangulation of .

Abstract: The vertex deletion number of a graph is the minimum number of vertices that must be deleted from to produce a planar graph. The splitting number of is the smallest number of vertex splitting operations that must be applied to to make it planar. Here we determine these topological invariants for the graph family , a regular triangulation of the torus obtained by adding parallel diagonal edges to the faces of the rectangular toroidal grid . Specifically, we prove that the obvious upper bound is also a lower bound.

The vertex deletion number of .

Abstract: The vertex deletion number of a graph is the smallest integer such that there is a planar induced subgraph of obtained by the removal of vertices from . In this work we study the vertex deletion number of , the rectangular grid with toroidal topology. We prove the extact result , where is the number of true conditions among the following: (i) and (ii) .

Resumo: Este documento descreve a implementação e experiências iniciais com um modelo de programação por restrições para o escalonamento mensal de mais de 1500 profissionais de enfermagem no Hospital Universitário da Unicamp. A implementação inclui uma interface amigável para o usuário.

Este relatório é baseado no projeto final de graduação de Denise G. Batista.

Abstract: This document describes the implementation and early experience with a constraint programming model for the monthly scheduling of more than 1500 nursing personel at Unicamp's University Hospital. The implementation includes a user-friendly interface.

This report is based on the final graduation project of Denise G. Batista.

Abstract: We propose a method for compressing programs running on embedded DSPs. Program expression trees are decomposed into opcode and operand sequences called patterns. We show that DSP program patterns have exponential frequency distributions. Based on that, we encode patterns using a mix of variable-length and fixed-length codewords. A decompression engine is proposed, which converts patterns into uncompressed instruction sequences. The experimental results reveal an average compression ratio of 67% for typical DSP programs running on the TMS320C25 processor. This ratio includes an estimate of the size of the decompression engine.

Abstract: This paper presents a method for minimizing test suites for embedded, nondeterministic Finite State Machines. The method preserves the fault coverage of the original test suite, and can be used in conjunction with any technique for generating test suites. The minimization is achieved by detecting and deleting redundant test cases in the test suite.

Resumo: Sistemas distribuídos tolerantes a falhas baseiam-se parcialmente na existência de mecanismos de checkpointing e recuperação por retrocesso de estado. Um outro mecanismo importante para esses sistemas é o que permite a monitorização do seu estado e a pronta reação a mudanças que afetam o seu funcionamento previsto. Apesar desses dois mecanismos estarem fortemente associados, a grande maioria dos sistemas tolerantes a falhas contruídos até hoje privilegia a implementação de mecanismos de checkpointing, em detrimento de mecanismos para monitorização. Visões progressivas são seqüências de checkpoints globais consistentes que poderiam ter ocorrido nesta ordem durante a execução das computações. Foram denominadas progressivas porque o algoritmo para a sua determinação minimiza o retrocesso necessário durante a fase de recuperação do sistema, em caso de falha parcial de hardware. Neste artigo, comentamos a utilidade de visões progressivas para o desenvolvimento de protocolos mais eficientes para checkpointing e para a integração de mecanismos de checkpointing, recuperação de estado e monitorização.

Abstract: Fault-tolerant distributed systems are partially based on the implementation of checkpointing and rollback-recovery mechanisms. Another important mechanism associated to tolerance of faults is the one that allows a system to monitor its state and to react to exceptional behaviour. Checkpointing and rollback-recovery are already part of most of the fault-tolerant systems implemented to date. This situation does not apply to monitoring mechanisms, especially to systems that integrate monitoring, checkpointing and rollback-recovery. Progressive views are formed by a sequence of consistent global checkpoints that may have occurred in this order during the execution of the system. Progressive views are called progressive because they have been designed to minimize the rollback of the system when a partial failure of hardware occurs. This article dicusses the application of progressive views towards the deployment of more efficient checkpointing mechanisms and its application to the integration of checkpointing, rollback-recovery and monitoring for fault-tolerant distributed systems.

Resumo: Algoritmos para a determinação de estados globais consistentes em um sistema distribuído têm grande importância para tarefas que envolvam monitorização e reconfiguração, como detecção de deadlocks, detecção de perda de token, depuração, coleta de lixo, entre outros. Este documento aborda aspectos teóricos da determinação de estados globais consistentes e descreve um ambiente de programação projetado e implementado para permitir a experimentação com algoritmos para obtenção de estados globais consistentes.

Abstract: Algorithms for the determination of consistent global states in a distributed system have major importantce in tasks that require monitoring and reconfiguration, such as the deadlock detection, token loss detection, debugging, and garbage colletion, among others. This document addressed theoretical aspects of consistent global state determination, and describes a programming environment designed and implemented to allow experimentation on algorithms for obtaining consistent global states.

Abstract: Running code downloaded from the network raises several security issues. Unlike the Java programming language, most existing reflective architectures have failed to address these issues. There is a clear need for mechanisms to impose some discipline on the interactions between objects and meta-objects, so as to retain or improve the security mechanisms offered by programming languages.

While the ability to dynamically associate objects with meta-objects is essential for developing flexible and adaptable reflective applications, reliability depends on mechanisms to regulate reconfigurations.

In the design of Guaraná, a language-independent meta-object protocol, we have attempted to address these issues. This papers describes and justifies some of the decisions we have made in order to allow developers of reflective applications to balance flexibility and security.

Abstract: We present a general algorithm to align two protein sequences that uses the concept of don't care regions. It is based on the classical Needleman-Wunsch dynamic programming method using affine penalty functions. We tested the algorithm on two problems, comparing it against the standard dynamic programming algorithm. Results were not consistently or significantly better, suggesting that refinements are needed.

Abstract: This work describes a meta-object library and a reflective object-oriented framework for cryptography-based security, which focuses on three points: the easy reuse of cryptography-aware code, the easy composition of cryptographic services and the transparent addition of cryptography-based security to third-party code, from the application programmer's point of view. Such a framework is applicable to both third-party commercial-off- the-shelf applications and legacy systems, and is based on a reflective variation of a pattern language for cryptographic software we had proposed. We are using Guarana, a reflective variation for the Java programming language which encourages composition of meta-objetcs, to implement our framework.

Abstract: In this work we show that compliance to Tropyc, a pattern language for cryptographic software, is a good criteria for Cryptographic Application Programming Interfaces (CAPIs) evaluation. Tropyc documents the constraints over cryptographic services combination by limiting the number of valid patterns. Also, we use this criteria to evaluate a group of six CAPIs: IBM's CCA, RSA's Cryptoki, Microsoft's CryptoAPI, Sun's JCA/JCE, X/Open's GCS-API and Intel's CSSM-API. We show that these CAPIs lack the ability of cryptographic service composition, an important feature of modern applications, such as electronic commerce systems.

Abstract: Object-oriented applications with non-functional cryptography-based security requirements can benefit from a flexible design in which cryptographic objects and application functional objects are weakly coupled. In this work, the combination of computational reflection and cryptographic design patterns is proposed in order to improve reuse of both design and code (while decreasing coupling and increasing flexibility) of cryptographic components. The usefulness of this approach is in the transparent addition of cryptography-based security to third-party commercial-off-the-shelf components. A reflective extension for the cryptographic design pattern is proposed. This extension is implemented in Guaraná, a meta-object protocol for Java.

Abstract: This work describes Tropyc, a pattern language for cryptographic software based on a generic object-oriented cryptographic architecture. Nine patterns are described: Information Secrecy, Sender Authentication, Message Integrity, Signature, Signature with Appendix, Secrecy with Integrity, Secrecy with Sender Authentication, Secrecy with Signature, and Secrecy with Signature with Appendix. They are classified according to four fundamental objectives of cryptography (confidentiality, integrity, authentication and non-repudiation) and compose a closed set of patterns for this domain. These patterns have the same dynamic behavior and structure. We abstracted these aspects into a Generic Object-Oriented Cryptographic Architecture ( GOOCA).

Abstract: Synchronous user interface is a medium where all objects being shared on it can be viewed indifferently from the geographical location and its users can interact with each other in real-time. Designing such an interface for users working collaboratively requires to deal with a number of issues. Herein, our concerns lies on the design of control component of Human-Computer Interaction (HCI) and corresponding User Interface (UI) software that implements it. We make use of our approach to interactive system development based on the MPX - Mapping from PAN (Protagonist Action Notation) into Xchart (eXtended Statechart) - and illustrate it by presenting the case study of a collaborative application.

Abstract: In this paper, we describe an envelope process for the fractal Brownian motion (fBm) process. We investigate the time scale of interest of queuing systems fed by a fBm process. We also introduce the Fractal Leaky Bucket, a novel policing mechanism which is able to accurately monitor self-similar sources. Moreover, we show expressions for computing the equivalent bandwidth of an aggregate of heterogeneous self-similar sources.