OpenRaiser/Intern-Atlas huggingface dataset:
Applying Software Defect Estimations: Using a Risk Matrix for Tuning Test Effort
Venue: arXiv cs.SE 2007
Year: 2007

Applying software defect esimation techniques and presenting this information in a compact and impactful decision table can clearly illustrate to collaborative groups how critical this position is in the overall development cycle. The Test Risk Matrix described here has proven to be a valuable addition to the management tools and approaches used in developing large scale software on several releases. Use of this matrix in development planning meetings can clarify the attendant risks and possible consequences of carrying out or bypassing specific test activities.
Kinematic calibration of orthoglide-type mechanisms
Venue: arXiv cs.RO 2007
Year: 2007

The paper proposes a novel calibration approach for the Orthoglide-type mechanisms based on observations of the manipulator leg parallelism during mo-tions between the prespecified test postures. It employs a low-cost measuring system composed of standard comparator indicators attached to the universal magnetic stands. They are sequentially used for measuring the deviation of the relevant leg location while the manipulator moves the TCP along the Cartesian axes. Using the measured differences, the developed algorithm estimates the joint offsets that are treated as the most essential parameters to be adjusted. The sensitivity of the meas-urement methods and the calibration accuracy are also studied. Experimental re-sults are presented that demonstrate validity of the proposed calibration technique
Autoregressive Time Series Forecasting of Computational Demand
Venue: arXiv cs.DC 2007
Year: 2007

We study the predictive power of autoregressive moving average models when forecasting demand in two shared computational networks, PlanetLab and Tycoon. Demand in these networks is very volatile, and predictive techniques to plan usage in advance can improve the performance obtained drastically. Our key finding is that a random walk predictor performs best for one-step-ahead forecasts, whereas ARIMA(1,1,0) and adaptive exponential smoothing models perform better for two and three-step-ahead forecasts. A Monte Carlo bootstrap test is proposed to evaluate the continuous prediction performance of different models with arbitrary confidence and statistical significance levels. Although the prediction results differ between the Tycoon and PlanetLab networks, we observe very similar overall statistical properties, such as volatility dynamics.
Query Evaluation and Optimization in the Semantic Web
Venue: arXiv cs.DB 2007
Year: 2007

We address the problem of answering Web ontology queries efficiently. An ontology is formalized as a Deductive Ontology Base (DOB), a deductive database that comprises the ontology's inference axioms and facts. A cost-based query optimization technique for DOB is presented. A hybrid cost model is proposed to estimate the cost and cardinality of basic and inferred facts. Cardinality and cost of inferred facts are estimated using an adaptive sampling technique, while techniques of traditional relational cost models are used for estimating the cost of basic facts and conjunctive ontology queries. Finally, we implement a dynamic-programming optimization algorithm to identify query evaluation plans that minimize the number of intermediate inferred facts. We modeled a subset of the Web ontology language OWL Lite as a DOB, and performed an experimental study to analyze the predictive capacity of our cost model and the benefits of the query optimization technique. Our study has been conducted over synthetic and real-world OWL ontologies, and shows that the techniques are accurate and improve query performance. To appear in Theory and Practice of Logic Programming (TPLP).
Patterns of i.i.d. Sequences and Their Entropy - Part II: Bounds for Some Distributions
Venue: arXiv cs.IT 2007
Year: 2007

A pattern of a sequence is a sequence of integer indices with each index describing the order of first occurrence of the respective symbol in the original sequence. In a recent paper, tight general bounds on the block entropy of patterns of sequences generated by independent and identically distributed (i.i.d.) sources were derived. In this paper, precise approximations are provided for the pattern block entropies for patterns of sequences generated by i.i.d. uniform and monotonic distributions, including distributions over the integers, and the geometric distribution. Numerical bounds on the pattern block entropies of these distributions are provided even for very short blocks. Tight bounds are obtained even for distributions that have infinite i.i.d. entropy rates. The approximations are obtained using general bounds and their derivation techniques. Conditional index entropy is also studied for distributions over smaller alphabets.
A Compact Self-organizing Cellular Automata-based Genetic Algorithm
Venue: arXiv cs.NE 2007
Year: 2007

A Genetic Algorithm (GA) is proposed in which each member of the population can change schemata only with its neighbors according to a rule. The rule methodology and the neighborhood structure employ elements from the Cellular Automata (CA) strategies. Each member of the GA population is assigned to a cell and crossover takes place only between adjacent cells, according to the predefined rule. Although combinations of CA and GA approaches have appeared previously, here we rely on the inherent self-organizing features of CA, rather than on parallelism. This conceptual shift directs us toward the evolution of compact populations containing only a handful of members. We find that the resulting algorithm can search the design space more efficiently than traditional GA strategies due to its ability to exploit mutations within this compact self-organizing population. Consequently, premature convergence is avoided and the final results often are more accurate. In order to reinforce the superior mutation capability, a re-initialization strategy also is implemented. Ten test functions and two benchmark structural engineering truss design problems are examined in order to demonstrate the performance of the method.
Error Exponents of Erasure/List Decoding Revisited via Moments of Distance Enumerators
Venue: arXiv cs.IT 2007
Year: 2007

The analysis of random coding error exponents pertaining to erasure/list decoding, due to Forney, is revisited. Instead of using Jensen's inequality as well as some other inequalities in the derivation, we demonstrate that an exponentially tight analysis can be carried out by assessing the relevant moments of a certain distance enumerator. The resulting bound has the following advantages: (i) it is at least as tight as Forney's bound, (ii) under certain symmetry conditions associated with the channel and the random coding distribution, it is simpler than Forney's bound in the sense that it involves an optimization over one parameter only (rather than two), and (iii) in certain special cases, like the binary symmetric channel (BSC), the optimum value of this parameter can be found in closed form, and so, there is no need to conduct a numerical search. We have not found yet, however, a numerical example where this new bound is strictly better than Forney's bound. This may provide an additional evidence to support Forney's conjecture that his bound is tight for the average code. We believe that the technique we suggest in this paper can be useful in simplifying, and hopefully also improving, exponential error bounds in other problem settings as well.
Une approche par les modèles pour le suivi de l'activité de construction d'un bâtiment. Bat'iViews : une interface multi-vues orientée gestion de chantier
Venue: arXiv cs.HC 2007
Year: 2007

Cooperation between actors in design and construction activities in architecture is an essential stake nowadays. In professional practices the actors involved in construction projects use numerous tools. The project is unique but the "views" that actors manipulate are various and sometimes fundamentally different. Their common characteristic is that they partially represent the cooperation context through a specific point of view. "Bat'iViews" suggests to the actors a multi-view interface of the context and enables to navigate through the different views. This proposition is based on a model-driven approach. We distinguish between "context modelling" and modelling of concepts represented in each "businessview". A model integrative infrastructure allows us to develop the prototype and to manage user interaction through the definition of models' transformations.
Degrees of Freedom of Wireless X Networks
Venue: arXiv cs.IT 2007
Year: 2007

We explore the degrees of freedom of $M\times N$ user wireless $X$ networks, i.e. networks of $M$ transmitters and $N$ receivers where every transmitter has an independent message for every receiver. We derive a general outerbound on the degrees of freedom \emph{region} of these networks. When all nodes have a single antenna and all channel coefficients vary in time or frequency, we show that the \emph{total} number of degrees of freedom of the $X$ network is equal to $\frac{MN}{M+N-1}$ per orthogonal time and frequency dimension. Achievability is proved by constructing interference alignment schemes for $X$ networks that can come arbitrarily close to the outerbound on degrees of freedom. For the case where either M=2 or N=2 we find that the outerbound is exactly achievable. While $X$ networks have significant degrees of freedom benefits over interference networks when the number of users is small, our results show that as the number of users increases, this advantage disappears. Thus, for large $K$, the $K\times K$ user wireless $X$ network loses half the degrees of freedom relative to the $K\times K$ MIMO outerbound achievable through full cooperation. Interestingly, when there are few transmitters sending to many receivers ($N\gg M$) or many transmitters sending to few receivers ($M\gg N$), $X$ networks are able to approach the $\min(M,N)$ degrees of freedom possible with full cooperation on the $M\times N$ MIMO channel. Similar to the interference channel, we also construct an example of a 2 user $X$ channel with propagation delays where the outerbound on degrees of freedom is achieved through interference alignment based on a simple TDMA strategy.
Dynamic 3-Coloring of Claw-free Graphs
Venue: arXiv cs.DM 2007
Year: 2007

A {\it dynamic $k$-coloring} of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex of degree at least 2 in $G$ will be adjacent to vertices with at least 2 different colors. The smallest number $k$ for which a graph $G$ can have a dynamic $k$-coloring is the {\it dynamic chromatic number}, denoted by $χ_d(G)$. In this paper, we investigate the dynamic 3-colorings of claw-free graphs. First, we prove that it is $NP$-complete to determine if a claw-free graph with maximum degree 3 is dynamically 3-colorable. Second, by forbidding a kind of subgraphs, we find a reasonable subclass of claw-free graphs with maximum degree 3, for which the dynamically 3-colorable problem can be solved in linear time. Third, we give a linear time algorithm to recognize this subclass of graphs, and a linear time algorithm to determine whether it is dynamically 3-colorable. We also give a linear time algorithm to color the graphs in the subclass by 3 colors.
Optimizing diversity
Venue: arXiv cs.DM 2007
Year: 2007

We consider the problem of minimizing the size of a family of sets G such that every subset of 1,...,n can be written as a disjoint union of at most k members of G, where k and n are given numbers. This problem originates in a real-world application aiming at the diversity of industrial production. At the same time, the minimum of G so that every subset of 1,...,n is the union of two sets in G has been asked by Erdos and studied recently by Furedi and Katona without requiring the disjointness of the sets. A simple construction providing a feasible solution is conjectured to be optimal for this problem for all values of n and k and regardless of the disjointness requirement; we prove this conjecture in special cases including all (n,k) for which n <= 3k holds, and some individual values of n and k.
How to realize "a sense of humour" in computers ?
Venue: arXiv cs.CL 2007
Year: 2007

Computer model of a "sense of humour" suggested previously [arXiv:0711.2058, 0711.2061, 0711.2270] is raised to the level of a realistic algorithm.
Motion-Based Generators for Industrial Applications
Venue: arXiv cs.OH 2007
Year: 2007

Scaling down of electronic systems has generated a large interest in the research on miniature energy sources. In this paper a closer look is given to the use of vibration based scavengers in industrial environments, where waste energy is abundantly available as engine related vibrations or large amplitude motions. The modeling of mechanical generators resulted in the design and realization of two prototypes, based on electromagnetic and electrostatic conversion of energy. Although the prototypes are not yet optimized against size and efficiency, a power of 0.3 mW has been generated in a 5 Hz motion with a 0.5 meter amplitude.
Contactless Thermal Characterization Method of PCB-s Using an IR Sensor Array
Venue: arXiv cs.OH 2007
Year: 2007

In this paper the feasibility study of an IR sensor card is presented. The methodology and the results of a quasi real-time thermal characterization tool and method for the temperature mapping of circuits and boards based on sensing the infrared radiation is introduced. With the proposed method the IR radiation-distribution of boards from the close proximity of the sensor card is monitored in quasi real-time. The proposed method is enabling in situ IR measurement among operating cards of a system e.g. in a rack.
Integration of Micro-Electro-Mechanical Deformable Mirrors in Doped Fiber Amplifiers
Venue: arXiv cs.OH 2007
Year: 2007

We present a simple technique to produce active Q-switching in various types of fiber amplifiers by active integration of an electrostatic actuated deformable metallic micro-mirror. The optical MEMS (MOEMS) device acts as one of the laser cavity reflectors and, at the same time, as switching/ modulator element. We aim to obtain laser systems emitting short, high-power pulses and having variable repetition rate. The electro-mechanical behavior of membrane (bridge-type) was simulated by using electrostatic and modal 3D finite element analysis (FEA). The results of the simulations fit well with the experimental mechanical, electrical and thermal measurements of the components. In order to decrease the sensitiveness to fiber-mirror alignment we are developing novel optical devices based on stressed-metal cantilever-type geometry that allow deflections up to 50 $μ$m with increased reflectivity discrimination during actuation.
Process Issues for a Multi-Layer Microelectrofluidic Platform
Venue: arXiv cs.OH 2007
Year: 2007

We report on the development of some process capabilities for a polymer-based, multi-layer microelectrofluidic platform, namely: the hot embossing process, metallization on polymer and polymer bonding. Hot embossing experiments were conducted to look at the effects of load applied, embossing temperature and embossing time on the fidelity of line arrays representing micro channels. The results revealed that the embossing temperature is a more sensitive parameter than the others due to its large effect on the polymer material's viscoelastic properties. Dynamic mechanical analysis (DMA) on polymethyl methacrylate (PMMA) revealed a steep glass transition over a 20 oC range, with the material losing more than 95 % of its storage modulus. The data explained the hot embossing results which showed large change in the embossed channel dimensions when the temperature is within the glass transition range. It was demonstrated that the micro-printing of silver epoxy is a possible low-cost technique in the mass production of disposable lab chips. An interconnecting network of electrical traces was fabricated in the form of a four-layer PMMA-based device. A four PMMA layer device with interconnecting microfluidic channels was also fabricated and tested.
An Inflationary Fixed Point Operator in XQuery
Venue: arXiv cs.DB 2007
Year: 2007

We introduce a controlled form of recursion in XQuery, inflationary fixed points, familiar in the context of relational databases. This imposes restrictions on the expressible types of recursion, but we show that inflationary fixed points nevertheless are sufficiently versatile to capture a wide range of interesting use cases, including the semantics of Regular XPath and its core transitive closure construct. While the optimization of general user-defined recursive functions in XQuery appears elusive, we will describe how inflationary fixed points can be efficiently evaluated, provided that the recursive XQuery expressions exhibit a distributivity property. We show how distributivity can be assessed both, syntactically and algebraically, and provide experimental evidence that XQuery processors can substantially benefit during inflationary fixed point evaluation.
Translating OWL and Semantic Web Rules into Prolog: Moving Toward Description Logic Programs
Venue: arXiv cs.AI 2007
Year: 2007

To appear in Theory and Practice of Logic Programming (TPLP), 2008. We are researching the interaction between the rule and the ontology layers of the Semantic Web, by comparing two options: 1) using OWL and its rule extension SWRL to develop an integrated ontology/rule language, and 2) layering rules on top of an ontology with RuleML and OWL. Toward this end, we are developing the SWORIER system, which enables efficient automated reasoning on ontologies and rules, by translating all of them into Prolog and adding a set of general rules that properly capture the semantics of OWL. We have also enabled the user to make dynamic changes on the fly, at run time. This work addresses several of the concerns expressed in previous work, such as negation, complementary classes, disjunctive heads, and cardinality, and it discusses alternative approaches for dealing with inconsistencies in the knowledge base. In addition, for efficiency, we implemented techniques called extensionalization, avoiding reanalysis, and code minimization.
Secure Fractal Image Coding
Venue: arXiv cs.MM 2007
Year: 2007

In recent work, various fractal image coding methods are reported, which adopt the self-similarity of images to compress the size of images. However, till now, no solutions for the security of fractal encoded images have been provided. In this paper, a secure fractal image coding scheme is proposed and evaluated, which encrypts some of the fractal parameters during fractal encoding, and thus, produces the encrypted and encoded image. The encrypted image can only be recovered by the correct key. To keep secure and efficient, only the suitable parameters are selected and encrypted through in-vestigating the properties of various fractal parameters, including parameter space, parameter distribu-tion and parameter sensitivity. The encryption process does not change the file format, keeps secure in perception, and costs little time or computational resources. These properties make it suitable for secure image encoding or transmission.
Very strict selectional restrictions
Venue: arXiv cs.CL 2007
Year: 2007

We discuss the characteristics and behaviour of two parallel classes of verbs in two Romance languages, French and Portuguese. Examples of these verbs are Port. abater [gado] and Fr. abattre [bétail], both meaning "slaughter [cattle]". In both languages, the definition of the class of verbs includes several features: - They have only one essential complement, which is a direct object. - The nominal distribution of the complement is very limited, i.e., few nouns can be selected as head nouns of the complement. However, this selection is not restricted to a single noun, as would be the case for verbal idioms such as Fr. monter la garde "mount guard". - We excluded from the class constructions which are reductions of more complex constructions, e.g. Port. afinar [instrumento] com "tune [instrument] with".
Convolutional codes from units in matrix and group rings
Venue: arXiv cs.IT 2007
Year: 2007

A general method for constructing convolutional codes from units in Laurent series over matrix rings is presented. Using group ring as matrix rings, this forms a basis for in-depth exploration of convolutional codes from group ring encoding, wherein the ring in the group ring is itself a group ring. The method is used to algebraically construct series of convolutional codes. Algebraic methods are used to compute free distances and to construct convolutional codes to prescribed distances.
A Family of Likelihood Ascent Search Multiuser Detectors: Approach to Single-User Performance via Quasi-Large Random Sequence CDMA
Venue: arXiv cs.IT 2007
Year: 2007

Since Tse and Verdu proved that the global maximum likelihood (GML) detector achieves unit asymptotic multiuser efficiency (AME) in the limit of large random spreading (LRS) CDMA, no suboptimal detector has been found to achieve unit AME. In this letter, we obtain that the WSLAS detector with a linear per-bit complexity achieves unit AME in the LRS-CDMA with a channel load < 1/2 - 1/(4ln2) bits/s/Hz. For a practical system with any user number, a quasi LRS-CDMA is then proposed to approach the single-user performance in the high SNR regime.
An Adaptive Checkpointing Scheme for Peer-to-Peer Based Volunteer Computing Work Flows
Venue: arXiv cs.DC 2007
Year: 2007

Volunteer Computing, sometimes called Public Resource Computing, is an emerging computational model that is very suitable for work-pooled parallel processing. As more complex grid applications make use of work flows in their design and deployment it is reasonable to consider the impact of work flow deployment over a Volunteer Computing infrastructure. In this case, the inter work flow I/O can lead to a significant increase in I/O demands at the work pool server. A possible solution is the use of a Peer-to- Peer based parallel computing architecture to off-load this I/O demand to the workers; where the workers can fulfill some aspects of work flow coordination and I/O checking, etc. However, achieving robustness in such a large scale system is a challenging hurdle towards the decentralized execution of work flows and general parallel processes. To increase robustness, we propose and show the merits of using an adaptive checkpoint scheme that efficiently checkpoints the status of the parallel processes according to the estimation of relevant network and peer parameters. Our scheme uses statistical data observed during runtime to dynamically make checkpoint decisions in a completely de- centralized manner. The results of simulation show support for our proposed approach in terms of reduced required runtime.
Iterative Filtering for a Dynamical Reputation System
Venue: arXiv cs.IR 2007
Year: 2007

The paper introduces a novel iterative method that assigns a reputation to n + m items: n raters and m objects. Each rater evaluates a subset of objects leading to a n x m rating matrix with a certain sparsity pattern. From this rating matrix we give a nonlinear formula to define the reputation of raters and objects. We also provide an iterative algorithm that superlinearly converges to the unique vector of reputations and this for any rating matrix. In contrast to classical outliers detection, no evaluation is discarded in this method but each one is taken into account with different weights for the reputation of the objects. The complexity of one iteration step is linear in the number of evaluations, making our algorithm efficient for large data set. Experiments show good robustness of the reputation of the objects against cheaters and spammers and good detection properties of cheaters and spammers.