Resumo: O problema da universalidade para Autômatos Temporizados (ATs) determinísticos é PSPACE-completo mas torna-se altamente indecidível quando não-determinismo irrestrito é permitido. Mais precisamente, o problema da universalidade para AT não-determinísticos é -difícil e ainda está em aberto se é -completo. É interessante notar que toda a hierarquia aritmética está contida neste salto de computabilidade entre determinismo e não-determinismo. Neste artigo, nós consideramos três tipos de restrição sintática para AT não-determinísticos, que podem contribuir para um melhor entendimento da dificuldade de se testar universalidade de TA. Para os dois primeiros tipos, que têm interesse independente, o problema da universalidade é -completo. Para o terceiro tipo, universalidade é -completo, o que é o mesmo que dizer que o problema complementar é completo para a classes dos problemas recursivamente enumeráveis. Nós também mostramos que todas as restrições definem subclasses próprias da classe de linguagens temporizadas definidas por AT não-determinísticos; e estabelecemos as relações entre todas as classes.

Abstract: Universality for deterministic Timed Automata (TA) is PSPACE-complete but becomes highly undecidable when unrestricted nondeterminism is allowed. More precisely, universality for nondeterministic TA is -hard and it is still open whether it is -complete. It is interesting to note that the entire arithmetical hierarchy is contained in this computability gap between determinism and nondeterminism. In this paper we consider three types of syntactical restrictions to nondeterministic TA, which may contribute to a better understanding of the universality problem for TA. For the first two types, which are of independent interest, the universality problem is shown to be -complete. For the third one, universality is -complete, which is the same as saying that the complementary problem is complete in the recursively enumerable class. We also show that all the restrictions define proper subclasses of the class of timed languages defined by nondeterministic TA; and establish the relationships between the classes.

Abstract: A checkpointing protocol that enforces rollback-dependency trackability (RDT) during the progress of a distributed computation must take forced checkpoints to break non-trackable dependencies. Breaking just non-visibly doubled dependencies instead of breaking all non-trackable dependencies leads to fewer forced checkpoints, but seemed to require the processes of a computation to maintain and propagate control information. In this paper, we prove that this hypothesis is false by presenting a protocol that breaks the minimal set of non-visibly doubled dependencies necessary to enforce RDT, called ``non-visibly doubled PMM-paths'', using only control information.

Abstract: Assume that a rectangle is given on the Euclidean plane together with a finite set of points that are interior to . A rectangular partition of is a partition of the surface of into smaller rectangles. The length of such a partition equals the sum of the lengths for the line segments that defined it. The partition is said to be feasible if no point of is interior to a partition rectangle. The Rectangular Partitioning Problem (RGP) seeks a feasible rectangular partition of with the least length. Computational evidence from the literature indicates that RGPs with non corectilinear points in , denoted RGNLPs, are the hardest to solve to proven optimality. In this paper, some structural properties of optimal feasible RGNLP partitions are presented. These properties allow for substantial reductions in problem input size to be carried out. Additionally, a stronger formulation of the problem is also made possible. Based on these ingredients, a hybrid Lagrangian Relaxation - Linear Programming Relaxation exact solution algorithm is proposed. Such an algorithm has proved capable of solving RGNLP instances more than twice as large as those found in the literature.

Keywords:: Rectangular partitions, optimality properties, Lagrangian relaxation, cutting planes.

Abstract: In this paper we present a new cryptographic primitive, the blinded-key signature, that allows the inclusion of private keys in autonomous mobile agents. This novel signature scheme can be applied to several well known digital signature schemes, such as RSA and ElGamal.

Abstract: This paper extends the RBAC model to deal with permission in a workflow management system. The extended model allows for dynamic constraints on instances of processes. We also extend the model so that delegations from an user to another user, and revocations of such delegations are dealt with. We also discuss the issues on delegations from a user to a group of users.

Abstract: This paper presents a pair of role-based access control models for workflow systems, collectively known as the W-RBAC model. The models described here contains both static and dynamic (history based) constraints, which is integrated with a workflow system. The W0-RBAC model describes our concept of dynamic constrains, and the integration of the access control system with the workflow. The W1-RBAC model extends the W0-RBAC model by allowing for a controlled overriding of constraints, which we argue are necessary in workflow applications in order to cope with exceptional situations. Finally we discuss a Prolog implementation of the access control models.

Abstract: The clique graph of a graph is the intersection graph of the (maximal) cliques of . The iterated clique graphs are defined by and , where and is the clique operator. A cograph is a graph with no induced subgraph isomorphic to . In this article we describe the -behaviour of cographs and give some partial results for the larger class of serial (i.e. complement-disconnected) graphs.

Abstract: This paper introduces the computation of delay and backlog bounds for a Generalized Processor Sharing (GPS) server under self-similar traffic. The traffic is supposed to be regulated by the Fractal Leaky Bucket policing mechanism, which is an appropriate regulator for self-similar traffic. Results are extended to a network of GPS servers with arbitrary topology, and the stability of those networks is analysed.

Resumo: As áreas de pesquisa em Sistemas de Informação Geográfica (SIG) tem sido principalmente relacionadas ao desenvolvimento de modelos para estruturação de dados. O design da interface é um tópico que ainda tem recebido pouco enfoque, apesar de ser determinante dos aspectos de usabilidade do sistema. É desejável que a interface permita ao usuário atingir seus objetivos facilmente, mas a forte carga conceitual desses sistemas tem impedido sua utilização por um grupo mais diversificado de usuários. Neste trabalho, temos como objetivo realizar uma análise semiótica dos sinais de interface do ArcView GIS 3D Analyst. Os resultados são ilustrados e qualificados de forma a informar e orientar o (re)design dos elementos de interface para esses sistemas.

Abstract: The research areas in Geographical Information Systems (GIS) have been mainly related to the development of models to structure data. The interface design is a topic that still has received little attention despite the fact that it is fundamental for achieving system usability. The interface should allow the user to achieve his goals easily, but the strong conceptual overload of these systems have prevented their use by a more diversified class of users. In this work, we have carried out a semiotic analysis of the interface signals of ArcView GIS 3D Analyst. The results are illustrated and classified to inform and orient the (re)design of interface elements of these systems.

Abstract: Tutte's 3-flow conjecture is restated as the problem of finding an orientation of the edges of a 4-edge-connected, 5-regular graph , for which the out-flow at each vertex is or . The induced equipartition of the vertices of is called mod 3-orientable. We give necessary and sufficient conditions for the existence of mod 3-orientable equipartitions in general 5-regular graphs, in terms of (i) a perfect matching of a bipartite graph derived from the equipartition and (ii) the size of cuts in . Also, we give a polynomial time algorithm for testing whether an equipartition is mod 3-orientable.

Resumo: Este trabalho é um survey sobre o estado da arte em segurança de sistemas de agentes móveis. Inicialmente, com base em um modelo simplificado de sistemas de agente móveis contendo apenas agentes e servidores, mostramos os problemas de segurança inerentes a estes sistemas e os requisitos de segurança desejáveis. Apresentamos também os fundamentos de Criptografia e de segurança de Java necessários para a compreensão das soluções adotadas pelos sistemas abordados. Dando ênfase aos aspectos de segurança, descrevemos alguns sistemas comerciais e não-comerciais de agentes móveis, apontando deficiências e recomendando algumas soluções. Para finalizar, apresentamos um quadro sinótico que resume as soluções propostas por cada um dos sistemas analisados.

Abstract: This report is a survey of the state of the art in security of mobile agent systems. Initially, based on a simplified model of mobile agent systems comprising only agents and servers, we show security problems inherent to these systems and the desirable security requirements. We also give the fundamentals of crytography and Java-based security needed to understand the solutions adopted by the systems surveyed here. With emphasis on security issues, we describe some commercial and non-commercial mobile agent systems, pointing out deficiencies and recommending some solutions. Finally, we give a table summarizing the solutions proposed by each of the systems we analyzed.

Abstract: Given two genomes represented as circularly ordered sequences of genes, we show a polynomial time algorithm for the minimum weight series of fusion, fissions, and transpositions (with transpositions weighing twice as much as fusions and fissions) that transforms one genome into the other. The algorithm is based on classical results of permutation group theory and is the first polynomial result for a genome rearrangement problem involving transpositions. It has been observed in real biological instances that transpositions occur with about half the frequency of reversals. Although we are not using reversals in this study, this observation motivated the double weight assigned to transpositions.

Resumo: Autômatos Temporizados (ATs) são uma generalização de -autômatos que tem sido bastante estudada tanto do ponto de vista prático de verificação de sistemas de tempo real, quanto da perspectiva teórica de linguagens formais. Universalidade para ATs determinísticos é PSPACE-completo mas, surpreendentemente, foi demonstrado -difícil para ATs não-determinísticos. A posição exata deste problema na hierarquia analítica está em aberto. Neste artigo nós consideramos a classe mais restrita de ATs quase determinísticos. Na nossa principal contribuição, mostramos que universalidade para ATs quase determinísticos é -completo e também mostramos que, ao contrário de -autômatos, ATs quase determinísticos definem uma subclasse própria de ATs não-determinísticos. Estes resultados ajudam a clarificar o papel do não-determinismo em ATs e revelam alguns aspectos surpreendentes do problema de universalidade para ATs não-determinísticos.

Abstract: Timed Automata (TAs) are a generalization of -automata that has been largely studied both from the practical point of view of verification of real-time systems, and from the theoretical perspective of formal languages. Universality for deterministic TAs is PSPACE-complete but, surprisingly, it was shown to be -hard for nondeterministic TAs. The exact position of this problem in the analytical hierarchy is still open. In this paper we consider the more restricted class of almost deterministic TAs. In our main contribution we show that the restriction to almost deterministic TAs characterizes this decision problem as -complete and we also show that, in contrast to -automata, almost deterministic TAs define a proper subclass of nondeterministic TAs. These results give new insights regarding the role of nondeterminism in TAs and reveal some surprising aspects of the universality problem for nondeterministic TAs.

Abstract: We describe a program that builds contig scaffolds from contig assemblies, to be used in a whole-genome sequencing project. Our program builds scaffolds based on forward/reverse pair information (both from small clones, such as plasmids, and from large clones, such as cosmids). The program assumes that a DNA assembly, preferably with large repeats masked, is available. A scaffold is a path in a weighted graph, and the main novelty of our approach is a careful weighting scheme for arcs in this graph, such that heavier paths represent more reliable scaffolds. This weighting scheme takes into account the presence of repeats, possible clone duplication, existence of different clone libraries, and hybrid (small clones mixed with large clones) links between contigs. The program provides two different algorithms for scaffold building: one that uses a simple greedy strategy, and one that produces scaffolds that correspond to paths of maximum weight. If is the number of contigs and is the number of F/R pairs, the complexities are (greedy) and (maximum-weight path). This program has been successfully used in several bacterial genome projects.

This report supersedes IC-TR-00-20.

Abstract: We describe here an efficient algorithm for reassembling one or more unknown objects that have been broken or torn into a large number of irregular fragments. The algorithm works by comparing the curvature-encoded fragment outlines, using a modified dynamic programming sequence-matching algorithm. By comparing the outlines at progressively increasing scales of resolution, we manage to reduce the cost of the search from (where is the mean number of samples per fragment) to about ; which, in principle, allows the method to be used for problems of practical size ( to fragments, to samples). The performance of the algorithm is illustrated with an artificial but realistic example.

A shorter version of this report was presented at the British Machine Vision Confrence (BMVC) in Bristol, UK (September 2000).

Abstract: Just-In-Time (JIT) compilation is a well-known technique used to improve the execution time in the Java Virtual Machine (JVM). However, the amount of time used by the JIT internals degrades, in many cases, the application execution time. Some techniques have been used to decrease the JIT overhead, while still keeping its effectiveness. However, the trade-off between the JIT running time and its object code execution time will always exist. From our observation, an end-user Java Virtual Machine deals with the same code most of its time. Users always launch the same applications which are typically composed of the same set of classes. On the other hand, in big companies, dozens, or even hundreds of employees share the same application or application suite. Usually, they are connected under the same fast and secure Intranet. In this scenario, the per-user JIT effort is repetitive and largely greater than the strictly required. The goal of our work is to detach linking activities from the JVM to a shared server, on a distributed fashion. By doing that, the client JVM turns to be a very simple piece of software that runs Java code natively, not requiring a JIT or interpreter. All complex linking activities -- like link-time error checking, class file verification and JIT compilation -- are done by the server which caches its responses. This document is a description of an alternate implementation of the Java Virtual Machine that inovates. It covers specially: techniques for detecting and caching repetitive link-time contexts; an alternate, off-line, bytecode verification procedure; the design and implementation of a Java specific intermediate representation; and the detailed description of many JVM implementation issues.

Resumo: Métodos para observar usuários de software em seu local de trabalho tendem a ser cada vez mais necessários, à medida que cresce o número de usuários de computadores e a inerente complexidade dos sistemas aumenta. Processos de avaliação contínua durante o ciclo de vida do design parecem ser condição necessária a um bom resultado de design. Métodos de inspeção de usabilidade por especialistas em interfaces, embora efetivos no que se propõem, não captam elementos do contexto de trabalho do usuário. Neste artigo argumentamos que abordagens etnográficas representam uma ferramenta efetiva para o designer avaliar antecipadamente o uso contextual do sistema sendo proposto, durante o ciclo de design. Ilustramos, em um estudo de caso, como a utilização de práticas etnográficas pode servir na avaliação formativa e informar o redesign do sistema.

Palavras-Chave:: Design, Etnografia, Interface, Avaliação formativa, Observação Participativa.

Abstract: Methods for observing software users in their work context tend to be more and more necessary as the number of computers users grows and the inherent complexity of the systems increases. Continuous evaluation process during the design life cycle seems to be a necessary condition for a good design. Usability methods of inspection applied by interface professionals, although effective in what they intend, do not capture elements of the user's work context. In this paper we argue that ethnographic approaches represent an effective tool for designers to evaluate in advance the contextual use of the system being proposed. We illustrate, by presenting a case study, how ethnographic practices can be useful to the formative evaluation and the system redesign.

Keywords:: Design, Ethnography, Interface, Evaluation, Participant observation.

Abstract: Let and be two linear function spaces defined on some domain . Let be a vector semi-norm for the space . We consider here the question of how well approximates in the sense of the metric . Global error measures are insufficiently informative when the space is not spatially homogeneous. We introduce here the concept of approximation error map, a mathematical description of how the approximation errors are distributed over the domain -- not for a single function , but for all such functions at once. We illustrate this concept by computing the error maps of several harmonic spline spaces on the circle and on the sphere.