Technical Reports Published in 2001

  • IC-01-20 pdf bib
    Classes of timed automata and the undecidability of universality.
    Arnaldo V. Moura and Guilherme A. Pinto.
    December 2001. In English, 16 pages.

    Summary: The problem of universality for deterministic Timed Automata (ATs) is PSPACE-complete but it becomes highly undecidable when unrestricted non-determinism is allowed. More precisely, the problem of universality for non-deterministic TA is $ \ Pi_1 ^ 1 $-difficult and is still open if it is $ \ Pi_1 ^ 1 $-complete. It is interesting to note that the entire arithmetic hierarchy is contained in this leap in computability between determinism and non-determinism. In this article, we consider three types of syntactic constraint for non-deterministic TA, which can contribute to a better understanding of the difficulty of testing the universality of AT. For the first two types, which have an independent interest, the problem of universality is $ \ Pi_1 ^ 1 $-complete. For the third type, universality is $ \ Pi_1 ^ 0 $-complete, which is to say that the complementary problem is complete for the classes of recursively enumerable problems. We also show that all constraints define subclasses of the class of timed languages ​​defined by non-deterministic ATs; and we establish the relationships between all 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 $ \ Pi_1 ^ 1 $-hard and it is still open whether it is $ \ Pi_1 ^ 1 $-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 $ \ Pi_1 ^ 1 $-complete. For the third one, universality is $ \ Pi_1 ^ 0 $-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.

  • IC-01-17 pdf bib
    A linear approach to enforce the minimal characterization of the rollback-dependency trackability property.
    Islene Calciolari Garcia and Luiz Eduardo Buzato.
    December 2001. In English, 20 pages.

    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 $ O (n ^ 2) $ 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 $ O (n) $ control information.

  • IC-01-16 pdf bib
    Optimal rectangular partitions.
    Felipe C. Calheiros, Abílio Lucena, and Cid C. de Souza.
    December 2001. In English, 29 pages.

    Abstract: Assume that a rectangle R $ is given on the Euclidean plane together with a finite set $ P $ That the interior of points are to R $. A rectangular partition of R $ is a partition of the surface of R $ 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 $ P $ is interior to a partition rectangle. The Rectangular Partitioning Problem (RGP) seeks a feasible rectangular partition of R $ with at least length. Computational evidence from the literature indicates that RGPs with non corectilinear points in $ P $, 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 provider 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.

  • IC-01-15 pdf bib
    Blinded-key signatures: Securing private keys embedded in mobile agents.
    Lucas de Carvalho Ferreira and Ricardo Dahab.
    December 2001. In English, 15 pages.

    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.

  • IC-01-14 pdf bib
    Security management in the presence of delegation and revocation in workflow systems.
    Jacques Wainer, Akhil Kumar, and Paulo Barthelmess.
    October 2001. In English, 18 pages.

    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.

  • IC-01-13 pdf bib
    W-RBAC - a workflow security model incorporating controlled overriding of constraints.
    Jacques Wainer, Paulo Barthelmess, and Akhil Kumar.
    October 2001. In English, 27 pages.

    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.

  • IC-01-12 pdf bib
    The click operator on cographs and serial graphs.
    F. Larrión, C. P. de Mello, V. Neumann-Lara, A. Morgana, and M. A. Pizaña.
    October 2001. In English, 12 pages.

    Abstract: The click graph of the graph $ G $ is the intersection graph $ K (G) $ of the (maximal) clicks of $ G $. The iterated click graphs $ K ^ {n} (G) $ are defined by $ K ^ {0} (G) = G $ and $ K ^ {i} (G) = K (K ^ {i-1} (G)) $, Onde $ i> 0 $ and $ K $ is the click operator. THE graph is a graph with no induced subgraph isomorphic to $ P_ {4} $🇧🇷 In this article we describe the $ K $-behavior of cographs and give some partial results for the larger class of serial (ie complement-disconnected) graphs.

  • IC-01-11 pdf bib
    On the performance of generalized processor sharing servers under long-range dependent traffic.
    Flavio M. Pereira, Nelson L. S. Fonseca, and Dalton S. Arantes.
    October 2001. In English, 28 pages.

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

  • IC-01-10 pdf bib
    Evaluating signals at interfaces for geographic information systems.
    Juliano Schimiguel and M. Cecília C. Baranauskas.
    October 2001. In Portuguese, 15 pages.

    Summary: The research areas in Geographic Information Systems (GIS) have been mainly related to the development of models for structuring data. The interface design is a topic that has received little focus, despite being determinant of the usability aspects of the system. It is desirable that the interface allows the user to easily achieve their goals, but the strong conceptual load of these systems has prevented their use by a more diverse group of users. In this work, we aim to perform a semiotic analysis of the ArcView GIS 3D Analyst interface signals. The results are illustrated and qualified in order to inform and guide the (re) design of the interface elements for these systems.

    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.

  • IC-01-09 pdf bib
    Tutte's 3-flow conjecture and matchings in bipartite graphs.
    Cândida Nunes da Silva and Ricardo Dahab.
    August 2001. In English, 11 pages.

    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 $ G $, for which the out-flow at each vertex is $ + $ 3 or $ -3 $. The induced equipartition of the vertices of $ G $ 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 $ G $. Also, we give a polynomial time algorithm for testing whether an equipartition is mod 3-orientable.

  • IC-01-08 pdf bib
    Survey on security of mobile agent systems.
    Nelson Uto and Ricardo Dahab.
    July 2001. In English, 35 pages.

    Summary: This work is a survey on the state of the art in security of mobile agent systems. Initially, based on a simplified model of mobile agent systems containing only agents and servers, we show the security problems inherent in these systems and the desirable security requirements. We also present the fundamentals of Cryptography and Java security necessary to understand the solutions adopted by the systems covered. With an emphasis on security aspects, we describe some commercial and non-commercial systems of mobile agents, pointing out deficiencies and recommending some solutions. Finally, we present a summary table that summarizes the solutions proposed by each of the systems analyzed.

    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.

  • IC-01-07 pdf bib
    Genome rearrangements distance by fusion, fission, and transposition is easy.
    Joao Meidanis and Zanoni Dias.
    July 2001. In English, 8 pages.

    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.

  • IC-01-06 pdf bib
    On almost deterministic timed automata.
    Arnaldo V. Moura and Guilherme A. Pinto.
    May 2001. In English, 16 pages.

    Summary: Timed Automata (ATs) are a generalization of $ \ omega $-automats that have been extensively studied both from the practical point of view of verifying real-time systems and from the theoretical perspective of formal languages. Universality for deterministic TAs is PSPACE-complete but, surprisingly, it has been demonstrated $ \ Pi_1 ^ 1 $-difficult for non-deterministic TAs. The exact position of this problem in the analytical hierarchy is open. In this article we consider the most restricted class of ATs to be almost deterministic. In our main contribution, we show that universality for almost deterministic TAs is $ \ Pi_1 ^ 1 $-complete and we also show that, unlike $ \ omega $-automats, quasi-deterministic TAs define a subclass of non-deterministic TAs. These results help to clarify the role of non-determinism in TAs and reveal some surprising aspects of the universality problem for non-deterministic TAs.

    Abstract: Timed Automata (TAs) are a generalization of $ \ omega $-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 $ \ Pi_1 ^ 1 $-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 $ \ Pi_1 ^ 1 $-complete and we also show that, in contrast to $ \ omega $-automata, almost deterministic TAs defines 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.

  • IC-01-05 pdf bib
    A program for building contig scaffolds in double-barreled shotgun genome sequencing.
    João Carlos Setubal and Renato F. Werneck.
    April 2001. In English, 20 pages.

    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 $ \ vert N \ vert $ is the number of contigs and $ \ vert L \ vert $ is the number of F / R pairs, the complexities are $ O (\ vert N \ vert + \ vert L \ vert \ log \ vert L \ vert) $ (greedy) and $ O (\ vert N \ vert ^ {2} + \ vert L \ vert \ log \ vert L \ vert) $ (maximum-weight path). This program has been successfully used in several bacterial genome projects.

    This report supersedes IC-TR-00-20.

  • IC-01-04 pdf bib
    A multi-scale technique for computer assisted re-assembly of fragmented objects.
    Helena Cristina da Gama Leitão and Jorge Stolfi.
    March 2001. In English, 23 pages.

    Abstract: We describe here an efficient algorithm for reassembling one or more unknown objects that have been broken or torn into a large number $ N $ 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 $ \ theta (N ^ 2 L ^ 2) $ (Onde $ L $ is the mean number of samples per fragment) to about $ O (N ^ 2 L) $; which, in principle, allows the method to be used for problems of practical size ($ N = 10 ^ 3 $ to $ 10 ^ 5 $ fragments, $ L = 10 ^ 3 $ to $ 10 ^ 4 $ 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).

  • IC-01-03 pdf bib
    Context-based JIT compilation: The design & implementation of a distributed JVM.
    R. Ferreira and G. Araújo.
    March 2001. In English, 193 pages.

    Abstract: Just-In-Time (JIT) compilation is a well-known technique used to improve the execution time in the Java VirtualMachine (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, offline, bytecode verification procedure; the design and implementation of a Java specific intermediate representation; and the detailed description of many JVM implementation issues.

  • IC-01-02 pdf bib
    Ethnographic-applied approach and the evaluation of interfaces: A case study.
    Janne Y. Y. Oeiras, Luciana A. S. Romani, Sílvia MS F. Massruhá, and M. Cecília C. Baranauskas.
    March 2001. In Portuguese, 18 pages.

    Summary: Methods for observing software users in their workplace tend to be increasingly necessary as the number of computer users grows and the inherent complexity of systems increases. Continuous assessment processes during the design life cycle seem to be a necessary condition for a good design result. Usability inspection methods by interface specialists, although effective in what they propose, do not capture elements of the user's work context. In this article we argue that ethnographic approaches represent an effective tool for the designer to evaluate in advance the contextual use of the system being proposed, during the design cycle. We illustrate, in a case study, how the use of ethnographic practices can serve in formative assessment and inform the redesign of the system.

    Key words:: Design, Ethnography, Interface, Formative assessment, Participatory Observation.

    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.

  • IC-01-01 pdf bib
    Approximation error maps.
    Anamaria Gomide and Jorge Stolfi.
    February 2001. In English, 23 pages.

    Abstract: Let $ F $ and $ A $ be two linear function spaces defined on some domain $ \ Omega $... Let $ \ left \ Vert \ cdot \ right \ Vert $ be a semi-norm vector for the space $ A + F $. We consider here the question of how well $ A $ approximate $ F $ in the sense of the metric $ \ left \ Vert \ cdot \ right \ Vert $. Global error measures are insufficiently informative when the space $ A $ 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 $ f \ in F $, 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.


  • 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