Technical Reports Published in 2009

  • IC-09-48 pdf bib
    Multivariate formal power series invariants generation for non linear hybrid systems.
    Nadir Matringe, Arnaldo V. Moura, and Rachid Rebiha.
    December 2009. In English, 22 pages.

    Abstract: We present the first automatic verification methods that automatically generate invariants which are assertions expressed by multivariate formal power series. We also discuss their convergence analysis over hybrid systems that exhibit highly non linear models. As far as we know, this is the first approach that can deal with this type of systems or that can automatically generate this type of invariants. We show that the preconditions for discrete transitions, the Lie-derivatives for continuous evolution and the newly introduced relaxed consecution requirements can be viewed as morphisms and thus can be suitably represented by matrices. By doing so, we reduce the invariant generation problem to linear algebraic matrix systems, from which one can provide very effective methods for solving the original problem. Such methods have much lower time complexities than other approaches based on Grobner basis computations, quantifier eliminations, cylindrical algebraic decompositions, directly solving non-linear systems or abstract operators, or even the more recent constraint-based approaches. More specifically, we bring necessary and sufficient conditions that allow existence and completeness proofs for our formal power series invariant generation methods. We illustrate the efficiency of our computational methods by dealing with highly non linear and complex hybrid systems.

  • IC-09-47 pdf bib
    Evaluating the potential of texture and color descriptors for remote sensing image retrieval and classification.
    Jefersson Alex dos Santos, Otávio Augusto Bizetto Penatti, and Ricardo da Silva Torres.
    December 2009. In English, 13 pages.

    Abstract: Classifying Remote Sensing Images (RSI) is a hard task. There are automatic approaches whose results normally need to be revised. The identification and polygon extraction tasks usually rely on applying classification strategies that exploit visual aspects related to spectral and texture patterns identified in RSI regions. There are a lot of image descriptors proposed in the literature for content-based image retrieval purposes that can be useful for RSI classification. This paper presents a comparative study to evaluate the potential of using successful color and texture image descriptors for remote sensing retrieval and classification. Seven descriptors that encode texture information and twelve color descriptors that can be used to encode spectral information were selected. We highlight the main characteristics and perform experiments to evaluate the effectiveness of these descriptors. To evaluate descriptors in classification tasks, we also proposed a methodology based on KNN classifier. Experiments demonstrate that Joint Auto-Correlogram (JAC), Color Bitmap, Invariant Steerable Pyramid Decomposition (SID) and Quantized Compound Change Histogram (QCCH) yield the best results.

  • IC-09-46 pdf bib
    An exact algorithm for an art gallery problem.
    Marcelo C. Couto, Pedro J. de Rezende, and Cid C. de Souza.
    November 2009. In English, 25 pages.

    Abstract: We consider an Art Gallery problem (AGP) which aims to minimize the number of vertex guards required to monitor an art gallery whose boundary is an $ n $-vertex simple polygon. In this paper, we compile and extend our research on exact approaches for solving the. In prior works, we proposed and tested an exact algorithm for the case of orthogonal polygons. In that algorithm, a discretization that approximates the polygon is used to formulate an instance of the Set Cover Problem which is subsequently solved to optimality. Either the set of guards that characterizes this solution solves the original instance of the AGP, and the algorithm halts, or the discretization is refined and a new iteration begins. This procedure always converges to an optimal solution of the AGP and, moreover, the number of iterations executed highly depends on the way we discretize the polygon. Notwithstanding that the best known theoretical bound for convergence is $ \ Theta (n ^ 3) $ iterations, our experiments show that an optimal solution is always found within a small number of them, even for random polygons of many hundreds of vertices. Herein, we broaden the family of polygon classes to which the algorithm is applied by including non orthogonal polygons. Furthermore, we propose new discretization strategies leading to additional trade-off analysis of preprocessing vs. processing times and achieving, in the case of the novel Convex Vertices strategy, the most efficient overall performance so far. We report on experiments with both simple and orthogonal polygons of up to 2500 vertices showing that, in all cases, no more than 15 minutes are needed to reach an exact solution, on a standard desktop computer. Ultimately, we more than doubled the size of the largest instances solved to optimality compared to our previous experiments, which were already five times larger than those previously reported in the literature.

  • IC-09-45 pdf bib
    A Two-Phase Model for Wikipedia Growth.
    Jorge Stolfi.
    November 2009. In English, 17 pages.

    Abstract: The number of articles $ N (t) $ in Wikipedia is quite accurately modeled as a function of time $ t $ by two exponential regimes or phases, with a relatively sharp transition over a one-year period centered on Janary 2006. The first regime has a positive rate constant $ R_1 = + $ 0.00217 per day, corresponding to a doubling time of about 10.5 months. The second regime has a negative rate constant $ R_2 = -0.000407 $ per day, corresponding to a halving time of about 4.5 years. The model predicts that $ N (t) $ will tend to a finite limit of about 5.9 million articles. We advance some possible explanations and implications of the negative rate.

  • IC-09-44 pdf bib
    SPICA's Multi-party Negotiation Protocol: Implementation using YAWL.
    E. Bacarin, ERM Madeira, CMB Medeiros, and WMP van der Aalst.
    November 2009. In English, 46 pages.

    Abstract: A supply chain comprises several different kind of actors that interact either in an ad hoc fashion (eg, an eventual deal) or in a previously well planned way. In the latter case, how the interactions develop is described in contracts that are agreed on before the interactions start. This agreement may involve several partners, thus a multi-party contract is better suited than a set of bi-lateral contracts. If one is willing to negotiate automatically such kind of contracts, an appropriate negotiation protocol should be at hand. However, the ones for bi-lateral contracts are not suitable for multi-party contracts, eg, the way of achieving consensus when only two negotiators are haggling over some issue is quite different if there are several negotiators involved. In the first case, a simple bargain would suffice, but in the latter a ballot process is needed. This paper presents a negotiation protocol for electronic multi-party contracts which seamlessly combines several negotiation styles. It also elaborates on the main negotiation patterns the protocol allows for: bargain (for peer-to-peer negotiation), auction (when there is competition among the negotiators) and ballot (when the negotiation aims at consensus). Finally, it describes an implementation of this protocol based on Web services, and built on the YAWL Workflow Management System.

  • IC-09-43 pdf bib
    An architecture-independent dynamic link system based on adl.
    Rafael Auler, Paulo Cesar Centoducatte, and Alexandro Baldassin.
    November 2009. In Portuguese, 34 pages.

    Summary: Different instructions are implemented in processors with an application specific instruction set (ASIPs), motivated by the need to specialize the processor for a given software load on an embedded platform. For the project to be completed in a timely manner, it is important to reduce the efforts required to build software development tools and simulators for the new platform. For this, simulators and other tools can be automatically synthesized based on the description of the processor architecture. In this technical report we discuss the design of a complete dynamic linkage system independent of target architecture, comprising the ability to automatically generate linkers: a build-time linker and a loader for runtime linkage. The system, however, is dependent on the object file and adopts the ELF format. The charger used was specifically built for this project so that we don't depend on the glibc library charger. The main objective is the easy redirection to application on a target processor as well as to their respective application binary interface rules (ABI - Application Binary Interface). Such target-dependent information is automatically extracted from a model described in an architecture description language (ADL - Architecture Description Language). The study focuses on implementation at ADL ArchC, and validation tests for the ARM architecture are presented, accompanied by a brief analysis of the experimental results for the simulator.

    Abstract: Different instructions are implemented by Aplication Specific Instruction-Set Processors (ASIPs), motivated by the need of processor specialization to a known software load in an embedded platform. In order to meet time demands, it is critical to reduce necessary efforts to build software development tools and simulator for the platform under development. To address this problem, simulators and other tools can be automatically generated based on a processor architecture description. In this technical report we discuss the project of a complete architecture independent dynamic linking system: the linker for compile-time and loader for run-time. The system is object file dependent and relies on the flexible ELF. Our loader is specifically designed for this project and we don't depend upon glibc's loader. The main purpose is to be easily retargetable for application in a target processor and respective Application Binary Interface (ABI) rules. These target specific information are extracted from an Architecture Description Language (ADL) model. Our study focuses on the ADL ArchC, and validation tests for the ARM architecture are presented.

  • IC-09-42 pdf bib
    Dominant sets in grids.
    Izumi Oniki Chiquito and C. N. Campos.
    November 2009. In Portuguese, 22 pages.

    Summary: Be $ P_ {m} $ e $ P_ {n} $ two paths of $ m $ e $ n $ vertices, respectively. a grid $ G_ {m \ times n} $ is the graph corresponding to the Cartesian product $ P_ {m} \ times P_ {n} $. In this work, we deal with dominant sets in grids. A dominant set of a graph $ G $ is a subset $ D $ of its set of vertices, such that every vertex of $ G $ or belongs to $ D $, or is adjacent to an element of $ D $. It is known that the determination of the domination number, that is, the cardinality of the smallest possible dominant set, is an NP-difficult problem for arbitrary graphs. However, this number is known for the subclass of grids in cases where $ 1 \ leq m \ leq 6 $. In this text, we provide an upper limit on the number of domination of $ G_ {m \ times n} $, with $ 7 \ leq m \ leq 10 $, as well as a polynomial algorithm to obtain dominant sets whose sizes reach this limit. Chang, Clark and Hare had similar limitations, but the results presented here were developed independently of the work of these authors.

  • IC-09-41 pdf bib
    Specifying Meta-communication Mechanisms for Vila Na Rede System.
    Elaine C. S. Hayashi and M. Cecília C. Baranauskas.
    October 2009. In English, 17 pages.

    Abstract: The main purpose of this document is to define the mechanisms functionalities and detailed elements. Starting from a more general description of the mechanism to be implemented, this technical report presents the meta-communication instrument instantiated at Vila na Rede - an inclusive social network system developed in the context of the e-Citizenship Project.

  • IC-09-40 pdf bib
    Preliminary Evaluation of Vila na Rede - An Inclusive Social Network System.
    Elaine C. S. Hayashi, Vania P. A. Neris, Carla L. Rodrigues, Leonardo C. de Miranda, Heiko H. Hornung, Vagner F. de Santana, Roberto Pereira, M. Cecília Martins, and M. Cecilia C. Baranauskas.
    October 2009. In English, 64 pages.

    Abstract: Vila na Rede conception and development is part of the e-Citizenship Project, which aims to study and propose solutions to challenges of interaction and user interface design on systems related to the practice of citizenship, contributing to the promotion of a digital culture in the Brazilian society. This Technical Report presents a preliminary evaluation of the Vila na Rede system by using three distinct dimensions: a) an evaluation of the interaction based on task analysis; b) an inspection of usability and accessibility of its user interface; and c) an analysis of the first nine months of the beta version system usage. Some changes and evolution caused by this analysis are also presented and discussed.

  • IC-09-39 pdf bib
    Image retrieval by multi-scale interval distance estimation.
    Carlos Elias Arminio Zampieri and Jorge Stolfi.
    October 2009. In English, 11 pages.

    Abstract: We describe a general method for query-by-example retrieval in image collections, using arithmetic interval to perform multi-scale distance estimation. The interval estimates are used to quickly eliminate candidate images at small scales, in a fashion similar to the branch-and-bound optimization paradigm. Experiments indicate that the method can provide significant speedup relative to exhaustive search; nevertheless, the method always returns the exact best match (and not merely an approximation thereof). The technique allows queries with a wide variety of image similarity functions, without the need to precompute or store specific descriptors for each function.

  • IC-09-38 pdf bib
    Generating test suites for timed systems with context variables.
    Adilson Luiz Bonifácio and Arnaldo Vieira Moura.
    October 2009. In English, 41 pages.

    Abstract: Model-based testing has been widely used for testing critical and reactive systems. Some aspects of reactive systems are treated by extended models that captures the notion of data flow on the system as well as its interactions with the environment. Other aspects are captured by conventional timed models that allow for the continuous evolution of time variables. Devising formal methods to automatically generate test suites for systems that comprise both of these has remained a challenge. In this work we use a new Timed Input / Output Context Automata (TIOCA) as a formal model for timed systems with context variables. We propose and prove the correctness of a new strategy to discretize TIOCA models, thus obtaining related grid automata. Grid automata allow us to automatically generate test cases based on test purposes, the latter being special TIOCA that specifically model those system properties to be tested. We also discuss how to extract test suites from the synchronous product of a TIOCA and an associated test purpose. Further, we show how to use test suites in order to automatically verify whether given implementations according to the specification and, also, reflect the desired properties.

  • IC-09-37 pdf bib
    Learning to rank for content-based image retrieval.
    Fábio Augusto Faria, Adriano Veloso, Humberto M. Almeida, Eduardo Valle, Ricardo da S. Torres, M. A. Gonçalves, and W. Meira Jr.
    October 2009. In English, 14 pages.

    Abstract: In Content-based Image Retrieval (CBIR), accurately ranking the returned images is of paramount importance, since it is common-sense that users consider mostly the topmost results. The typical ranking strategy used by many CBIR systems is to employ image content descriptors, so that returned images that are most similar to the query image are placed higher in the rank. While this strategy is well accepted and widely used, improved results may be obtained by combining multiple image descriptors. In this paper we explore this idea, and introduce algorithms that learn to combine information coming from different descriptors. The proposed learning to rank algorithms are based on three diverse learning techniques: Support Vector Machines (CBIR-SVM), Genetic Programming (CBIR-GP), and Association Rules (CBIR-AR). Eighteen image content descriptors (color, texture, and shape information) are used as input and provided as training to the learning algorithms. We performed a systematic evaluation involving two complex and heterogeneous image databases (Corel and Caltech) and two evaluation measures (Precision and MAP). The empirical results show that all learning algorithms provide significant gains when compared to the typical ranking strategy in which descriptors are used in isolation. We concluded that, in general, CBIR-AR and CBIR-GP outperforms CBIR-SVM. A fine-grained analysis revealed the lack of correlation between the results provided by CBIR-AR and the results provided by the other two algorithms, which indicates the opportunity of an advantageous hybrid approach.

  • IC-09-36 pdf bib
    Proceedings of the V Thesis, Dissertations and Scientific Initiation Work in Progress Workshop IC-UNICAMP.
    Mariana Piquet Dias, Cecília Mary F. Rubira, Rodolfo Jardim de Azevedo, Carla G. N. Macario, Joana E. G. Malaverr, Jefersson Alex dos Santos, Luiz Fernando Bittencourt, Ricardo Caceffo, Roberto Pereira, and Vânia Paula de A. Neris.
    September 2009. Partly in English, partly in Portuguese, 232 pages.

    Summary: This technical report contains summaries of 76 papers presented at the 2009th Workshop of Theses, Dissertations and Scientific Initiation Work in Progress at the UNICAMP Computing Institute (WTD-IC-UNICAMP XNUMX).

    In 2009, the Workshop was part of the celebrations of "40 years of Computing at UNICAMP", when the first Bachelor's Degree in Computer Science in Brazil was created by Unicamp on March 18, 1969. In this special edition we had, in addition to traditional oral presentations, a poster fair, in order to allow a greater number of students to participate.

    The Workshop, held from September 29 to October 1, 2009, allowed the Institute's doctoral students, master's students and undergraduate students to present the main aspects of their research.

    Each doctoral, master's or scientific initiation work summary corresponds to an oral presentation or poster presentation, the text being limited to 4 pages. The publication of abstracts in the form of a technical report aims to (i) publicize the work in progress at the IC and (ii) record succinctly the state of the art of the IC research in 2009.

  • IC-09-35 pdf bib
    Edge-coloring of split graphics.
    Sheila Morais de Almeida, Célia Picinin de Mello, and Aurora Morgana.
    September 2009. In English, 11 pages.

    Abstract: The Classification Problem is the problem of deciding whether a simple graph has chromatic index equals to $ \ Delta $ or $ \ Delta + 1 $, Onde $ \ Delta $ is the maximum degree of the graph. It is known that to decide if a graph has chromatic index equals to $ \ Delta $ is NP-complete. THE split graph is a graph whose vertex set admits a partition into a stable set and a click. The chromatic indexes for some subsets of split graphs, such as split graphs with odd maximum degree and split-indifference graphs, are known. However, for the general class, the problem remains unsolved. In this paper we exhibit a new subset of split graphs with even maximum degree that have chromatic index equal to $ \ Delta $. Moreover, we present polynomial time algorithms to perform an edge-coloring and to recognize these graphs.

  • IC-09-34 pdf bib
    On an abstract theory of computational models and the converse of Rice's theorem.
    Igor Carboni Oliveira, Arnaldo Vieira Moura, and Walter Carnielli.
    September 2009. In English, 13 pages.

    Abstract: In this paper we put forward an abstract definition of computational model and provide a negative answer to a conjecture involving the converse of Rice's theorem. In particular, any reasonable formal system in which the notion of computation is involved should satisfy our general definition of computational model. Furthermore, in order to give a natural counter-example to our conjecture we present a new interpretation to a result of Bernardi [1] involving undecidability in sufficiently strong formal theories. Finally, we raise the question if an abstract theory of computational models can lead to new problems and interesting results in theoretical computer science.

  • IC-09-33 pdf bib
    A generalization of the time and space hierarchy theories.
    Igor Carboni Oliveira and Arnaldo Vieira Moura.
    September 2009. In English, 7 pages.

    Abstract: In this paper we introduce a new class of complexity measures and prove a general hierarchy theorem in computational complexity. In addition, we derive as a particular case of our result the traditional time and space hierarchy theorems.

  • IC-09-32 pdf bib
    False abortions in software transactional memory systems.
    Daniel Nicácio and Guido Araújo.
    September 2009. In Portuguese, 22 pages.

    Summary: Transactional memory (MT) remains the most promising approach to replace locks in concurrent programming, but MT systems in software (MTS) still do not perform satisfactorily when compared to implementations using locks well refined. It is known that the critical operation in MV systems is to guarantee the atomicity and isolation of threads that are running concurrently. This task is known as validating read / write sets. In an attempt to carry out this process as quickly as possible, MTS systems usually use a possession table to perform conflict detection, but this approach generates false positives, which result in false abortions. This paper shows the true impact of false abortions and how their relevance increases as the number of threads competitors also increases, showing that this factor is essential for MTS systems. We propose two different techniques to prevent false abortions and consequently improve the performance of MTS. The first is a collision list attached to the existing table hash. The second is a completely new and efficient technique for detecting conflicts between transactions. This new technique makes use of SSE technology to detect conflicts and replaces the normally used table hash. Due to its memory mapping scheme, this technique is able to prevent the occurrence of false positives. With fast collision detection and free of false conflicts, we have achieved significant performance improvements in some STAMP benchmark programs. O SpeedUp obtained was up to 1,63x. We also show that speedups get bigger and bigger with the increase in the number of threads parallel. Finally, based on the results obtained, we characterize the programs that were most benefited by the two techniques.

    Abstract: Transactional memory (TM) continues to be the most promising approach replacing locks in concurrent programming, but TM systems based on software (STM) still lack the desired performance when compared to fine-grained lock implementations. It is known that the critical operation in TM systems is to ensure the atomicity and isolation of concurrently executing threads. This task is known as the read / write-set validation. In attempt to make this process as fast as possible, STM systems usually use ownership tables to perform conflict detection, but this approach generates false positive occurrences, which result in false aborts. This paper shows the real impact of false aborts and how its relevance increases along with the number of concurrent threads, showing it is an essential factor for TM systems. We propose two different techniques to avoid false aborts, consequently improving the TM performance. The first is a collision list attached to the existing hash table. The second is a novel and efficient technique to detect conflicts between transactions. This technique makes use of SSE technology to detect conflicts and replaces the commonly used hash table. Due to its memory mapping scheme, the technique avoids false positive occurrences. With fast collision detection, free of false conflicts, we achieved significant performance improvements in some STAMP benchmark programs. The speedup obtained was up to 1.63x. We also show that speedups become higher when the number of parallel threads increases. Finally, based on the results obtained, we characterize which programs are most benefited by the two techniques.

  • IC-09-31 pdf bib
    A new timed discretization method for automatic test generation for timed systems.
    Adilson Luiz Bonifácio and Arnaldo Vieira Moura.
    September 2009. In English, 33 pages.

    Abstract: Devising formal techniques and methods that can automatically generate test case suites for timed systems has remained a challenge. In this work we use Timed Input / Output Automata (TIOA) as a formal specification model for timed systems. We propose and prove the correctness of a new and more general discretization method that can be used to obtain grid automata corresponding to specification TIOA, using almost any granularity of interest. We also show how test purposes, for modeling specific system properties, can be used together with the TIOA specification in order to generate grid automata that captures the behavior of both the specification and the test purpose. From such grid automata one can, then, algorithmically extract test suites that can be used to verify whether given implementations according to the specification and reflect the desired properties.

  • IC-09-30 pdf bib
    Genome rearrangement phylogeny using the single-cut-or-join operation.
    Pedro Cipriano Feijão and João Meidanis.
    September 2009. In English, 9 pages.

    Abstract: The problem of parsimonious phylogeny reconstruction using genome rearrangement is called Multiple Genome Rearrangement Problem. There are two usual approaches: the small phylogeny problem, where a tree is given and we want to find the ancestral nodes that minimize total branch length of the tree; and the big phylogeny problem, finding the tree and ancestral nodes with minimum total branch length. In this paper we show that, under the Single-Cut-or-Join metric, the small phylogeny problem is solvable in polynomial time while the big phylogeny problem is NP-hard.

  • IC-09-29 pdf bib
    Comparison of finite element bases for global illumination in image synthesis.
    Anamaria Gomide, Danillo Roberto. Pereira, and Jorge Stolfi.
    September 2009. In English, 17 pages.

    Abstract: Finite element bases defined by sampling points were used by J. Lehtinen in 2008 for the efficient computation of global illumination in virtual scenes. The bases provide smooth approximations for the radiosity and spontaneous emission functions, leading to a discrete version of Kajiya's rendering equation. Unlike methods that are based on surface subdivision, Lehtinen's method can cope with arbitrarily complex geometries. In this paper we present an experimental validation of Lehtinen's meshless method by comparing its results with an independent numerical solution of the rendering equation on a simple three-dimensional scene. We also compare Lehtinen's special finite-element basis with two other similar bases that are often used for meshless data interpolation, namely a radial basis with a Gaussian mother function, and Shepard's inverse-square-distance weighted interpolation. The results confirm the superiority of Lehtinen's basis and clarify why the other two bases provide inferior-looking results.

  • IC-09-28 pdf bib
    Games with purpose and knowledge building in design.
    Roberto Romani and Maria Cecília C. Baranauskas.
    August 2009. In Portuguese, 11 pages.

    Summary: The design of “for all” systems is not a trivial task for the user interface (UI) designers, since countless aspects must be considered so that ICTs (Information and Communication Technologies) make sense and can be used by the citizen . Extending the concept of user-centered design in such a way that a significant part of potential users could give their opinion on the design of the interfaces, would involve the participation of hundreds or thousands of people in this process. This work proposes the use of human competence to assist in the development of interfaces accessible to all through Games With A Purpose (GWAP). We propose to involve the user in the construction of knowledge, making him co-participant in the design process. Initial analyzes suggest the potential of using games for the purpose of assisting UI designers in making informed choices about system design elements that should be for everyone.

    Abstract: The design of systems for all is not a trivial task for user interface (UI) designers. Many aspects should be considered to enable ICT (Information and Communication Technologies) to make sense and be used by citizens. Extending the concept of user centered design to a meaningful portion of potential users would involve the participation of hundreds or thousands of people in this process. This paper proposes the use of the human expertise to assist in the development of accessible interfaces for all, by using the Games With A Purpose (GWAP) approach. We propose to bring the user to the design processes, contributing to his / her construction of knowledge and co-participation. Initial analyzes suggest the potential of using games with a purpose to help designers with regard to informed choices of UI elements in the design of systems for all.

  • IC-09-27 pdf bib
    Recognizing well covered graphs of families with special $ P_4 $-components.
    Sulamita Klein, Célia Picinin de Mello, and Aurora Morgana.
    August 2009. In English, 13 pages.

    Abstract: The graph $ G $ is called well covered if every two maximal independent sets of $ G $ have the same number of vertices. In this paper we shall use the modular and primeval decomposition techniques to decide well coveredness of graphs such that, either all of them $ P_4 $-connected components are separable or they belong to well known classes of graphs that, in some local sense, contain few $ P_4 $'s. In particular, we shall consider the class of cographs, $ P_4 $-reducible, $ P_4 $-sparse, extended $ P_4 $-reducible, extended $ P_4 $-sparse graphs, $ P_4 $-extendible graphs, $ P_4 $-lite graphs, and $ P_4 $- tidy graphs.

  • IC-09-26 pdf bib
    A tool for detection of similarities in large software systems (preliminary report).
    Tomasz Kowaltowski and Ranieri C. Pereira Filho.
    August 2009. In English, 9 pages.

    Abstract: Reuse of program parts through cloning and adaptation is a common practice in software development. However it creates later problems in system maintenance. This report describes the main ideas behind a tool developed to assist in identification of software clones based on some techniques used in detecting program plagiarism.

  • IC-09-25 pdf bib
    Components meet aspects: Assessing design stability of a software product line.
    Leonardo P. Tizzei, Marcelo Dias, Cecília MF Rubira, Alessandro Garcia, and Jaejoon Lee.
    July 2009. In English, 12 pages.

    Abstract: A Product Line Architecture (PLA) should remain stable accommodating evolutionary changes of stakeholder's requirements. Otherwise, architectural modifications may have to be propagated to products of a product line, thereby increasing maintenance costs. Hence, it is important to understand which techniques better cope with PLA stability through evolution. This paper presents a comparative study to evaluate the positive and negative change impact on PLA designs based on components and aspects. The objective of the evaluation is to assess when aspects and components promote PLA stability in the presence of various types of change. To support a broader analysis, we compare the stability of the joint application of components and aspects to a PLA design against the isolated use of aspect-oriented, object-oriented, and component-based design techniques. The results show that the combination of aspects and components tends to promote superior PLA resilience than the other PLAs in most of the circumstances.

  • IC-09-24 pdf bib
    Robust estimation of camera motion using optical flow models.
    Jurandy Almeida, Rodrigo Minetto, Tiago A. Almeida, Ricardo da S. Torres, and Neucimar J. Leite.
    July 2009. In English, 13 pages plus errata.

    Abstract: The estimation of camera motion is one of the most important aspects for video processing, analysis, indexing, and retrieval. Most of existing techniques to estimate camera motion are based on optical flow methods in the uncompressed domain. However, to decode and to analyze a video sequence is extremely time-consuming. Since video data are usually available in MPEG-compressed form, it is desirable to directly process video material without decoding. In this paper, we present a novel approach for estimating camera motion in MPEG video sequences. Our technique relies on linear combinations of optical flow models. The proposed method first creates prototypes of optical flow, and then performs a linear decomposition on the MPEG motion vectors, which is used to estimate the camera parameters. Experiments on synthesized and real-world video clips show that our technique is more effective than the state-of-the-art approaches for estimating camera motion in MPEG video sequences.

  • IC-09-23 pdf bib
    Evaluation of a Tablet PC image annotation and retrieval tool in the parasitology domain.
    Nádia P. Kozievitch, Ricardo da Silva Torres, Thiago Falcão, Evandro Ramos, Felipe Andrade, Silmara Marques Allegretti, Marlene Tiduko Ueta, Rubens Riscala Madi, Uma Murthy, Eduard A. Fox, Yinlin Chen, and Eric Hallerman.
    July 2009. In English, 16 pages.

    Abstract: The project Deployment and Assessment of an Image Annotation and Retrieval Tool has the objective of specifying and implementing an application for image support annotation and search (based on a textual and a visual description) in the biodiversity domain. This technical report presents the activities related to the use of the tablet PC tool in the parasitology domain at Unicamp. The objective of this tool is to help the comparison of morphological characteristics among different species. The report is divided into activities accomplished, application setup and specific features, followed by experimental results and conclusion. Preliminary results showed that students regarded the tool as being very useful, contributing as an alternative learning approach.

  • IC-09-22 pdf bib
    An experimental scenario to investigate the remote control as artifact for interaction with television.
    Leonardo Cunha de Miranda, Elaine Cristina Saito Hayashi, and Maria Cecília Calani Baranauskas.
    June 2009. In English, 17 pages.

    Abstract: This technical report presents the results of an experiment whose objective was to observe users' interactions with television using the remote control. We believe that a culture mediated by the new media of Interactive Digital Television (iDTV) will depend directly on the artifact for physical interaction available to the user. In the work reported here we made an in loco observation of barriers related to the use of remote control in the television context and identified project requirements that should be considered in the design of new physical artifacts of interaction with iDTV.

  • IC-09-21 pdf bib
    Finding minimal bases in arbitrary spline spaces.
    Ana Paula Resende Malheiro and Jorge Stolfi.
    June 2009. In English, 21 pages.

    Abstract: In this work we describe a general algorithm to find a finite-element basis with minimum total support for an arbitrary spline space, given any basis for that same space. The running time is exponential on $ n $ in the worst case, but $ O (n m ^ 3) $ for many cases of practical interest, where $ n $ is the number of mesh cells and $ m $ is the dimension of the spline space.

  • IC-09-20 pdf bib
    Invisible work in standard bibliometric evaluation of computer science.
    Cleo Billa, Jacques Wainer, and Siome Goldenstein.
    June 2009. In English, 8 pages.

    Abstract: Science is a competitive business, and researchers from different fields are constantly compared in terms of funding and for promotion evaluations. This article analyzes the quantity of computer scientists' work which is not duly recognized when using Web of Science and / or Scopus bibliometrics. We randomly selected CS faculty from highly-ranked US Computer Science departments and determined that, on average, 67% of their published work is not accounted for within Web of Science searches and 44% is absent when searching with Scopus. We defined this parameter as the invisible work rate. We compared these figures to similar samples from Mathematics, Physics, and Electrical Engineering faculty. While CS and EE have significantly distinct publishing patterns as compared to Mathematics and Physics, the variance of the invisible work rate for CS is high, which suggests that different subareas of CS also have different publication practices - a possible indication that it will be difficult for computer scientists to agree on one bibliometric evaluation criterion.

  • IC-09-19 pdf bib
    $ K_r $-packing of $ P_4 $- tidy graphs.
    Vagner Pedrotti and Célia Picinin de Mello.
    May 2009. In English, 11 pages.

    Abstract: The $ K_r $-packing problem asks for the maximum number of pairwise vertex-disjoint clicks of size $ r $ in a graph, for a fixed integer $ r \ geq 2 $. This problem is NP-hard for general graphs when $ r \ geq 3 $, and even when restricted to chordal graphs. However, Guruswami et al. proposed a polynomial-time algorithm for cographs (when $ r $ is fixed). In this work we extended this algorithm to $ P_4 $-tidy graphs, keeping the same time complexity.

  • IC-09-18 pdf bib
    Revisiting the challenges of retrieving geographic information on the web.
    Lin Tzy Li and Ricardo da Silva Torres.
    May 2009. In Portuguese, 19 pages.

    Summary: There is a great deal of information on the Web about geographic entities and great interest in locating it on maps. However, search engines on the Web do not yet support searches that involve spatial relationships in a single tool, since in general the query is processed taking into account only the keywords used in the query. This article makes a brief review of the Geographic Information Retrieval (GIR) area and a re-reading of challenges and research opportunities in the area, based on the proposal of an architecture for Web searches involving spatial relationship between geographical entities and an initial implementation.

    Abstract: The geographic information is part of people's daily life. There is a huge amount of information on the Web about or related to geographic entities and people are interested in localizing them on maps. Nevertheless, the conventional Web search engines, which are keywords-driven mechanisms, do not support queries involving spatial relationships between geographic entities. This paper reviews the Geographic Information Retrieval (GIR) area and restates its research challenges and opportunities, based on a proposed architecture for executing Web queries involving spatial relationships and an initial implementation of that.

  • IC-09-17 pdf bib
    A study for the implementation of a component-based software product line.
    Ana Elisa de Campos Lobo and Cecília Mary Fischer Rubira.
    May 2009. In Portuguese, 29 pages.

    Summary: The software development activity has been facing increasing challenges in terms of reducing costs, effort and time to market, accompanied by an increase in the complexity and size of software products. To meet these demands, new approaches that favor the reuse of software artifacts have been proposed, such as that of Product Line Engineering. Product line engineering consists of designing, implementing and evolving a set of products with a high degree of similarity to each other, in a prescriptive way, from a set of basic artifacts. Companies that develop software products in a given application domain can achieve significant gains in terms of reduced effort and costs using the product line approach, developing several similar products at the same time, instead of focusing on the development of a single product at a time.

    Domain Engineering is one of the basic foundations for product line engineering. Domain Analysis, which is one of the activities of domain engineering, consists of identifying the objects and operations of a set of similar systems in a specific domain. In the literature, several domain engineering and product line methods can be found; however, most of them deal with the establishment of a product line from the beginning, and not from components and systems based on existing components. Today there are already several companies that use component-based development, which facilitates the establishment of a product line from existing artifacts.

    This report presents a study for the implementation of a product line in a software development company that develops products with a high degree of similarity to each other, and that already uses the component-based development paradigm. As an initial step towards the creation of a product line, a domain analysis was made, aiming to identify and model the similarities between the products developed by the company. The method chosen for domain analysis was FODA, and the tool used to support domain modeling was Odyssey. The objective of this study is to get familiar with methods and tools of domain analysis, seeking to identify possible problems and point out solutions for the construction of a software product line based on pre-existing components.

    The case study presented was carried out in a company in the area of ​​financial investments, in January 2006.

  • IC-09-16 pdf bib
    Prospecting requirements for online communication in social network systems.
    Elaine C. S. Hayashi, Leonelo Dell Anhol Almeida, Diego S. Melo-Solarte, Carla L. Rodrigues, M. Cecília C. Baranauskas, and M. Cecília Martins.
    April 2009. In English, 21 pages.

    Abstract: The Inclusive Social Network (ISN) Vila na Rede is being developed in a conjoined action with community leaders, end users and researchers from diverse fields of knowledge. The features of this ISN are being designed to support the needs of these social groups in a way that it makes sense to them and that it is part of their reality. In order to better understand this reality, the 6th Semio-Participatory Workshop of the e-Citizenship Project: "System and Methods for the Constitution of a Culture mediated by Information and Communication Technology" was held and one of its activities was concerned with the investigation of communication mechanisms for social network systems. This technical report presents how the workshop was conducted, the data collected from the activities and the analysis of the data. As a result, first requirements for online conversation on including social networks are presented.

  • IC-09-15 pdf bib
    A participatory practice for designing including social networks in the e-Citizenship Project.
    Leonardo Cunha de Miranda, Leonelo Dell Anhol Almeida, Elaine Cristina Saito Hayashi, Vânia Paula de Almeida Neris, and Maria Cecília Calani Baranauskas.
    April 2009. In English, 24 pages.

    Abstract: e-Cidadania is a research Project inspired by one of the current grand challenges of Computer Science research in Brazil for the next years: the Participative and Universal Access to Knowledge for the Brazilian Citizen. This Project investigates the potentialities of including social network systems as mediators in the constitution of a digital culture among those digitally illiterate. This work builds on Participatory Design (PD) techniques adapted to an including setting to conduct the 3rd Semio-Participatory Workshop of the e-Citizenship Project and to analyze its achievements. The Workshop aimed at the design of user interface elements for an inclusive social network system. This research report illustrates the participatory practice adapted to an inclusive scenario, presents the main achievements of the Workshop and discusses results that inform the UI design.

  • IC-09-14 pdf bib
    Launching Vila na Rede: First results of e-Cidadania Project.
    Elaine C. S. Hayashi, Heiko Hornung, and M. Cecília C. Baranauskas.
    April 2009. In English, 22 pages.

    Abstract: Vila na Rede is an Inclusive Social Network built for and with Brazilian citizens. It was conceived after the research and analysis that took place throughout the first three Semio-Participatory Workshops conducted at Vila União, a neighborhood of low income families located in Campinas, SP. These workshops, as well as the Vila na Rede itself, are part of the e-Citizenship Project, which aims to study and propose solutions to the challenges of interaction and user interface design on systems related to the exercise of citizenship, contributing to the promotion of a digital culture. This Technical Report describes the activities from e-Cidadania's 4th Workshop, since its preparation until the examination of the collected results. The 4th Workshop had as main objective the launch of Vila na Rede system.

  • IC-09-13 pdf bib
    A first study on characterizing the energy consumption of software transactional memory.
    Alexandro Baldassin, Felipe Klein, Paulo Centoducatte, Guido Araujo, and Rodolfo Azevedo.
    April 2009. In English, 10 pages.

    Abstract: The well-known drawbacks imposed by lock-based synchronization have forced researchers to devise new alternatives for concurrent execution, of which transactional memory is a promising one. Extensive research has been carried out on Software Transaction Memory (STM), most of all concentrated on program performance, leaving unattended other metrics of great importance like energy consumption. This paper presents a systematic methodology to characterize a class of STMs that implement a common set of API calls. We thoroughly evaluate the impact on energy consumption due to STM by quantifying the energy costs of the primitives involved in an optimistic time-based STM implementation. This work is a first study towards a better understanding of the energy consumption behavior of STM systems, and could prompt STM designers to research new optimizations in this area, paving the way for an energy-aware transactional memory.

  • IC-09-12 pdf bib
    Robust estimation of camera motion using local invariant features.
    Jurandy Almeida, Rodrigo Minetto, Tiago A. Almeida, Ricardo da S. Torres, and Neucimar J. Leite.
    April 2009. In English, 9 pages.

    Abstract: Most of existing techniques to estimate camera motion are based on analysis of the optical flow. However, the estimation of the optical flow supports only a limited amount of scene motion. In this report, we present a novel approach to estimate camera motion based on analysis of local invariant features. Such features are robust across a substantial range of affine distortion. Experiments on synthesized video clips with a fully controlled environment show that our technique is more effective than the optical flow-based approaches for estimating camera motion with a large amount of scene motion.

  • IC-09-11 pdf bib
    Design, verification and implementation of exception control flows for product line architectures.
    Patrick H. S. Brito, Nelio Cacho, Alessandro Garcia, Cecília M. F. Rubira, and Rogério de Lemos.
    March 2009. In English, 21 pages.

    Abstract: Separation of concerns is one of the overarching goals of exception handling in order to keep separate normal and exceptional behavior of a software system. In the context of software product lines, this separation of concerns is important for designing software variability related to different exception handling strategies. This technical report presents a tool-supported solution for designing, verifying and implementing exceptional behavior variability into product lines architectures. Our solution is based on: (i) the adoption of an exception handling model that supports explicit exception control flows and pluggable handlers; (ii) a strategy for designing and automatically checking the selection of variation points related to exception control flows and handlers; and (iii) an aspect-oriented implementation for exceptional behavior variability. We evaluate qualitatively and quantitatively our solution through a case study targeting a real mobile application.

  • IC-09-10 pdf bib
    Verifying architectural variabilities in software fault tolerance techniques.
    Patrick H. S. Brito, Rogério de Lemos, and Cecília M. F. Rubira.
    March 2009. In English, 15 pages.

    Abstract: This technical report considers the representation of different software fault tolerance techniques as a product line architecture (PLA) for promoting the reuse of software artefacts, such as formal specifications and verification. The proposed PLA enables to specify a series of closely related applications in terms of a single architecture, which is obtained by identifying variation points associated with design decisions regarding software fault tolerance. These decisions are used to choose the appropriate technique depending on the features selected for the instance, eg, the number of redundant resources, or the type of adjudicator. The proposed approach also comprises the formalization of the PLA, using B-Method and CSP, for systematising the verification of fault-tolerant software systems at the architectural level. The properties verified cover two complementary contexts: the selection of the correct architectural variabilities for instantiating the PLA, and also the properties of the chosen fault tolerance techniques.

  • IC-09-09 pdf bib
    Hybrid Lagrangian algorithms for optimal vertex separators.
    Victor F. Cavalcante and Cid C. de Souza.
    March 2009. In English, 39 pages.

    Abstract: In this paper we propose a Lagrangian relaxation framework to solve the vertex separator problem (VSP). This framework is based on the development of relax-and-cut algorithms which embed the separation of valid inequalities for the VSP discussed in [3] in the subgradient method. These relax-and-cut algorithms are then used as a preprocessing phase in a hybrid algorithm which combines them with branch-and-cut algorithms proposed in [12]. This is done basically by feeding the branch-and-cut algorithms not only with the primal bound but also the cuts separated during the preprocessing phase. Computational results obtained with benchmarks from the literature showed that the hybrid algorithm developed here outperforms the best exact algorithm available for the VSP to date.

  • IC-09-08 pdf bib
    Qualitative analysis and comparison of plagiarism-detection systems in student programs.
    Alan Bustos Kleiman and Tomasz Kowaltowski.
    March 2009. In English, 8 pages.

    Summary: Plagiarism in student assignments is a problem that has been increasing over time and educational institutions have considerable work to address it. In this work, we examine the problem from the point of view of plagiarism in programming tasks. We implemented some of the described algorithms in order to carry out a direct and qualitative comparison, with emphasis on the program pre-processing phase. Our main conclusion is that pre-processing can be even more important than the comparison algorithm itself, and we point out new directions for future work.

    Abstract: Plagiarism in student coursework has become increasingly common and significant effort has been undertaken to face this problem. In this work we focus on the plagiarism in computer programs. We implemented some of the algorithms we discuss so that we could perform a direct and qualitative comparison, with emphasis on the program pre-processing phase. Our main conclusion is that pre-processing may be more important than the comparison algorithm itself and we point to new directions for future work.

  • IC-09-07 pdf bib
    Exponentially more succinct test suites.
    Adilson Luiz Bonifácio, Arnaldo Vieira Moura, and Adenilso da Silva Simão.
    March 2009. In English, 26 pages.

    Abstract: We present a generalized test case generation method, or G-method, extending some previous work. Although inspired on the W-method, the G-method, in contrast, allows for test case suite generation even in the absence of characterization sets for the specification models. Instead, the G-method relies on knowledge about the index of certain equivalences induced in the implementation models. We show that the W-method can be derived from the G-method as a particular case. Moreover, we discuss some naturally occurring infinite classes of FSM models over which the G-method generates test suites that are exponentially more compact than those produced by the W-method. Proofs for important results are presented in detail.

  • IC-09-06 pdf bib
    Matching signatures and Pfaffian graphs.
    Alberto Alexandre Assis Miranda and Cláudio Leonardo Lucchesi.
    February 2009. In English, 13 pages.

    Abstract: We prove that every 4-Pfaffian that is not Pfaffian essentially has a unique signature matrix. We also give a simple composition Theorem of $ 2r $-Pfaffian graphs from $ r $ Pfaffian spanning subgraphs. We apply these results and exhibit a graph that is 6-Pfaffian but not 4-Pfaffian. This is a counter-example to a conjecture of Norine, which states that if a graph $ G $ is $ k $-Pfaffian but not $ (k-1) $-Pfaffian then $ k $ is a power of four.

  • IC-09-05 pdf bib
    Recovering Brazilian indigenous cultural heritage using new information and communication technologies.
    Maria Beatriz Felgar de Toledo.
    February 2009. In English, 25 pages.

    Abstract: The objective of this paper is to discuss the new demands imposed on museums, the possibilities to achieve them using new Information and Communication Technologies (ICTs) and to propose a platform to meet these requirements. The platform will provide services to the external public, the museum staff and researchers. The artifacts to be collected and interpreted will belong to Brazilian indigenous culture.

  • IC-09-04 pdf bib
    MultiS: A gesture based interaction model for iDTV.
    Leonardo Cunha de Miranda, Heiko Horst Hornung, and Maria Cecília Calani Baranauskas.
    February 2009. In English, 14 pages.

    Abstract: The existence of digital artefacts commonly used to interact with today's television systems does not guarantee that those devices are adequate to mediate the use of Interactive Digital Television (iDTV) and its new types of applications. This is especially true in the context of developing countries where iDTV is a promise to cope with the digital divide. This technical report reviews the state of the art of physical artefacts of interaction with iDTV. In addition it presents a gesture based interaction model for iDTV that could inform the design of a new interaction language based on gesture and physical artefacts of interaction with iDTV.

  • IC-09-03 pdf bib
    Creating the HasCASL library.
    Glauber M. Cabral and Arnaldo V. Moura.
    January 2009. In English, 68 pages.

    Abstract: The effective use of a speci fi cation language depends on the availability of prede fi ned speci fi cations. Although the CASL speci fi cation has such a library, that is not the case of the HasCASL language, one of the CASL's extensions. Here we start to specify such a library to the HasCASL language, based on the Prelude library of the Haskel l programming language. When completed this approach would create a library that, after re fi nements, should lead to reusable speci fi cations for real Haskel l programs. This technical report discusses the speci fi cation and veri fi cation of a kernel library to the HasCASL language.

  • IC-09-02 pdf bib
    Experimental evaluation in computer science II: A quantitative study, 12 years later.
    Jacques Wainer, Claudia G. Novoa Barsottini, Danilo Lacerda, and Leandro Rodrigues Magalhaes de Marco.
    January 2009. In English, 17 pages.

    Abstract: This paper repeats part of the analysis performed in the 1995 paper `` Experimental evaluation in computer science: A quantitative study '' by Tichy and collaborators, for 147 papers randomly selected from the ACM, published in the year 2005. The papers published in 2005 are classified in the following way: 4% theory, 17% empirical, 4.7% hypothesis testing, 3.4% other, and 70% design and modeling (using the 1995 paper categories). Within the design and modeling class, 33% of the papers have no evaluation. The numbers of the 2005 sample are very similar to the original figures for the 1995 sample, which shows that Computer Science research has not increased significantly its empirical or experimental component.

  • IC-09-01 pdf bib
    Using latin squares to color split graphs.
    Sheila Morais de Almeida, Célia Picinin de Mello, and Aurora Morgana.
    January 2009. In English, 9 pages.

    Abstract: An edge-coloring of a graph is an assignment of colors to its edges such that no adjacent edges have the same color. THE split graph is a graph whose vertex set admits a partition into a stable set and a click. Split graphs have been introduced by Földes and Hammer and it is a well-studied class of graphs. However, the problem of deciding the chromatic index of any split graph remains unsolved. Chen, Fu, and Ko use a latin square to color any split graph with odd maximum degree. In this work, we also use a latin square to color some split graphs with even maximum degree and we show that these graphs are Class 1.


  • 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