OpenRaiser/Intern-Atlas huggingface dataset:
Vérification d'assemblages de composants logiciels : Application aux modèles de composants UML2.0 et Ugatze
Venue: arXiv cs.SE 2012
Year: 2012

The component approach aims for the reuse by a coherent and easy components assembly. But obtaining a coherent components assembly is not an easy exercise. To achieve this, we advocate a contractual approach distinguishing different syntactic, structural, semantic, synchronization and service quality contracts. We have successfully applied this approach on two models of semi-formal contractual components: UML2.0 and Ugatze. Indeed, we propose two approaches: VerifComponentUML2.0 and VerifComponentUgatze. The VerifComponentUML2.0 approach aims the verification of syntactic, structural, synchronization and quality service contracts on a UML2.0 component assembly through two formal component models Acme/Armani and Wright. VerifComponentUML2.0 has two tools: Wr2fdr and Wright2Ada. The tool Wr2fdr allows translating Wright expression to CSP contracts in order to verify synchronization using the model checker FDR. It is a IDM tool Wright2Ada which allow is transforming Wright code to Ada, in order to open UML2.0 on static analysis and dynamic tools associated with Ada. VerifComponentUgatze approach provides a frame allowing to check syntactic and structural contracts of an Ugatze component assembly through Acme/Armani.
Information and Estimation over Binomial and Negative Binomial Models
Venue: arXiv cs.IT 2012
Year: 2012

In recent years, a number of results have been developed which connect information measures and estimation measures under various models, including, predominently, Gaussian and Poisson models. More recent results due to Taborda and Perez-Cruz relate the relative entropy to certain mismatched estimation errors in the context of binomial and negative binomial models, where, unlike in the case of Gaussian and Poisson models, the conditional mean estimates concern models of different parameters than those of the original model. In this note, a different set of results in simple forms are developed for binomial and negative binomial models, where the conditional mean estimates are produced through the original models. The new results are more consistent with existing results for Gaussian and Poisson models.
Completeness of algebraic CPS simulations
Venue: arXiv cs.LO 2012
Year: 2012

The algebraic lambda calculus and the linear algebraic lambda calculus are two extensions of the classical lambda calculus with linear combinations of terms. They arise independently in distinct contexts: the former is a fragment of the differential lambda calculus, the latter is a candidate lambda calculus for quantum computation. They differ in the handling of application arguments and algebraic rules. The two languages can simulate each other using an algebraic extension of the well-known call-by-value and call-by-name CPS translations. These simulations are sound, in that they preserve reductions. In this paper, we prove that the simulations are actually complete, strengthening the connection between the two languages.
Probabilistic Monads, Domains and Classical Information
Venue: arXiv cs.PL 2012
Year: 2012

Shannon's classical information theory uses probability theory to analyze channels as mechanisms for information flow. In this paper, we generalize results of Martin, Allwein and Moskowitz for binary channels to show how some more modern tools - probabilistic monads and domain theory in particular - can be used to model classical channels. As initiated Martin, et al., the point of departure is to consider the family of channels with fixed inputs and outputs, rather than trying to analyze channels one at a time. The results show that domain theory has a role to play in the capacity of channels; in particular, the (n x n)-stochastic matrices, which are the classical channels having the same sized input as output, admit a quotient compact ordered space which is a domain, and the capacity map factors through this quotient via a Scott-continuous map that measures the quotient domain. We also comment on how some of our results relate to recent discoveries about quantum channels and free affine monoids.
The power of linear programming for valued CSPs: a constructive characterization
Venue: arXiv cs.CC 2012
Year: 2012

A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum. We study which classes of finite-valued languages can be solved exactly by the basic linear programming relaxation (BLP). Thapper and Zivny showed [20] that if BLP solves the language then the language admits a binary commutative fractional polymorphism. We prove that the converse is also true. This leads to a necessary and a sufficient condition which can be checked in polynomial time for a given language. In contrast, the previous necessary and sufficient condition due to [20] involved infinitely many inequalities. More recently, Thapper and Zivny [21] showed (using, in particular, a technique introduced in this paper) that core languages that do not satisfy our condition are NP-hard. Taken together, these results imply that a finite-valued language can either be solved using Linear Programming or is NP-hard.
Multi-Dimensional Nonsystematic Reed-Solomon Codes
Venue: arXiv cs.IT 2012
Year: 2012

This paper proposes a new class of multi-dimensional nonsystematic Reed-Solomon codes that are constructed based on the multi-dimensional Fourier transform over a finite field. The proposed codes are the extension of the nonsystematic Reed-Solomon codes to multi-dimension. This paper also discusses the performance of the multi-dimensional nonsystematic Reed-Solomon codes.
Privacy, Trust and Identity in Pervasive Computing: A Review of Technical Challenges and Future Research Directions
Venue: arXiv cs.CR 2012
Year: 2012

Developments in pervasive computing introduced a new world of computing where networked processors embedded and distributed in everyday objects communicating with each other over wireless links. Computers in such environments work in the background while establishing connections among them dynamically and hence will be less visible and intrusive. Such a vision raises questions about how to manage issues like privacy, trust and identity in those environments. In this paper, we review the technical challenges that face pervasive computing environments in relation to each of these issues. We then present a number of security related considerations and use them as a basis for comparison between pervasive and traditional computing. We will argue that these considerations pose particular concerns and challenges to the design and implementation of pervasive environments which are different to those usually found in traditional computing environments. To address these concerns and challenges, further research is needed. We will present a number of directions and topics for possible future research with respect to each of the three issues.
Robots-Assisted Redeployment in Wireless Sensor Networks
Venue: arXiv cs.NI 2012
Year: 2012

Connectivity and coverage are two crucial problems for wireless sensor networks. Several studies have focused on proposing solutions for improving and adjusting the initial deployment of a wireless sensor network to meet these two criteria. In our work, we propose a new hierarchical architecture for sensor networks that facilitates the gathering of redundancy information of the topology. Several mobile robots must then relocate, in an optimized way, redundant sensors to achieve optimal connectivity and coverage of the network. Mobile robots have to cooperate and coordinate their movement. A performance evaluation is conducted to study the trade-off between the number of required robots and its impact on the rate of network connectivity and coverage.
Diversifying Top-K Results
Venue: arXiv cs.DB 2012
Year: 2012

Top-k query processing finds a list of k results that have largest scores w.r.t the user given query, with the assumption that all the k results are independent to each other. In practice, some of the top-k results returned can be very similar to each other. As a result some of the top-k results returned are redundant. In the literature, diversified top-k search has been studied to return k results that take both score and diversity into consideration. Most existing solutions on diversified top-k search assume that scores of all the search results are given, and some works solve the diversity problem on a specific problem and can hardly be extended to general cases. In this paper, we study the diversified top-k search problem. We define a general diversified top-k search problem that only considers the similarity of the search results themselves. We propose a framework, such that most existing solutions for top-k query processing can be extended easily to handle diversified top-k search, by simply applying three new functions, a sufficient stop condition sufficient(), a necessary stop condition necessary(), and an algorithm for diversified top-k search on the current set of generated results, div-search-current(). We propose three new algorithms, namely, div-astar, div-dp, and div-cut to solve the div-search-current() problem. div-astar is an A* based algorithm, div-dp is an algorithm that decomposes the results into components which are searched using div-astar independently and combined using dynamic programming. div-cut further decomposes the current set of generated results using cut points and combines the results using sophisticated operations. We conducted extensive performance studies using two real datasets, enwiki and reuters. Our div-cut algorithm finds the optimal solution for diversified top-k search problem in seconds even for k as large as 2,000.
Answering Queries using Views over Probabilistic XML: Complexity and Tractability
Venue: arXiv cs.DB 2012
Year: 2012

We study the complexity of query answering using views in a probabilistic XML setting, identifying large classes of XPath queries -- with child and descendant navigation and predicates -- for which there are efficient (PTime) algorithms. We consider this problem under the two possible semantics for XML query results: with persistent node identifiers and in their absence. Accordingly, we consider rewritings that can exploit a single view, by means of compensation, and rewritings that can use multiple views, by means of intersection. Since in a probabilistic setting queries return answers with probabilities, the problem of rewriting goes beyond the classic one of retrieving XML answers from views. For both semantics of XML queries, we show that, even when XML answers can be retrieved from views, their probabilities may not be computable. For rewritings that use only compensation, we describe a PTime decision procedure, based on easily verifiable criteria that distinguish between the feasible cases -- when probabilistic XML results are computable -- and the unfeasible ones. For rewritings that can use multiple views, with compensation and intersection, we identify the most permissive conditions that make probabilistic rewriting feasible, and we describe an algorithm that is sound in general, and becomes complete under fairly permissive restrictions, running in PTime modulo worst-case exponential time equivalence tests. This is the best we can hope for since intersection makes query equivalence intractable already over deterministic data. Our algorithm runs in PTime whenever deterministic rewritings can be found in PTime.
Probabilistic Databases with MarkoViews
Venue: arXiv cs.DB 2012
Year: 2012

Most of the work on query evaluation in probabilistic databases has focused on the simple tuple-independent data model, where tuples are independent random events. Several efficient query evaluation techniques exists in this setting, such as safe plans, algorithms based on OBDDs, tree-decomposition and a variety of approximation algorithms. However, complex data analytics tasks often require complex correlations, and query evaluation then is significantly more expensive, or more restrictive. In this paper, we propose MVDB as a framework both for representing complex correlations and for efficient query evaluation. An MVDB specifies correlations by views, called MarkoViews, on the probabilistic relations and declaring the weights of the view's outputs. An MVDB is a (very large) Markov Logic Network. We make two sets of contributions. First, we show that query evaluation on an MVDB is equivalent to evaluating a Union of Conjunctive Query(UCQ) over a tuple-independent database. The translation is exact (thus allowing the techniques developed for tuple independent databases to be carried over to MVDB), yet it is novel and quite non-obvious (some resulting probabilities may be negative!). This translation in itself though may not lead to much gain since the translated query gets complicated as we try to capture more correlations. Our second contribution is to propose a new query evaluation strategy that exploits offline compilation to speed up online query evaluation. Here we utilize and extend our prior work on compilation of UCQ. We validate experimentally our techniques on a large probabilistic database with MarkoViews inferred from the DBLP data.
Optimization of Analytic Window Functions
Venue: arXiv cs.DB 2012
Year: 2012

Analytic functions represent the state-of-the-art way of performing complex data analysis within a single SQL statement. In particular, an important class of analytic functions that has been frequently used in commercial systems to support OLAP and decision support applications is the class of window functions. A window function returns for each input tuple a value derived from applying a function over a window of neighboring tuples. However, existing window function evaluation approaches are based on a naive sorting scheme. In this paper, we study the problem of optimizing the evaluation of window functions. We propose several efficient techniques, and identify optimization opportunities that allow us to optimize the evaluation of a set of window functions. We have integrated our scheme into PostgreSQL. Our comprehensive experimental study on the TPC-DS datasets as well as synthetic datasets and queries demonstrate significant speedup over existing approaches.
Compacting Transactional Data in Hybrid OLTP & OLAP Databases
Venue: arXiv cs.DB 2012
Year: 2012

Growing main memory sizes have facilitated database management systems that keep the entire database in main memory. The drastic performance improvements that came along with these in-memory systems have made it possible to reunite the two areas of online transaction processing (OLTP) and online analytical processing (OLAP): An emerging class of hybrid OLTP and OLAP database systems allows to process analytical queries directly on the transactional data. By offering arbitrarily current snapshots of the transactional data for OLAP, these systems enable real-time business intelligence. Despite memory sizes of several Terabytes in a single commodity server, RAM is still a precious resource: Since free memory can be used for intermediate results in query processing, the amount of memory determines query performance to a large extent. Consequently, we propose the compaction of memory-resident databases. Compaction consists of two tasks: First, separating the mutable working set from the immutable "frozen" data. Second, compressing the immutable data and optimizing it for efficient, memory-consumption-friendly snapshotting. Our approach reorganizes and compresses transactional data online and yet hardly affects the mission-critical OLTP throughput. This is achieved by unburdening the OLTP threads from all additional processing and performing these tasks asynchronously.
ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases
Venue: arXiv cs.DB 2012
Year: 2012

We study the problem of local alignment, which is finding pairs of similar subsequences with gaps. The problem exists in biosequence databases. BLAST is a typical software for finding local alignment based on heuristic, but could miss results. Using the Smith-Waterman algorithm, we can find all local alignments in O(mn) time, where m and n are lengths of a query and a text, respectively. A recent exact approach BWT-SW improves the complexity of the Smith-Waterman algorithm under constraints, but still much slower than BLAST. This paper takes on the challenge of designing an accurate and efficient algorithm for evaluating local-alignment searches, especially for long queries. In this paper, we propose an efficient software called ALAE to speed up BWT-SW using a compressed suffix array. ALAE utilizes a family of filtering techniques to prune meaningless calculations and an algorithm for reusing score calculations. We also give a mathematical analysis and show that the upper bound of the total number of calculated entries using ALAE could vary from 4.50mn0.520 to 9.05mn0.896 for random DNA sequences and vary from 8.28mn0.364 to 7.49mn0.723 for random protein sequences. We demonstrate the significant performance improvement of ALAE on BWT-SW using a thorough experimental study on real biosequences. ALAE guarantees correctness and accelerates BLAST for most of parameters.
An Automat for the Semantic Processing of Structured Information
Venue: arXiv cs.IR 2012
Year: 2012

Using the database of the PuertoTerm project, an indexing system based on the cognitive model of Brigitte Enders was built. By analyzing the cognitive strategies of three abstractors, we built an automat that serves to simulate human indexing processes. The automat allows the texts integrated in the system to be assessed, evaluated and grouped by means of the bipartite spectral graph partitioning algorithm, which also permits visualization of the terms and the documents. The system features an ontology and a database to enhance its operativity. As a result of the application, we achieved better rates of exhaustivity in the indexing of documents, as well as greater precision and retrieval of information, with high levels of efficiency.
Solving Cyclic Longest Common Subsequence in Quadratic Time
Venue: arXiv cs.DS 2012
Year: 2012

We present a practical algorithm for the cyclic longest common subsequence (CLCS) problem that runs in O(mn) time, where m and n are the lengths of the two input strings. While this is not necessarily an asymptotic improvement over the existing record, it is far simpler to understand and to implement.
Grey Power Models Based on Optimization of Initial Condition and Model Parameters
Venue: arXiv cs.SY 2012
Year: 2012

We propose a novel approach to improve prediction accuracy of grey power models including GM(1,1) and grey Verhulst model through optimization of the initial condition and model parameters in this paper. And we propose a modified grey Verhulst model. The new initial condition consists of the first item and the last item of a sequence generated from applying the first-order accumulative generation operator on the sequence of raw data. Weighted coefficients of the first item and the last item in the combination as the initial condition are derived from a method of minimizing error summation of square. We shows that the newly modified grey power model is an extension of the previous optimized GM(1,1) models and grey Verhulst models. The new optimized initial condition can express the principle of new information priority emphasized on in grey systems theory fully. The result of a numerical example indicates that the modified grey model presented in this paper can obtain a better prediction performance than that from the original grey model.
Debugging Memory Issues In Embedded Linux: A Case Study
Venue: arXiv cs.SE 2012
Year: 2012

Debugging denotes the process of detecting root causes of unexpected observable behaviors in programs, such as a program crash, an unexpected output value being produced or an assertion violation. Debugging of program errors is a difficult task and often takes a significant amount of time in the software development life cycle. In the context of embedded software, the probability of bugs is quite high. Due to requirements of low code size and less resource consumption, embedded softwares typically do away with a lot of sanity checks during development time. This leads to high chance of errors being uncovered in the production code at run time. In this paper we propose a methodology for debugging errors in BusyBox, a de-facto standard for Linux in embedded systems. Our methodology works on top of Valgrind, a popular memory error detector and Daikon, an invariant analyzer. We have experimented with two published errors in BusyBox and report our findings in this paper.
Triggercast: Enabling Wireless Collisions Constructive
Venue: arXiv cs.DC 2012
Year: 2012

It is generally considered that concurrent transmissions should be avoided in order to reduce collisions in wireless sensor networks. Constructive interference (CI) envisions concurrent transmissions to positively interfere at the receiver. CI potentially allows orders of magnitude reductions in energy consumptions and improvements on link quality. In this paper, we theoretically introduce a sufficient condition to construct CI with IEEE 802.15.4 radio for the first time. Moreover, we propose Triggercast, a distributed middleware, and show it is feasible to generate CI in TMote Sky sensor nodes. To synchronize transmissions of multiple senders at the chip level, Triggercast effectively compensates propagation and radio processing delays, and has $95^{th}$ percentile synchronization errors of at most 250ns. Triggercast also intelligently decides which co-senders to participate in simultaneous transmissions, and aligns their transmission time to maximize the overall link PRR, under the condition of maximal system robustness. Extensive experiments in real testbeds reveal that Triggercast significantly improves PRR from 5% to 70% with 7 concurrent senders. We also demonstrate that Triggercast provides on average $1.3\times$ PRR performance gains, when integrated with existing data forwarding protocols.
On the control of abelian group codes with information group of prime order
Venue: arXiv cs.IT 2012
Year: 2012

Finite State Machine (FSM) model is widely used in the construction of binary convolutional codes. If Z_2={0,1} is the binary mod-2 addition group and (Z_2)^n is the n-times direct product of Z_2, then a binary convolutional encoder, with rate (k/n)< 1 and memory m, is a FSM with (Z_2)^k as inputs group, (Z_2)^n as outputs group and (Z_2)^m as states group. The next state mapping nu:[(Z_2)^k x (Z_2)^m] --> (Z_2)^m is a surjective group homomorphism. The encoding mapping omega:[(Z_2)^k x (Z_2)^m] --> (Z_2)^n is a homomorphism adequately restricted by the trellis graph produced by nu. The binary convolutional code is the family of bi-infinite sequences produced by the binary convolutional encoder. Thus, a convolutional code can be considered as a dynamical system and it is known that well behaved dynamical systems must be necessarily controllable. The generalization of binary convolutional encoders over arbitrary finite groups is made by using the extension of groups, instead of direct product. In this way, given finite groups U,S and Y, a wide-sense homomorphic encoder (WSHE) is a FSM with U as inputs group, S as states group, and Y as outputs group. By denoting (U x S) as the extension of U by S, the next state homomorphism nu:(U x S) --> S needs to be surjective and the encoding homomorphism omega:(U x S) --> Y has restrictions given by the trellis graph produced by nu. The code produced by a WSHE is known as group code. In this work we will study the case when the extension (U x S) is abelian with U being Z_p, p a positive prime number. We will show that this class of WSHEs will produce controllable codes only if the states group S is isomorphic with (Z_p)^j, for some positive integer j.