OpenRaiser/Intern-Atlas huggingface dataset:
Adaptation of Black-Box Software Components
Venue: arXiv cs.SE 2009
Year: 2009

The globalization of the software market leads to crucial problems for software companies. More competition between software companies arises and leads to the force on companies to develop ever newer software products in ever shortened time interval. Therefor the time to market for software systems is shortened and obviously the product life cycle is shortened too[...]The approach introduced here presents the novel technique together with a supportive environment that enables developers to cope with the adaptability of black-box software components. A supported environment will be designed that checks the compatibility of black-box software components with the assistance of their specifications.
Expert Software for the Determination of Juvenile People's Obesity
Venue: arXiv cs.CY 2009
Year: 2009

Keeping the health condition at the juvenile population is the concern of both the medical staff and the physical education teachers. Considering the steady tendency of the growth of the number of the youth with excessive weight (overweighted or obese) the intervention to combat this phenomenon must be initiated in the early stage when this condition occurs. The screening method for evaluating the body weight presented in this study uses a calculus program through which, based on the input data (age, sex, weight the width of the skin fold) an evaluation regarding each juvenile's weight and the body structure can be done. This program can be used in schools, high schools, universities, to signal the weight excess and to appreciate the intervention results for getting a normal weight.
About Testing the Speed of Calculating the Shortest Route
Venue: arXiv cs.DM 2009
Year: 2009

Applied into a various area of domains, the graph theory and its applications allow the determination of the shortest route. The common algorithm to solve this problem is Bellman-Kalaba, based on the matrix multiplying operation. If the graph is very large (e.g., the dimension of the associated incidence matrix is big) one of the main problems is to reduce the calculus time. This paper presents a testing method able to analyze if an acceleration of the Bellman-Kalaba is possible and able to determine the time efficiency.
Online Estimation of SAT Solving Runtime
Venue: arXiv cs.AI 2009
Year: 2009

We present an online method for estimating the cost of solving SAT problems. Modern SAT solvers present several challenges to estimate search cost including non-chronological backtracking, learning and restarts. Our method uses a linear model trained on data gathered at the start of search. We show the effectiveness of this method using random and structured problems. We demonstrate that predictions made in early restarts can be used to improve later predictions. We also show that we can use such cost estimations to select a solver from a portfolio.
Hierarchical neighbor graphs: A low stretch connected structure for points in Euclidean space
Venue: arXiv cs.NI 2009
Year: 2009

We introduce hierarchical neighbor graphs, a new architecture for connecting ad hoc wireless nodes distributed in a plane. The structure has the flavor of hierarchical clustering and requires only local knowledge and minimal computation at each node to be formed and repaired. Hence, it is a suitable interconnection model for an ad hoc wireless sensor network. The structure is able to use energy efficiently by reorganizing dynamically when the battery power of heavily utilized nodes degrades and is able to achieve throughput, energy efficiency and network lifetimes that compare favorably with the leading proposals for data collation in sensor networks such as LEACH (Heinzelman et. al., 2002). Additionally, hierarchical neighbor graphs have low power stretch i.e. the power required to connect nodes through the network is a small factor higher than the power required to connect them directly. Our structure also compares favorably to mathematical structures proposed for connecting points in a plane e.g. nearest-neighbor graphs (Ballister et. al., 2005), $θ$-graphs (Ruppert and Seidel, 1991), in that it has expected constant degree and does not require any significant computation or global information to be formed.
L'entreprise franco-roumaine face au Internet
Venue: arXiv cs.CY 2009
Year: 2009

The main goal of the present work is to analyze the activity of the French companies from Romania related to the increasing use of the information and communication technology in the productive field. The convergent assembly of information and communication technologies and the process of economic globalization have led to a profound transformation of the economic activity. The present paper is part of a series of studies made on the French firms from Romania between 2007 and 2008.
Multi-Objective Problem Solving With Offspring on Enterprise Clouds
Venue: arXiv cs.DC 2009
Year: 2009

In this paper, we present a distributed implementation of a network based multi-objective evolutionary algorithm, called EMO, by using Offspring. Network based evolutionary algorithms have proven to be effective for multi-objective problem solving. They feature a network of connections between individuals that drives the evolution of the algorithm. Unfortunately, they require large populations to be effective and a distributed implementation can leverage the computation time. Most of the existing frameworks are limited to providing solutions that are basic or specific to a given algorithm. Our Offspring framework is a plug-in based software environment that allows rapid deployment and execution of evolutionary algorithms on distributed computing environments such as Enterprise Clouds. Its features and benefits are presented by describing the distributed implementation of EMO.
Jeeva: Enterprise Grid-enabled Web Portal for Protein Secondary Structure Prediction
Venue: arXiv cs.DC 2009
Year: 2009

This paper presents a Grid portal for protein secondary structure prediction developed by using services of Aneka, a .NET-based enterprise Grid technology. The portal is used by research scientists to discover new prediction structures in a parallel manner. An SVM (Support Vector Machine)-based prediction algorithm is used with 64 sample protein sequences as a case study to demonstrate the potential of enterprise Grids.
A Lagrangian Relaxation for the Maximum Stable Set Problem
Venue: arXiv cs.DM 2009
Year: 2009

We propose a new integer programming formulation for the problem of finding a maximum stable set of a graph based on representatives of stable sets. In addition, we investigate exact solutions provided by a Lagrangian decomposition of this formulation in which only one constraint is relaxed. Some computational experiments were carried out with an effective multi-threaded implementation of our algorithm in a multi-core system, and their results are presented.
Dynamic Updating for L1 Minimization
Venue: arXiv cs.IT 2009
Year: 2009

The theory of compressive sensing (CS) suggests that under certain conditions, a sparse signal can be recovered from a small number of linear incoherent measurements. An effective class of reconstruction algorithms involve solving a convex optimization program that balances the L1 norm of the solution against a data fidelity term. Tremendous progress has been made in recent years on algorithms for solving these L1 minimization programs. These algorithms, however, are for the most part static: they focus on finding the solution for a fixed set of measurements. In this paper, we will discuss "dynamic algorithms" for solving L1 minimization programs for streaming sets of measurements. We consider cases where the underlying signal changes slightly between measurements, and where new measurements of a fixed signal are sequentially added to the system. We develop algorithms to quickly update the solution of several different types of L1 optimization problems whenever these changes occur, thus avoiding having to solve a new optimization problem from scratch. Our proposed schemes are based on homotopy continuation, which breaks down the solution update in a systematic and efficient way into a small number of linear steps. Each step consists of a low-rank update and a small number of matrix-vector multiplications -- very much like recursive least squares. Our investigation also includes dynamic updating schemes for L1 decoding problems, where an arbitrary signal is to be recovered from redundant coded measurements which have been corrupted by sparse errors.
The Digital Restoration of Da Vinci's Sketches
Venue: arXiv cs.CV 2009
Year: 2009

A sketch, found in one of Leonardo da Vinci's notebooks and covered by the written notes of this genius, has been recently restored. The restoration reveals a possible self-portrait of the artist, drawn when he was young. Here, we discuss the discovery of this self-portrait and the procedure used for restoration. Actually, this is a restoration performed on the digital image of the sketch, a procedure that can easily extended and applied to ancient documents for studies of art and palaeography.
How Much Information can One Get from a Wireless Ad Hoc Sensor Network over a Correlated Random Field?
Venue: arXiv cs.IT 2009
Year: 2009

New large deviations results that characterize the asymptotic information rates for general $d$-dimensional ($d$-D) stationary Gaussian fields are obtained. By applying the general results to sensor nodes on a two-dimensional (2-D) lattice, the asymptotic behavior of ad hoc sensor networks deployed over correlated random fields for statistical inference is investigated. Under a 2-D hidden Gauss-Markov random field model with symmetric first order conditional autoregression and the assumption of no in-network data fusion, the behavior of the total obtainable information [nats] and energy efficiency [nats/J] defined as the ratio of total gathered information to the required energy is obtained as the coverage area, node density and energy vary. When the sensor node density is fixed, the energy efficiency decreases to zero with rate $Θ({area}^{-1/2})$ and the per-node information under fixed per-node energy also diminishes to zero with rate $O(N_t^{-1/3})$ as the number $N_t$ of network nodes increases by increasing the coverage area. As the sensor spacing $d_n$ increases, the per-node information converges to its limit $D$ with rate $D-\sqrt{d_n}e^{-αd_n}$ for a given diffusion rate $α$. When the coverage area is fixed and the node density increases, the per-node information is inversely proportional to the node density. As the total energy $E_t$ consumed in the network increases, the total information obtainable from the network is given by $O(\log E_t)$ for the fixed node density and fixed coverage case and by $Θ(E_t^{2/3})$ for the fixed per-node sensing energy and fixed density and increasing coverage case.
Continuation-Passing Style and Strong Normalisation for Intuitionistic Sequent Calculi
Venue: arXiv cs.LO 2009
Year: 2009

The intuitionistic fragment of the call-by-name version of Curien and Herbelin's λ\_mu\_{mu}-calculus is isolated and proved strongly normalising by means of an embedding into the simply-typed lambda-calculus. Our embedding is a continuation-and-garbage-passing style translation, the inspiring idea coming from Ikeda and Nakazawa's translation of Parigot's λ\_mu-calculus. The embedding strictly simulates reductions while usual continuation-passing-style transformations erase permutative reduction steps. For our intuitionistic sequent calculus, we even only need "units of garbage" to be passed. We apply the same method to other calculi, namely successive extensions of the simply-typed λ-calculus leading to our intuitionistic system, and already for the simplest extension we consider (λ-calculus with generalised application), this yields the first proof of strong normalisation through a reduction-preserving embedding. The results obtained extend to second and higher-order calculi.
Limitations of Self-Assembly at Temperature 1
Venue: arXiv cs.DM 2009
Year: 2009

We prove that if a set $X \subseteq \Z^2$ weakly self-assembles at temperature 1 in a deterministic tile assembly system satisfying a natural condition known as \emph{pumpability}, then $X$ is a finite union of semi-doubly periodic sets. This shows that only the most simple of infinite shapes and patterns can be constructed using pumpable temperature 1 tile assembly systems, and gives evidence for the thesis that temperature 2 or higher is required to carry out general-purpose computation in a tile assembly system. Finally, we show that general-purpose computation \emph{is} possible at temperature 1 if negative glue strengths are allowed in the tile assembly model.
Better Termination for Prolog with Constraints
Venue: arXiv cs.PL 2009
Year: 2009

Termination properties of actual Prolog systems with constraints are fragile and difficult to analyse. The lack of the occurs-check, moded and overloaded arithmetical evaluation via is/2 and the occasional nontermination of finite domain constraints are all sources for invalidating termination results obtained by current termination analysers that rely on idealized assumptions. In this paper, we present solutions to address these problems on the level of the underlying Prolog system. Improved unification modes meet the requirements of norm based analysers by offering dynamic occurs-check detection. A generalized finite domain solver overcomes the shortcomings of conventional arithmetic without significant runtime overhead. The solver offers unbounded domains, yet propagation always terminates. Our work improves Prolog's termination and makes Prolog a more reliable target for termination and type analysis. It is part of SWI-Prolog since version 5.6.50.
Rfuzzy framework
Venue: arXiv cs.PL 2009
Year: 2009

Fuzzy reasoning is a very productive research field that during the last years has provided a number of theoretical approaches and practical implementation prototypes. Nevertheless, the classical implementations, like Fril, are not adapted to the latest formal approaches, like multi-adjoint logic semantics. Some promising implementations, like Fuzzy Prolog, are so general that the regular user/programmer does not feel comfortable because either representation of fuzzy concepts is complex or the results difficult to interpret. In this paper we present a modern framework, Rfuzzy, that is modelling multi-adjoint logic. It provides some extensions as default values (to represent missing information, even partial default values) and typed variables. Rfuzzy represents the truth value of predicates through facts, rules and functions. Rfuzzy answers queries with direct results (instead of constraints) and it is easy to use for any person that wants to represent a problem using fuzzy reasoning in a simple way (by using the classical representation with real numbers).
A Novel Approach for Compression of Images Captured using Bayer Color Filter Arrays
Venue: arXiv cs.MM 2009
Year: 2009

We propose a new approach for image compression in digital cameras, where the goal is to achieve better quality at a given rate by using the characteristics of a Bayer color filter array. Most digital cameras produce color images by using a single CCD plate, so that each pixel in an image has only one color component and therefore an interpolation method is needed to produce a full color image. After the image processing stage, in order to reduce the memory requirements of the camera, a lossless or lossy compression stage often follows. But in this scheme, before decreasing redundancy through compression, redundancy is increased in an interpolation stage. In order to avoid increasing the redundancy before compression, we propose algorithms for image compression in which the order of the compression and interpolation stages is reversed. We introduce image transform algorithms, since non interpolated images cannot be directly compressed with general image coders. The simulation results show that our algorithm outperforms conventional methods with various color interpolation methods in a wide range of compression ratios. Our proposed algorithm provides not only better quality but also lower encoding complexity because the amount of luminance data used is only half of that in conventional methods.
Construction and Covering Properties of Constant-Dimension Codes
Venue: arXiv cs.IT 2009
Year: 2009

Constant-dimension codes (CDCs) have been investigated for noncoherent error correction in random network coding. The maximum cardinality of CDCs with given minimum distance and how to construct optimal CDCs are both open problems, although CDCs obtained by lifting Gabidulin codes, referred to as KK codes, are nearly optimal. In this paper, we first construct a new class of CDCs based on KK codes, referred to as augmented KK codes, whose cardinalities are greater than previously proposed CDCs. We then propose a low-complexity decoding algorithm for our augmented KK codes using that for KK codes. Our decoding algorithm corrects more errors than a bounded subspace distance decoder by taking advantage of the structure of our augmented KK codes. In the rest of the paper we investigate the covering properties of CDCs. We first derive bounds on the minimum cardinality of a CDC with a given covering radius and then determine the asymptotic behavior of this quantity. Moreover, we show that liftings of rank metric codes have the highest possible covering radius, and hence liftings of rank metric codes are not optimal packing CDCs. Finally, we construct good covering CDCs by permuting liftings of rank metric codes.
Dynamic Multi-Vehicle Routing with Multiple Classes of Demands
Venue: arXiv cs.RO 2009
Year: 2009

In this paper we study a dynamic vehicle routing problem in which there are multiple vehicles and multiple classes of demands. Demands of each class arrive in the environment randomly over time and require a random amount of on-site service that is characteristic of the class. To service a demand, one of the vehicles must travel to the demand location and remain there for the required on-site service time. The quality of service provided to each class is given by the expected delay between the arrival of a demand in the class, and that demand's service completion. The goal is to design a routing policy for the service vehicles which minimizes a convex combination of the delays for each class. First, we provide a lower bound on the achievable values of the convex combination of delays. Then, we propose a novel routing policy and analyze its performance under heavy load conditions (i.e., when the fraction of time the service vehicles spend performing on-site service approaches one). The policy performs within a constant factor of the lower bound (and thus the optimal), where the constant depends only on the number of classes, and is independent of the number of vehicles, the arrival rates of demands, the on-site service times, and the convex combination coefficients.
On the Computational Complexity of Satisfiability Solving for String Theories
Venue: arXiv cs.CC 2009
Year: 2009

Satisfiability solvers are increasingly playing a key role in software verification, with particularly effective use in the analysis of security vulnerabilities. String processing is a key part of many software applications, such as browsers and web servers. These applications are susceptible to attacks through malicious data received over network. Automated tools for analyzing the security of such applications, thus need to reason about strings. For efficiency reasons, it is desirable to have a solver that treats strings as first-class types. In this paper, we present some theories of strings that are useful in a software security context and analyze the computational complexity of the presented theories. We use this complexity analysis to motivate a byte-blast approach which employs a Boolean encoding of the string constraints to a corresponding Boolean satisfiability problem.
A decidable policy language for history-based transaction monitoring
Venue: arXiv cs.LO 2009
Year: 2009

Online trading invariably involves dealings between strangers, so it is important for one party to be able to judge objectively the trustworthiness of the other. In such a setting, the decision to trust a user may sensibly be based on that user's past behaviour. We introduce a specification language based on linear temporal logic for expressing a policy for categorising the behaviour patterns of a user depending on its transaction history. We also present an algorithm for checking whether the transaction history obeys the stated policy. To be useful in a real setting, such a language should allow one to express realistic policies which may involve parameter quantification and quantitative or statistical patterns. We introduce several extensions of linear temporal logic to cater for such needs: a restricted form of universal and existential quantification; arbitrary computable functions and relations in the term language; and a "counting" quantifier for counting how many times a formula holds in the past. We then show that model checking a transaction history against a policy, which we call the history-based transaction monitoring problem, is PSPACE-complete in the size of the policy formula and the length of the history. The problem becomes decidable in polynomial time when the policies are fixed. We also consider the problem of transaction monitoring in the case where not all the parameters of actions are observable. We formulate two such "partial observability" monitoring problems, and show their decidability under certain restrictions.
Introducing Hierarchy in Energy Games
Venue: arXiv cs.GT 2009
Year: 2009

In this work we introduce hierarchy in wireless networks that can be modeled by a decentralized multiple access channel and for which energy-efficiency is the main performance index. In these networks users are free to choose their power control strategy to selfishly maximize their energy-efficiency. Specifically, we introduce hierarchy in two different ways: 1. Assuming single-user decoding at the receiver, we investigate a Stackelberg formulation of the game where one user is the leader whereas the other users are assumed to be able to react to the leader's decisions; 2. Assuming neither leader nor followers among the users, we introduce hierarchy by assuming successive interference cancellation at the receiver. It is shown that introducing a certain degree of hierarchy in non-cooperative power control games not only improves the individual energy efficiency of all the users but can also be a way of insuring the existence of a non-saturated equilibrium and reaching a desired trade-off between the global network performance at the equilibrium and the requested amount of signaling. In this respect, the way of measuring the global performance of an energy-efficient network is shown to be a critical issue.
A Unified Theory of Time-Frequency Reassignment
Venue: arXiv cs.SD 2009
Year: 2009

Time-frequency representations such as the spectrogram are commonly used to analyze signals having a time-varying distribution of spectral energy, but the spectrogram is constrained by an unfortunate tradeoff between resolution in time and frequency. A method of achieving high-resolution spectral representations has been independently introduced by several parties. The technique has been variously named reassignment and remapping, but while the implementations have differed in details, they are all based on the same theoretical and mathematical foundation. In this work, we present a brief history of work on the method we will call the method of time-frequency reassignment, and present a unified mathematical description of the technique and its derivation. We will focus on the development of time-frequency reassignment in the context of the spectrogram, and conclude with a discussion of some current applications of the reassigned spectrogram.