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, E.R.M. Madeira, C.M.B. Medeiros, and W.M.P. 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 (e.g., 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, e.g., 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
    Um sistema de ligação dinâmica independente de arquitetura baseado em adl.
    Rafael Auler, Paulo Cesar Centoducatte, and Alexandro Baldassin.
    November 2009. In Portuguese, 34 pages.

    Resumo: Diferentes instruções são implementadas em processadores com conjunto de instruções específico para a aplicação (ASIPs - Application Specific Instruction-Set Processors), motivados pela necessidade de especializar o processador para uma determinada carga de software em uma plataforma embarcada. Para que o projeto seja concluído em tempo viável, é importante reduzir os esforços necessários para construir ferramentas de desenvolvimento de software e simuladores para a nova plataforma. Para isso, simuladores e demais ferramentas podem ser automaticamente sintetizados baseados na descrição da arquitetura do processador. Neste relatório técnico discutimos o projeto de um sistema completo de ligação dinâmica independente de arquitetura alvo, compreendendo a capacidade de geração automática de ligadores: um ligador de tempo de compilação e um carregador para ligação em tempo de execução. O sistema, entretanto, é dependente de arquivo objeto e adota o formato ELF. O carregador utilizado foi especificamente construído para este projeto de modo que não dependemos do carregador da biblioteca glibc. O objetivo principal é o fácil redirecionamento para aplicação em um processador alvo bem como às suas respectivas regras da interface binária da aplicação (ABI - Application Binary Interface). Tais informações dependentes do alvo são extraídas automaticamente de um modelo descrito em uma linguagem de descrição de arquiteturas (ADL - Architecture Description Language). O estudo foca a implementação na ADL ArchC, e testes de validação para a arquitetura ARM são apresentados, acompanhados de uma breve análise dos resultados experimentais para o simulador.

    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 in the ADL ArchC, and validation tests for the ARM architecture are presented.

  • IC-09-42 pdf bib
    Conjuntos dominantes em grids.
    Izumi Oniki Chiquito and C. N. Campos.
    November 2009. In Portuguese, 22 pages.

    Resumo: Sejam $P_{m}$ e $P_{n}$ dois caminhos de $m$ e $n$ vértices, respectivamente. Um grid $G_{m
         \times  n}$ é o grafo correspondente ao produto cartesiano $P_{m}  \times P_{n}$. Neste trabalho, tratamos de conjuntos dominantes em grids. Um conjunto dominante de um grafo $G$ é um subconjunto $D$ de seu conjunto de vértices, tal que todo vértice de $G$ ou pertence a $D$, ou é adjacente a um elemento de $D$. Sabe-se que a determinação do número de dominação, isto é, da cardinalidade de um menor conjunto dominante possível, é um problema NP-difícil para grafos arbitrários. Entretanto, esse número é conhecido para a subclasse dos grids nos casos em que $1 \leq m \leq 6$. Neste texto, fornecemos um limite superior para o número de dominação de $G_{m \times n}$, com $7 \leq m \leq 10$, bem como um algoritmo polinomial para obtenção de conjuntos dominantes cujos tamanhos atingem esse limite. Chang, Clark e Hare obtiveram limitantes similares, mas os resultados aqui apresentados foram desenvolvidos independentemente do trabalho destes autores.

  • 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-Cidadania 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-Cidadania 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 interval arithmetic 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 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 conform 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 e 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
    Anais do V Workshop de Teses, Dissertações e Trabalhos de Iniciação Científica em Andamento 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.
    Setembro 2009. Partly in English, partly in Portuguese, 232 pages.

    Resumo: Este relatório técnico contém os resumos de 76 trabalhos apresentados no V Workshop de Teses, Dissertações e Trabalhos de Iniciação Científica em Andamento do Instituto de Computação da UNICAMP (WTD-IC-UNICAMP 2009).

    No ano de 2009, o Workshop fez parte das comemorações dos "40 anos de Computação da UNICAMP", quando o primeiro curso de Bacharelado em Ciência da Computação do Brasil foi criado pela Unicamp em 18 de março de 1969. Nesta edição especial tivemos, além das tradicionais apresentações orais, uma feira de pôsters, com o intuito de permitir um maior número de participações de alunos.

    O Workshop, realizado de 29 de setembro a 1 de outubro de 2009, permitiu que doutorandos, mestrandos e alunos de graduação de iniciação científica do Instituto apresentassem os principais aspectos de suas pesquisas.

    Cada resumo de trabalho de doutorado, de mestrado ou de iniciação científica, corresponde a uma apresentação oral ou uma apresentação de pôster, sendo o texto limitado a 4 páginas. A publicação dos resumos sob forma de um relatório técnico tem por objetivo (i) divulgar os trabalhos em andamento no IC e (ii) registrar de forma sucinta o estado da arte da pesquisa do IC no ano de 2009.

  • IC-09-35 pdf bib
    Edge-coloring of split graphs.
    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$, where $\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. A split graph is a graph whose vertex set admits a partition into a stable set and a clique. 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 theorems.
    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
    Abortos falsos em sistemas de memória transacional em software.
    Daniel Nicácio and Guido Araújo.
    September 2009. In Portuguese, 22 pages.

    Resumo: Memória transacional (MT) continua a ser a abordagem mais promissora para substituir locks em programação concorrente, mas sistemas de MT em software (MTS) ainda não possuem desempenho satisfatório quando comparados a implementações utilizando locks bem refinados. Sabe-se que a operação crítica em sistemas de MT é garantir a atomicidade e o isolamento das threads que estejam executando concorrentemente. Essa tarefa é conhecida como a validação dos conjuntos de leitura/escrita. Na tentativa de realizar esse processo o mais rápido possível, sistemas de MTS costumam utilizar uma tabela de posse para realizar a detecção de conflitos, mas essa abordagem gera ocorrência de falsos positivos, os quais resultam em abortos falsos. Este trabalho mostra o verdadeiro impacto dos abortos falsos e como sua relevância aumenta à medida que o número de threads concorrentes também aumenta, mostrando que este fator é essencial para sistemas de MTS. Nós propomos duas diferentes técnicas para evitar abortos falsos e conseqüentemente melhorar o desempenho de MTS. A primeira é uma lista de colisão anexada à já existente tabela hash. A segunda è uma técnica completamente nova e eficiente para detectar conflitos entre transações. Esta nova técnica faz uso de tecnologia SSE para detectar conflitos e substitui a normalmente usada tabela hash. Devido ao seu esquema de mapeamento de memória, esta técnica consegue evitar a ocorrência de falsos positivos. Com uma detecção de colisão rápida e livre de falsos conflitos, nós conseguimos significativa melhora de desempenho em alguns programas do benchmark STAMP. O speedup obtido foi de ate 1,63x. Nós também mostramos que os speedups ficam cada vez maiores com o aumento do número de threads paralelas. Por fim, baseado nos resultados obtidos, nós caracterizamos os programas que foram mais beneficiados pelas duas técnicas.

    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 specification TIOA 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 conform 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
    Jogos com propósito e construção de conhecimento em design.
    Roberto Romani and Maria Cecília C. Baranauskas.
    August 2009. In Portuguese, 11 pages.

    Resumo: O design de sistemas “para todos” não é uma tarefa trivial para os designers de interface de usuário (IU), uma vez que inúmeros aspectos devem ser considerados para que TICs (Tecnologias de Informação e Comunicação) façam sentido e possam ser usados pelo cidadão. Estender o conceito de design centrado no usuário de forma que parte significativa dos potenciais usuários pudesse opinar sobre o design das interfaces, implicaria na participação de centenas ou milhares de pessoas nesse processo. Este trabalho propõe o uso da competência humana para auxiliar no desenvolvimento de interfaces acessíveis a todos por meio de Games With A Purpose (GWAP). Propomos envolver o usuário na construção de conhecimento, tornando-o co-participante no processo de design. Análises iniciais sugerem o potencial do uso de jogos com propósito em auxiliar designers de IU em escolhas informadas sobre elementos de design de sistemas que devem ser para todos.

    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 analyses 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: A 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 their $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 M.F. 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 cliques 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
    Revisitando os desafios da recuperação de informação geográfica na web.
    Lin Tzy Li and Ricardo da Silva Torres.
    May 2009. In Portuguese, 19 pages.

    Resumo: Há uma grande quantidade de informação na Web sobre entidades geográficas e grande interesse em localizá-la em mapas. Entretanto, os mecanismos de busca na Web ainda não suportam em uma única ferramenta buscas que envolvam relações espaciais, pois em geral a consulta é processada levando-se em conta apenas as palavras-chaves usadas na consulta. Este artigo faz uma breve revisão da área de Recuperação de Informação Geográfica (GIR) e uma releitura de desafios e oportunidades de pesquisa da área a partir da proposta de uma arquitetura para buscas Web envolvendo relacionamento espacial entre entidades geográficas e uma implementação inicial dela.

    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 revises 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
    Um estudo para implantação de linha de produto de software baseada em componentes.
    Ana Elisa de Campos Lobo and Cecília Mary Fischer Rubira.
    May 2009. In Portuguese, 29 pages.

    Resumo: A atividade de desenvolvimento de software vem enfrentando crescentes desafios em termos de diminuição de custos, esforço e tempo de chegada ao mercado, acompanhados do aumento da complexidade e do tamanho dos produtos de software. Para atender a estas demandas, novos enfoques que favoreçam o reuso de artefatos de software têm sido propostos, tais como o de Engenharia de Linha de Produto. A engenharia de linha de produto consiste em projetar, implementar e evoluir um conjunto de produtos com alto grau de similaridade entre si, de forma prescritiva, a partir de um conjunto de artefatos básicos. Empresas que desenvolvem produtos de software em um determinado domínio de aplicação podem obter ganhos significativos em termos de redução de esforço e custos utilizando o enfoque de linha de produto, desenvolvendo vários produtos similares ao mesmo tempo, ao invés de focar no desenvolvimento de um único produto por vez.

    A Engenharia de Domínio é um dos fundamentos básicos para a engenharia de linha de produto. A Análise de Domínio, que é uma das atividades da engenharia de domínio, consiste na identificação dos objetos e operações de um conjunto de sistemas similares em um domínio específico. Na literatura podem ser encontrados vários métodos de engenharia de domínio e de linha de produto; entretanto, a maioria deles tratam do estabelecimento de uma linha de produtos desde o seu início, e não a partir de componentes e sistemas baseados em componentes já existentes. Hoje já existem várias empresas que usam desenvolvimento baseado em componentes, o que facilita o estabelecimento de uma linha de produtos a partir de artefatos já existentes.

    Este relatório apresenta um estudo para a implantação de linha de produto em uma empresa de desenvolvimento de software que desenvolve produtos com alto grau de similaridade entre si, e que já utiliza o paradigma de desenvolvimento baseado em componentes. Como passo inicial para a criação de uma linha de produto foi feita uma análise de domínio, visando identificar e modelar as similaridades existentes entre os produtos desenvolvidos pela empresa. O método escolhido para a análise de domínio foi o FODA, e a ferramenta utilizada para suporte à modelagem do domínio foi o Odyssey. O objetivo deste estudo é obter familiaridade com métodos e ferramentas de análise de domínio, buscando identificar possíveis problemas e apontar soluções para a construção de uma linha de produto de software baseada em componentes pré-existentes.

    O estudo de caso apresentado foi realizado em uma empresa da área de aplicações financeiras, em Janeiro de 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-Cidadania 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 inclusive social networks are presented.

  • IC-09-15 pdf bib
    A participatory practice for designing inclusive social networks in the e-Cidadania 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 inclusive 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 inclusive setting to conduct the 3rd Semio-Participatory Workshop of the e-Cidadania 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-Cidadania 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 behaviour 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 behaviour 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 verifying the selection of variation points related to exception control flows and handlers; and (iii) an aspect-oriented implementation for exceptional behaviour 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, e.g, the number of redundant resources, or the type of adjudicator. The proposed approach also comprises the formalisation 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.

    Resumo: Plágio em tarefas de alunos é um problema que vem aumentando ao longo do tempo e instituições de ensino têm trabalho considerável para enfrentá-lo. Neste trabalho, examinamos o problema do ponto de vista de plágio em tarefas de programação. Implementamos alguns dos algoritmos descritos com a finalidade de efetuar uma comparação direta e qualitativa, com ênfase na fase de pré-processamento de programas. Nossa conclusão principal é que o pré-processamento pode ser até mais importante do que o algoritmo de comparação em si, e apontamos novas direções para trabalhos futuros.

    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 a HasCASL library.
    Glauber M. Cabral and Arnaldo V. Moura.
    January 2009. In English, 68 pages.

    Abstract: The effective use of a specification language depends on the availability of predefined specifications. Although the CASL specification 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 refinements, should lead to reusable specifications for real Haskel l programs. This technical report discusses the specification and verification 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. A split graph is a graph whose vertex set admits a partition into a stable set and a clique. 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 :: Universidade Estadual de Campinas
    Caixa Postal 6176 • Av. Albert Einstein, 1251 - Cidade Universitária • CEP 13083-970 • Campinas/SP - Brasil • Fone: [19] 3521-5838