Technical Reports Published in 1998

  • IC-98-42 pdf bib
    Interface understood as communicating entities - A semiotic perspective.
    Osvaldo Luiz de Oliveira e M. Cecília Calani Baranauskas.
    December 1998. In English, 11 pages.

    Abstract: Some proposals based on Semiotics are being addressed in HCI literature as a complement to the traditional cognitive approaches to interface design. In such approaches the interface is understood as a collection of messages sent by the designer to the user. This paper discusses the main Semiotic proposals to software design and proposes a new understanding for interface design which makes explicit the communication among the entities that inhabit the interface. The proposal is illustrated by observing results of users in game playing situation.

  • IC-98-41 pdf bib
    Packing squares into squares.
    Carlos E. Ferreira, Flavio K. Miyazawa, and Yoshiko Wakabayashi.
    December 1998. In English, 15 pages.

    Abstract: We consider the problem of packing a list of squares into unit capacity squares. The objective of this problem is to minimize the number of squares used in the packing. We consider a restricted version of this problem and exhibit a polynomial time algorithm to solve it. We use this algoritm in the design of an approximation algorithm for the original problem, and show that its asymptotic performance bound is 1.988. This bound compares favorably with the bound 2.125, known for an algorithm obtained by Chung, Garey and Johnson for the more general problem, where the items to be packed are rectangles.

  • IC-98-40 pdf bib
    Acyclic clique-interval graphs.
    R. Zuchello and R. Dahab.
    October 1998. In English, 10 pages.

    Abstract: The class of acyclic clique-interval (ACI) graphs is introduced as the class of those graphs $G=(V,E)$ whose cliques are intervals (chains) of an acyclic order on the vertex set $V$. The class of ACI graphs is related to the classes of proper interval graphs, tree-clique graphs and to the class DV (intersection graphs of directed paths of a directed tree). Compatibility between a graph and an acyclic order is defined, ACI graphs are characterized in terms of it and some special sets of vertices are found by means of the acyclic compatible order. ACI graphs are also characterized in terms of the dual hypergraph of the hypergraph of all cliques of $G$. Results concerning substitution and reduction preserving the ACI status are established. A strong necessary condition for a graph to be an ACI graph is also given.

  • IC-98-39 pdf bib
    Improved algorithms for elliptic curve arithmetic in $GF(2^n)$.
    Julio López and R. Dahab.
    October 1998. In English, 12 pages.

    Abstract: This paper describes three contributions for the efficient implementation of elliptic curve cryptosystems in $GF(2^n)$. The first is a new method for doubling an elliptic curve point, which is simpler to implement than the fastest known method, due to Schroeppel, and which favors sparse elliptic curve coefficients. The second is a generalized and improved version of the Guajardo and Paar's formulas for computing repeated doubling points. The third contribution consists of a new kind of projective coordinates that provides the fastest known arithmetic on elliptic curves. The algorithms resulting from this new formulation lead to a running time improvement for computing a scalar multiplication of about $17\%$ over previous projective coordinate methods.

  • IC-98-38 pdf bib
    Gathering user interface design requirements for social computing.
    Antonio Mendes da Silva Filho and Hans Kurt E. Liesenberg.
    October 1998. In English, 13 pages.

    Abstract: Design for cooperation is a challenge. As designers we note that as we are moving towards the final years of this century, several areas have achieved significant breakthroughs. Among them, it is easy to perceive that areas of Computing and Telecommunications have had an impact of paramount importance to society as a whole. These technologies have allowed an increasing integration of research fields, people of various backgrounds and abilities as well as made the interaction of different cultures possible. As a result, we have been living in the Internet era with a very large number of Web sites which can be visited, queried and played with. That constitutes what we call social computing. Application examples are: digital libraries, health care information systems, Physics collaboratories, and Web-based entertainments like interactive Web games. Within this context, we are concerned with the user interface design requirements gathering for such systems. In that sense, we present a protagonist task-based approach for capturing the user interface design requirements.

  • IC-98-37 pdf bib
    Um Modelo Oculto de Markov para encontrar promotores em seqüências de DNA.
    Nalvo Franco de Almeida Jr. and João Carlos Setubal.
    October 1998. In Portuguese, 12 pages.

    Abstract: We present a Hidden Markov Model (HMM) to find binding sites, like promoters, in a DNA sequence. This approach allows variable-length spacers between the consensus sequences. The model was built using 150 known promoters of the Escherichia coli genome and uses the Expectation-Maximization (EM) algorithm to reestimate parameters. In order to test the model, we used 30 regions of E. coli, each one known to contain a promoter. By cutting randomly these regions, we produced 20 sets of 30 sequences. The model was able to determine the correct or nearly correct (within 6 bp) 78$\%$ of the consensus sequences of a set, on average. The program is available through the WWW and can be useful as a tool to find a promoter in any procaryotic DNA sequence.

  • IC-98-36 pdf bib
    Progressive construction of consistent global checkpoints.
    Islene Calciolari Garcia and Luiz Eduardo Buzato.
    October 1998. In English, 15 pages.

    Abstract: A checkpoint pattern is an abstraction of the computation performed by a distributed application. A progressive view of this abstraction is formed by a sequence of consistent global checkpoints that may have occurred in this order during the execution of the application. Considering pairs of checkpoints, we have determined that a checkpoint must be observed before another in a progressive view if the former Z-precedes the latter. Based on the Z-precedence and characteristics of the checkpoint pattern, we propose original algorithms for the progressive construction of consistent global checkpoints. We demonstrate that the Z-precedence between a pair of checkpoints is a much simpler way to express the existence of a zigzag path connecting them, and we discuss other advantages of our relation.

  • IC-98-35 pdf bib
    Exact solutions of rectangular partitions via integer programming.
    Cláudio Nogueira de Meneses and Cid Carvalho de Souza.
    October 1998. In English, 48 pages.

    Abstract: We are given a rectangle $R$ in the plane and a finite set $P$ of $n$ points in the interior of $R$. A rectangular partition of $R$ is a partition of the surface of $R$ into smaller rectangles. A rectangular partition is said to be feasible with respect to $P$ if no points in $P$ lie in the strict interior of any rectangle of the partition. The length of a rectangular partition is computed as the sum of the lengths of the straight line segments that define the boundary of its rectangles. The goal is to find a (feasible) rectangular partition whose length is minimized. This problem, denoted here by RGP, is NP-hard and has application in VLSI design. Several approximation algorithms have been proposed in the literature to solve it. In this paper we investigate how to obtain exact solutions for the RGP. We introduce two different Integer Programming formulations. To test these formulations computationally we have implemented a Branch-and-Cut algorithm and a Branch-and-Price algorithm for the first and the second formulation, respectively. Comparisons between the two formulations are made. The computational results with a randomly generated set of instances show that it is possible to solve exactly medium-sized instances of the RGP. Moreover, we show that the size of the instances that can be solved with our algorithms decrease by an order of magnitude in the absence of corectilinear points in $P$, a special case of RGP whose complexity is still open. Finally we also have implemented the best approximation algorithm known for RGP and we show that it usually produces solutions about 10$\%$ off the optimum.

  • IC-98-34 pdf bib
    Access structures for moving points.
    Mario A. Nascimento, Jefferson R. O. Silva, and Yannis Theodoridis.
    October 1998. In English, 23 pages.

    Abstract: Several applications require management of data which is spatially dynamic, e.g., tracking of battle ships or moving cells in a blood sample.

    The capability of handling the temporal aspect, i.e., the history of such type of data, is also important. This paper presents and evaluates three temporal extensions of the R-tree--the 3D R-tree, the $2+3$ R-tree and the HR-tree--which are capable of indexing spatiotemporal data. Our experiments have shown that while the HR-tree was the larger structure, its query processing cost was over 50$\%$ smaller than the ones yielded by the 3D R-tree and the $2+3$ R-tree. Also compared to the (non-practical) approach of storing one R-tree for each of the spatial database states it offered the same query processing cost, saving around one third of storage space.

  • IC-98-33 pdf bib
    Composition of meta-objects in Guaraná.
    Alexandre Oliva and Luiz Eduardo Buzato.
    September 1998. In English, 6 pages.

    Abstract: There are meta-object protocols (MOPs) that do not provide support for meta-object composition. Others require explicit modification of existing meta-level code or provide a limited delegation mechanism in order to support it. There is much room for improvement in this field.

    The MOP of Guaraná favors the development of meta-objects that can be easily composed. Composers are meta-objects that define arbitrary policies of delegation to other meta-objects, separating the implementation of meta-level functionality from its organization. Composers can also implement meta-level security policies, limiting the abilities of its component meta-objects. Composers can be further composed, forming a potentially infinite reconfigurable hierarchy.

    Our MOP is currently implemented in Java$^{\rm (TM)}$. Nevertheless, most design decisions presented in this paper can be transported to other programming languages and MOPs, improving their flexibility, reconfigurability, security and code reuse.

  • IC-98-32 pdf bib
    The implementation of Guaraná on Java.
    Alexandre Oliva and Luiz Eduardo Buzato.
    September 1998. In English, 26 pages.

    Abstract: Guaraná is a reflective architecture that aims at simplicity, flexibility, security and reuse of meta-level code. It is implemented as an extension of Kaffe OpenVM$^{\rm (TM)}$, a free implementation of the Java$^{\rm (TM)}$ Virtual Machine.

    We describe the Java classes that implement the meta-object protocol of Guaraná, and the modifications introduced in the virtual machine to intercept and reify of operations. Finally, we evaluate the performance impact of our modifications, and suggest some optimizations that may be implemented in the future.

  • IC-98-31 pdf bib
    Guaraná: A tutorial.
    Alexandre Oliva and Luiz Eduardo Buzato.
    September 1998. In English, 30 pages.

    Abstract: This text is a tutorial for people interested in using our Java$^{\rm (TM)}$-based implementation of Guaraná, a reflective architecture that aims at flexibility, security and reuse of meta-level code. It shows what kind of operations can be intercepted with Guaraná and how meta-objects can monitor and modify base-level behavior. It also introduces composition of meta-objects, and discusses dynamic reconfiguration and management of meta-configurations. Several tricks and internal details of the implementation are exposed, through the use of numerous examples and detailed explanations.

  • IC-98-30 pdf bib
    Maximizando o número de usuários em servidores de vídeo sob demanda.
    Nelson L. S. da Fonseca and Roberto de A. Façanha.
    August 1998. In Portuguese, 12 pages.

    Resumo: Aplicações de vídeo, como por exemplo Vídeo sob Demanda, requerem grande largura de banda para a transmissão de fluxos de vídeo. Portanto, o oferecimento de serviços de vídeo em larga escala requer o emprego de técnicas como Batching e Piggybacking. Neste artigo, introduz-se uma nova política de Batching que visa maximizar o número de usuários suportados por um servidor de vídeo.

    Abstract: The deployment of video services in large scale requires the adoption of bandwidth reduction techniques such as Batching and Piggybacking. In this paper, we introduce a new Batching policy which aims at maximizing the number of users in a video-on-demand system.

  • IC-98-29 pdf bib
    Facilitando o desenvolvimento de controle complexo usando Xchart.
    Fábio Nogueira de Lucena and Hans Kurt Edmund Liesenberg.
    August 1998. In Portuguese, 13 pages.

    Resumo: Um dos componentes de um sistema interativo cujo desenvolvimento apresenta maiores desafios é o gerenciador de diálogo. A especificação, o projeto, a implementação e a execução deste componente ainda são tarefas cujas ferramentas disponíveis praticamente não apresentam suporte, ao contrário do sucesso obtido por elas no desenvolvimento de outros componentes (a apresentação, por exemplo). Este trabalho descreve uma proposta para desenvolvimento de gerenciadores de diálogos composta pela linguagem Xchart e um ambiente de apoio. Xchart é uma linguagem visual e formal projetada para adequadamente capturar o controle complexo das funções de gerenciadores de diálogos, que podem estar organizados em uma arquitetura de software baseada em múltiplos agentes. Nesta proposta, controle complexo descrito através de diagramas executáveis eliminam a tarefa manual de gerar o código que o implementa e oferece suporte ao modelo de múltiplos agentes.

    Abstract: The development of the dialogue manager presents many challenges. Specification, design, implementation and execution are hard to define with the available tools. This work presents a proposal to develop dialogue managers: the Xchart language and support tools. Xchart is a visual and a formal language. It was designed to properly capture complex control of dialogue managers possibly based on multiple agents. In the proposed approach, complex control described through executable diagrams reduces the manual and error-prone task of generating code that implements it, and offers support to multiple agent architectures.

  • IC-98-28 pdf bib
    Service migration and a transparency service.
    B. Schulze, F. Assis Silva, S. Choy, I. Busse, and S. Covaci.
    August 1998. In English, 15 pages.

    Abstract: Location and migration distribution transparencies are considered in the context of multi agent systems. The extension of a mobile agent facility architecture is proposed with the addition of an availability service and a transparency service. Transparent mobility of services is explored in applications using overall load-balancing of resources. The search for a new destination agencies follows a transparent location and selection of available resources. Transparency is trimmed by a parameter defining the goal of the application.

  • IC-98-27 pdf bib
    Transparent service mobility using CORBA.
    B. Schulze and E. R. M. Madeira.
    August 1998. In English, 23 pages.

    Abstract: Distributed Object Computing platforms like CORBA allow for object programming separate from configuration and distribution, and the addition of a mobility support extends distribution aspects. Reviewing distributed object computing, we present a service-oriented architecture based on a OMG/CORBA platform. The addition of an availability service associated to a mobility service allows for transparent migration of components, i.e., services or agents. The current work presents more the structure behind the availability service and less the transparency interface to it. Transparent mobility of services is interesting in applications using load-balancing mixing strategies of normal caching and inverse caching, i.e., code moved close to data. The search for a new destination host follows a transparent location and selection of resources available on other hosts. Supportive testing is presented on an example of component migration in mobile computing.

  • IC-98-26 pdf bib
    Avaliação heurística de um sistema altamente dependente do domínio.
    Luciana Alvim Santos Romani and M. Cecília Calani Baranauskas.
    July 1998. In Portuguese, 13 pages.

    Resumo: Alguns domínios do conhecimento possuem, entre seus profissionais, um amplo espectro de expertise no uso da tecnologia do computador, que abrange desde usuários que se utilizam de sistemas computacionais em seu trabalho rotineiro, até novatos no uso dessa tecnologia. Argumenta-se que características específicas de usuários no domínio considerado devem ser observadas no design e na avaliacão de software. Neste artigo, é mostrado o uso da avaliacão heurística para análise de usabilidade de um sistema altamente dependente de domínio. O sistema escolhido para estudo de caso foi o Sistema de Acompanhamento e Avaliacão de Rebanhos Leiteiros (ProLeite), que é usado na organizacão das informacões de desempenho produtivo e reprodutivo dos animais de rebanhos leiteiros. Esse sistema possui grande quantidade de formulários para entrada de dados, e possibilita consultas e emissão de relatórios. A partir dos resultados da avaliacão heurística do sistema é mostrada a necessidade de um conjunto de heurísticas de categorias específicas, para captar aspectos específicos do domínio considerado.

    Abstract: Some knowledge domains have, among their personnel, a wide spectrum of expertise in the use of computer technology, which embraces from daily users of computational systems to beginners. We argue that specific characteristics of users in the domain should be considered in the design and software evaluation. In this paper we present the use of heuristic evaluation for usability analysis of a domain-dependent system. The system chosen for a case study was the Sistema de Acompanhamento e Avaliação de Rebanhos Leiteiros. This system is used for organizing information about productive and reproductive control of animals. It possesses a large amount of forms for entrance of data, queries and emission of reports. Results of the heuristic evaluation point to the need for specific category heuristics, to capture specific aspects of the considered domain.

  • IC-98-25 pdf bib
    Code compression based on operand factorization.
    Guido Araújo, Ricardo Pannain, Paulo Centoducatte, and Mario Côrtes.
    July 1998. In English, 22 pages.

    Abstract: This paper proposes a code compression technique called operand factorization. The key idea of operand factorization is the separation of program expression trees into sequences of tree patterns (opcodes) and operand patterns (registers and immediates). Using operand factorization we show that tree and operand patterns have exponential frequency distributions. A set of experiments is performed to determine the best encoding technique that explores this feature. The experimental results show an average compression ratio of 35$\%$ for SPEC CINT95 programs, when patterns are encoded using Huffman encoding. Another encoding method, that improves the performance of the decompression engine, results in an average compression ratio of 41$\%$. A decompression engine is proposed which assembles tree and operand patterns into uncompressed instruction sequences, using a combination of dictionaries and state machines.

  • IC-98-24 pdf bib
    On a conjecture of Lovász concerning bricks.
    Marcelo H. de Carvalho, Cláudio L. Lucchesi, and U. S. R. Murty.
    July 1998. In English, 53 pages.

    Abstract: In 1987, Lovász conjectured that every brick $G$ different from $K_{4}$, $\overline{C}_{6}$, and the Petersen graph has an edge $e$ such that $G-e$ is a matching covered graph with exactly one brick. Lovász and Vempala announced a proof of this conjecture in 1994. Their paper is under preparation. We present here an independent proof of their theorem. We shall in fact prove that if $G$ is any brick different from $K_{4}$ and $\overline{C}_{6}$ and does not have the Petersen graph as its underlying simple graph, then it has an edge $e$ such that $G-e$ is a matching covered graph with exactly one brick, with the additional property that the underlying simple graph of that one brick is different from the Petersen graph. Our proof involves establishing an interesting new property of the Petersen graph.

  • IC-98-23 pdf bib
    Capturing computer-human interaction design via the protagonist action notation.
    Antonio Mendes da Silva Filho and Hans Kurt E. Liesenberg.
    June 1998. In English, 14 pages.

    Abstract: With the recent increase in popularity of the Internet a new user population has emerged with little expertise to use interactive systems. Hence, developing interfaces for such systems has required the involvement of experts of several areas. A further observation is that about $50\%$ of the time and resources are consumed just for the interface component of well-designed interactive systems. In order to contribute to the quality improvement of interface components as well as to make the development process of such components more effective, a specification technique for Computer-Human Interaction (CHI), called Protagonist Action Notation (PAN) is presented. PAN along with the Task Coordination Model (TCM) are used to represent the control aspects of the CHI Design. An example of a networked Web game called NetConnect4 illustrates the use of PAN.

  • IC-98-22 pdf bib
    Some comments on thinning algorithms for 3-d images.
    Francisco Nivando Bezerra and Neucimar Jerônimo Leite.
    May 1998. In English, 9 pages.

    Abstract: The problem of defining simple points in a two-dimensional binary image was extensively discussed in the literature. This definition is more complicated for 3-d images due to the introduction of a new topological component, namely, the tunnel. Recently, some simple-point characterizations for these images have been proposed. In this paper we show the equivalences between these new characterizations and discuss the implementation problems concerned with their use in thinning algorithms. An extension of the 2-d gray-level thinning algorithm to the 3-d case is also presented.

  • IC-98-21 pdf bib
    Modelagem geométrica de 3-complexos celulares.
    L. A. P. Lozada e C. F. X. de Mendonça.
    May 1998. In Portuguese, 9 pages.

    Resumo: Um complexo celular tridimensional é uma subdivisão de um espaço topológico tridimensional em um número finito de células (vértices, arestas, faces e poliedros). A estrutura topológica de um 3-complexo celular (isto é, as relações abstratas de incidência e adjacência entre seus elementos) é representado mediante esquemas de colagens de poliedros. Neste trabalho propomos uma representação geométrica para a construção de 3-complexos celulares com topologia de 3-variedades fechadas e orientáveis, baseado em colagens de ``tetraedros topológicos'' com orientações consistentes.

  • IC-98-20 pdf bib
    Sistemas de pagamento eletrônico.
    Lucas de Carvalho Ferreira and Ricardo Dahab.
    May 1998. In Portuguese, 58 pages.

    Resumo: Neste trabalho, apresentamos um esquema que possibilita a análise e comparação de sistemas de pagamento eletrônico a partir de sua tipificação, dos requisitos para estes sistemas, seu modo de funcionamento e aspectos de implementação e apresentamos análises de alguns dos sistemas de pagamento eletrônico que consideramos mais importantes ou representativos.

    Abstract: In this work we present a framework for the analysis and comparison of electronic payment systems. The following aspects are considered: typification, desirable requisites, functioning description and implementation issues. This framework is then used to analyze some of the most popular or representative payment systems that have been proposed so far.

  • IC-98-19 pdf bib
    An adaptable transaction model for traditional and advanced applications.
    Maria Beatriz Felgar de Toledo and George Marconi de Araújo Lima.
    May 1998. In English, 10 pages.

    Abstract: Transaction processing systems provide the required tools to maintain data consistency transparently. However, application diversity imposes conflicting requirements on transaction management. This report presents a framework of adaptable transaction management supporting short-duration applications, long-duration applications and cooperative applications. In addition to allowing an application to choose a transaction manager according to its characteristics, the proposed framework provides version management and support for synchronous and asynchronous interactions among users working in collaboration.

  • IC-98-18 pdf bib
    A framework supporting integrated transaction and session management for cooperative applications.
    Maria Beatriz Felgar de Toledo.
    May 1998. In English, 14 pages.

    Abstract: This report presents a framework of integrated transaction and session management to meet the requirements of applications based on group work. Transaction management is provided in order to guarantee data consistency and recovery from failures with the additional benefit of structuring complex applications as nested transactions. Visibility between users is achieved by allowing unfinished work to be transferred between users or by establishing a synchronous session. Within a session users can update shared objects in turns and be notified of others' actions synchronously.

  • IC-98-17 pdf bib
    Cortes consistentes em aplicações distribuídas.
    Islene Calciolari Garcia and Luiz Eduardo Buzato.
    April 1998. In Portuguese, 7 pages.

    Resumo: A avaliação de predicados sobre estados globais consistentes é requerida em uma vasta classe de soluções para problemas em sistemas distribuídos. A construção de cortes consistentes de maneira assíncrona permite maior eficiência e flexibilidade a sistemas de monitorização. Consideramos a abordagem assíncrona para aplicações construídas sobre o Modelo de Processos e Mensagens e sobre o Modelo Objetos e Ações. Propomos uma arquitetura de software para sistemas de monitorização e analisamos a construção progressiva de checkpoints globais consistentes.

    Abstract: The evaluation of predicates against consistent global states is required to solve a large class of problems in distributed systems. The asynchronous construction of consistent cuts allows greater efficiency and flexibility to monitoring systems. We consider the asynchronous approach for applications built upon the Process and Message Model and upon the Object and Action Model. We propose a software architecture for monitoring systems and analyze the progressive construction of consistent global checkpoints.

  • IC-98-16 pdf bib
    Asynchronous construction of consistent global snapshots in the object and action model.
    Islene Calciolari Garcia and Luiz Eduardo Buzato.
    April 1998. In English, 18 pages.

    Abstract: The Object and Action Model (OAM) is well-known as an adequate paradigm to build fault-tolerant configurable distributed applications. The reconfiguration of an application depends on the construction of a consistent global snapshot of its global state. An atomic action that reads the states of all objects of the application is a simple and straightforward way to obtain such global snapshot, but reduces concurrency and interferes with the underlying computation. In the Process and Message Model (PMM) consistent snapshots can be constructed asynchronously by a component that passively receives process states. This paper presents OAM-based asynchronous global snapshot algorithms equivalent to PMM-based algorithms, built using a precedence relation defined for atomic actions. Arjuna, an object-oriented action-based distributed programming environment, has been used to implement these OAM-based global snapshot algorithms, allowing us to conclude that our approach is promising.

  • IC-98-15 pdf bib
    An overview of MOLDS: A meta-object library for distributed systems.
    Alexandre Oliva and Luiz Eduardo Buzato.
    April 1998. In English, 8 pages.

    Abstract: This paper presents a library of meta-objects suitable for developing distributed systems. The reflexive architecture of Guaraná makes it possible for these meta-objects to be easily combined in order to form complex, dynamically reconfigurable meta-level behavior. We briefly describe the implementation of Guaraná on Java. Then, we explain how several meta-level services, such as persistence, distribution, replication and atomicity, can be implemented in a transparent and flexible way.

  • IC-98-14 pdf bib
    The reflexive architecture of Guaraná.
    Alexandre Oliva, Islene Calciolari Garcia, and Luiz Eduardo Buzato.
    April 1998. In English, 13 pages.

    Abstract: This text describes a reflexive software architecture called Guaraná. Its run-time meta-level protocol has been designed to achieve a very high degree of flexibility, reconfigurability, security and meta-level code reuse. Composers are meta-objects that can be used to combine other meta-objects (that may be composers themselves) into dynamically modifyable meta-configurations. Instances of a class may have different meta-configurations, either determined explicitly or derived from the context in which every single object was created.

    A free Java-based implementation of the language-independent Guaraná reflexive architecture is currently available.

  • IC-98-13 pdf bib
    On computing a multiple of an elliptic curve point.
    Julio López and Ricardo Dahab.
    April 1998. In English, 10 pages.

    Abstract: We describe an improved algorithm for computing a multiple of a point on elliptic curves defined over finite fields of characteristic greater than three. The proposed algorithm is based on new formulae for computing repeated doubling points with only one field inversion, and the signed-digit exponent recoding algorithm. The new algorithm is shown to be faster than Müller's 1997 method. Our new formulae for repeated doubling points can also be used to speed up algorithms such as the $k$-ary method and the signed binary window method.

  • IC-98-12 pdf bib
    An improvement of the Guajardo-Paar method for multiplication on non-supersingular elliptic curves.
    Julio López and Ricardo Dahab.
    April 1998. In English, 9 pages.

    Abstract: This paper presents improved formulae for computing repeated doubling points on non-supersingular elliptic curves defined over finite fields of characteristic 2. These formulae, in combination with variants of the sliding-window method, lead to efficient algorithms for computing a multiple of a point on such elliptic curves. For many practical implementations of the finite field $GF(2^n)$, our formulae offer a computational advantage over Guajardo and Paar's 1997 results.

  • IC-98-11 pdf bib
    Register allocation for indirect addressing in loops.
    Guido Araújo and Sharad Malik.
    April 1998. In English, 10 pages.

    Abstract: Indirect addressing is by far the most used addressing mode in programs running in embedded CISC architectures. The reason is that it enables fast address computation combined with short instructions, resulting in faster/smaller programs. This paper proposes a solution to the problem of allocating address registers to array references within loops, when using indirect addressing combined with auto-increment. The result is a $O(n^{2.5})$ algorithm, based on the solution of a maximum bipartite matching problem, which minimizes the number of address registers required by a program.

    (A version on this paper is going to be published in ACM Transactions on Programming Languages.).

  • IC-98-10 pdf bib
    Semiotic proposals for software design: Problems and prospects.
    Osvaldo Luiz de Oliveira and M. Cecília Calani Baranauskas.
    April 1998. In English, 13 pages.

    Abstract: Recently, the wide use of computers raised the need for better interface design. As a complement to the traditional cognitive approaches to interface design some proposals based on Semiotics are being addressed in the HCI literature. In such approaches the interface is understood as a collection of messages sent by the designer to the user. With a focus on the relationship designer-message-user these approaches do not make explicit the dialogue between the user, the interface entities and among the entities themselves. This paper discusses the main current proposals for applying Semiotics to software design, their underlying drawbacks, and proposes using of Semiotics to make explicit the design of the communication among the entities that inhabit the interface.

  • IC-98-09 pdf bib
    A semiótica e o design de software.
    Osvaldo Luiz de Oliveira and M. Cecília Calani Baranauskas.
    April 1998. In Portuguese, 29 pages.

    Abstract: Software interface can be understood as a sign system manifested in computational processes, which people consciously or unconsciously create as they use or interpret systems. In this approach the computer has the role of a medium - a physical substance in which signs are manifested and used for communication. The aim of this work is to situate the reader in the context of the Semiotic Theory, presenting its foundations and roots, and to discuss the understanding of software design using the perspective of semiotic systems.

  • IC-98-08 pdf bib
    Exact algorithms for circles on the sphere.
    Marcus Vinícius A. Andrade and Jorge Stolfi.
    April 1998. In English, 16 pages.

    Abstract: We develop exact algorithms for geometric operations on general circles and circular arcs on the sphere, using integer homogeneous coordinates. The algorithms include testing a point against a circle, computing the intersection of two circles, and ordering three arcs out of the same point. These operations allow robust manipulation of maps on the sphere, providing a reliable framework for GIS, robotics, and other geometric applications.

    (This paper will be presented at the ACM Symposium on Computational Geometry, Minneapolis, June 07-10, 1998.).

  • IC-98-07 pdf bib
    Política de piggybacking $S^2$.
    Roberto A. Façanha and Nelson L. S. Fonseca.
    April 1998. In Portuguese, 13 pages.

    Resumo: Em ambientes de vídeo sob demanda, espera-se que após a seleção do filme a exibição do mesmo inicie em curto intervalo de tempo. Isto é possível se existir banda passante disponível para satisfazer às requisições dos usuários. Diversas técnicas foram propostas com o objetivo de reduzir a grande demanda de banda passante em servidores de vídeo. Neste artigo, a política $S^2$ e uma heurística para redução da complexidade de geração da árvore de mesclagens de fluxos de vídeo são introduzidas e analisadas.

  • IC-98-06 pdf bib
    Automatic reassembly of irregular fragments.
    Helena Cristina da Gama Leitão and Jorge Stolfi.
    April 1998. In English, 38 pages.

    Abstract: This report addresses the following problem: given one or more unknown objects that have been broken or torn into a large number of irregular fragments, find the pairs of fragments that were adjacent in the original objects.

    Our approach is based on information extracted from the fragment outlines, which is used to compute the mismatch between pairs of pieces of contour. In order to asymptotically reduce the cost of matching, we use a multiple scales technique: after filtering and resampling the fragment outlines at several different scales of detail, we look for initial matchings at the coarsest possible scale. We then repeatedly select the most promising pairs, and re-match them at the next finer scale of detail. In the end, we are left with a small set of fragment pairs that are most likely to be adjacent in the original object.

  • IC-98-05 pdf bib
    Multiple class selective discard polices under a longe-range dependent process.
    Nelson L. S. Fonseca and Marcelo J. Ferreira.
    April 1998. In English, 7 pages.

    Abstract: Providing diverse QoS requirements in multimedia networks is a challenging task. Under a long-range dependent process, the loss rate does not decrease considerably as we increase the buffer size. In this paper, we investigate the advantages of adopting a multi-priority selective discard mechanisms over traditional two-priority mechanisms under a long range dependent process.

  • IC-98-04 pdf bib
    On the efectiveness of the Longest-Packet-In selective packet discarding policy.
    Nelson L. S. Fonseca and Marcelo J. Ferreira.
    March 1998. In English, 33 pages.

    Abstract: In this paper, we introduce a novel packet discarding policy called Longest-Packet-In (LPI) which maximizes the cell goodput, the ratio of outgoing good cells to the total number of cells that arrive at a queue. We compare LPI to: Tail Drop, Early Packet Discard, Early Packet Discard with Hysteresis, and Fair Early Packet Discard with Hysteresis, by investigating the trade-off between maximizing the cell goodput and maximizing the packet goodput. We show that LPI not only provides the highest cell goodput, but also produces the highest packet goodput for a high ratio of the mean packet size to the buffer size and under a short-range dependent process. We evaluate the impact of network load, mean packet size, packet distribution and the Hurst parameter into both the cell goodput and into the packet goodput. Furthermore, we extend our analysis to networks which carry sources with distinct mean packet length.

  • IC-98-03 pdf bib
    Ear decompositions of matching covered graphs.
    Marcelo H. Carvalho, Cláudio L. Lucchesi, and U. S. R. Murty.
    February 1998. In English, 15 pages.

    Abstract: Ear decompositions of matching covered graphs are important for understanding their structure. By exploiting the properties of the dependence relation introduced by Carvalho and Lucchesi, we are able to provide simple proofs of several well-known theorems concerning ear decompositions. Our method actually provides proofs of generalizations of these theorems. For example, we show that every matching covered graph $G$ different from $K_2$ has at least $\Delta$ edge-disjoint removable ears, where $\Delta$ is the maximum degree of $G$. This shows that any matching covered graph $G$ has at least $\Delta !$ different ear decompositions, and thus is a generalization of the fundamental theorem of Lovász and Plummer establishing the existence of ear decompositions. We also show that every brick $G$ other than $K_4$ and the triangular prism has $\Delta -2$ edges, each of which is a removable edge in $G$, that is, an edge whose deletion from $G$ results in a matching covered graph. This generalizes a well-known theorem of Lovász. Using this theorem, we give a simple proof of another theorem due to Lovász which says that every non-bipartite matching covered graph has a canonical ear decomposition, that is, one in which either the third graph in the sequence is an odd-subdivision of $K_4$ or the fourth graph in the sequence is an odd-subdivision of the triangular prism. Our method in fact shows that every non-bipartite matching covered graph has a canonical ear decomposition which is optimal, that is, one which has as few double ears as possible.

  • IC-98-02 pdf bib
    Finite automata and efficient lexicon implementation.
    Tomasz Kowaltowski, Cláudio L. Lucchesi, and Jorge Stolfi.
    January 1998. In English, 12 pages.

    Abstract: We describe a general technique for the encoding of lexical functions -- such as lexical classification, gender and number marking, inflections and conjugations -- using minimized acyclic finite-state automata. This technique has been used to store a Portuguese lexicon with over 2 million entries in about 1 megabyte. Unlike general file compression schemes, this representation allows random access to the stored data. Moreover it allows the lexical functions and their inverses to be computed at negligible cost. The technique can be easily adapted to practically any language or lexical classification scheme, and this task does not require any knowledge of the programs or data structures.

  • IC-98-01 pdf bib
    Representing conics using the oriented projective plane.
    Guilherme A. Pinto and Pedro J. de Rezende.
    January 1998. In English, 7 pages.

    Abstract: We present a geometric definition of conic sections in the oriented projective plane and describe some of their nice properties. The three main classes of affine conics are unified by a generalized distance notion on that space. This definition leads to a very simple representation of conic arcs suitable for implementations of geometric solutions to problems involving the concept of distance, in particular, the construction of various generalizations of Voronoi diagrams.

  • Instituto de Computação :: Universidade Estadual de Campinas
    Caixa Postal 6176 • Av. Albert Einstein, 1251 - Cidade Universitária • CEP 13083-970 • Campinas/SP - Brasil • Fone: [19] 3521-5838