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
-difficult and is still open if it is
-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
-complete. For the third type, universality is
-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
-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
That the interior of points are 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 at 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 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.
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 click graph of the graph
is the intersection graph
of the (maximal) clicks of
. The iterated click graphs
are defined by
and
, Onde
and
is the click operator. THE graph is a graph with no induced subgraph isomorphic to
🇧🇷 In this article we describe the
-behavior of cographs and give some partial results for the larger class of serial (ie 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 analyzed.
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.
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.
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.
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.
Summary: Timed Automata (ATs) are a generalization of
-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
-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
-complete and we also show that, unlike
-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
-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 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.
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
(Onde
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 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.
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.
Abstract: Let
and
be two linear function spaces defined on some domain
... Let
be a semi-norm vector for the space
. We consider here the question of how well
approximate
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.
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 |