OpenRaiser/Intern-Atlas huggingface dataset:
Extending Design by Contract for Aspect-Oriented Programming
Venue: arXiv cs.SE 2005
Year: 2005

Design by Contract (DbC) and runtime enforcement of program assertions enables the construction of more robust software. It also enables the assignment of blame in error reporting. Unfortunately, there is no support for runtime contract enforcement and blame assignment for Aspect-Oriented Programming (AOP). Extending DbC to also cover aspects brings forward a plethora of issues related to the correct order of assertion validation. We show that there is no generally correct execution sequence of object assertions and aspect assertions. A further classification of aspects as agnostic, obedient, or rebellious defines the order of assertion validation that needs to be followed. We describe the application of this classification in a prototyped DbC tool for AOP named Cona, where aspects are used for implementing contracts, and contracts are used for enforcing assertions on aspects.
An Information Network Overlay Architecture for the NSDL
Venue: arXiv cs.DL 2005
Year: 2005

We describe the underlying data model and implementation of a new architecture for the National Science Digital Library (NSDL) by the Core Integration Team (CI). The architecture is based on the notion of an information network overlay. This network, implemented as a graph of digital objects in a Fedora repository, allows the representation of multiple information entities and their relationships. The architecture provides the framework for contextualization and reuse of resources, which we argue is essential for the utility of the NSDL as a tool for teaching and learning.
A Tree Search Method for Iterative Decoding of Underdetermined Multiuser Systems
Venue: arXiv cs.IT 2005
Year: 2005

Application of the turbo principle to multiuser decoding results in an exchange of probability distributions between two sets of constraints. Firstly, constraints imposed by the multiple-access channel, and secondly, individual constraints imposed by each users' error control code. A-posteriori probability computation for the first set of constraints is prohibitively complex for all but a small number of users. Several lower complexity approaches have been proposed in the literature. One class of methods is based on linear filtering (e.g. LMMSE). A more recent approach is to compute approximations to the posterior probabilities by marginalising over a subset of sequences (list detection). Most of the list detection methods are restricted to non-singular systems. In this paper, we introduce a transformation that permits application of standard tree-search methods to underdetermined systems. We find that the resulting tree-search based receiver outperforms existing methods.
Corpus based Enrichment of GermaNet Verb Frames
Venue: arXiv cs.AI 2005
Year: 2005

Lexical semantic resources, like WordNet, are often used in real applications of natural language document processing. For example, we integrated GermaNet in our document suite XDOC of processing of German forensic autopsy protocols. In addition to the hypernymy and synonymy relation, we want to adapt GermaNet's verb frames for our analysis. In this paper we outline an approach for the domain related enrichment of GermaNet verb frames by corpus based syntactic and co-occurred data analyses of real documents.
Identification of complex systems in the basis of wavelets
Venue: arXiv cs.CE 2005
Year: 2005

In this paper is proposed the method of the identification of complex dynamic systems. Method can be used for the identification of linear and nonlinear complex dynamic systems for the determined or stochastic signals at the inputs and the outputs. It is proposed to use a basis of wavelets for obtaining the impulse transient function (ITF) of system. ITF is considered in the form of surface in the 3D space. Are given the results of experiments on the identification of systems in the basis of wavelets.
Sequential File Programming Patterns and Performance with .NET
Venue: arXiv cs.PF 2005
Year: 2005

Programming patterns for sequential file access in the .NET Framework are described and the performance is measured. The default behavior provides excellent performance on a single disk - 50 MBps both reading and writing. Using large request sizes and doing file pre-allocation when possible have quantifiable benefits. When one considers disk arrays, .NET unbuffered IO delivers 800 MBps on a 16-disk array, but buffered IO delivers about 12% of that performance. Consequently, high-performance file and database utilities are still forced to use unbuffered IO for maximum sequential performance. The report is accompanied by downloadable source code that demonstrates the concepts and code that was used to obtain these measurements.
Estimating mutual information and multi--information in large networks
Venue: arXiv cs.IT 2005
Year: 2005

We address the practical problems of estimating the information relations that characterize large networks. Building on methods developed for analysis of the neural code, we show that reliable estimates of mutual information can be obtained with manageable computational effort. The same methods allow estimation of higher order, multi--information terms. These ideas are illustrated by analyses of gene expression, financial markets, and consumer preferences. In each case, information theoretic measures correlate with independent, intuitive measures of the underlying structures in the system.
EPspectra: A Formal Toolkit for Developing DSP Software Applications
Venue: arXiv cs.LO 2005
Year: 2005

The software approach to developing Digital Signal Processing (DSP) applications brings some great features such as flexibility, re-usability of resources and easy upgrading of applications. However, it requires long and tedious tests and verification phases because of the increasing complexity of the software. This implies the need of a software programming environment capable of putting together DSP modules and providing facilities to debug, verify and validate the code. The objective of the work is to provide such facilities as simulation and verification for developing DSP software applications. This led us to develop an extension toolkit, Epspectra, built upon Pspectra, one of the first toolkits available to design basic software radio applications on standard PC workstations. In this paper, we first present Epspectra, an Esterel-based extension of Pspectra that makes the design and implementation of portable DSP applications easier. It allows drastic reduction of testing and verification time while requiring relatively little expertise in formal verification methods. Second, we demonstrate the use of Epspectra, taking as an example the radio interface part of a GSM base station. We also present the verification procedures for the three safety properties of the implementation programs which have complex control-paths. These have to obey strict scheduling rules. In addition, Epspectra achieves the verification of the targeted application since the same model is used for the executable code generation and for the formal verification.
aDORe: a modular, standards-based Digital Object Repository
Venue: arXiv cs.DL 2005
Year: 2005

This paper describes the aDORe repository architecture, designed and implemented for ingesting, storing, and accessing a vast collection of Digital Objects at the Research Library of the Los Alamos National Laboratory. The aDORe architecture is highly modular and standards-based. In the architecture, the MPEG-21 Digital Item Declaration Language is used as the XML-based format to represent Digital Objects that can consist of multiple datastreams as Open Archival Information System Archival Information Packages (OAIS AIPs).Through an ingestion process, these OAIS AIPs are stored in a multitude of autonomous repositories. A Repository Index keeps track of the creation and location of all the autonomous repositories, whereas an Identifier Locator registers in which autonomous repository a given Digital Object or OAIS AIP resides. A front-end to the complete environment, the OAI-PMH Federator, is introduced for requesting OAIS Dissemination Information Packages (OAIS DIPs). These OAIS DIPs can be the stored OAIS AIPs themselves, or transformations thereof. This front-end allows OAI-PMH harvesters to recurrently and selectively collect batches of OAIS DIPs from aDORe, and hence to create multiple, parallel services using the collected objects. Another front-end, the OpenURL Resolver, is introduced for requesting OAIS Result Sets. An OAIS Result Set is a dissemination of an individual Digital Object or of its constituent datastreams. Both front-ends make use of an MPEG-21 Digital Item Processing Engine to apply services to OAIS AIPs, Digital Objects, or constituent datastreams that were specified in a dissemination request.
Scalability of Genetic Programming and Probabilistic Incremental Program Evolution
Venue: arXiv cs.NE 2005
Year: 2005

This paper discusses scalability of standard genetic programming (GP) and the probabilistic incremental program evolution (PIPE). To investigate the need for both effective mixing and linkage learning, two test problems are considered: ORDER problem, which is rather easy for any recombination-based GP, and TRAP or the deceptive trap problem, which requires the algorithm to learn interactions among subsets of terminals. The scalability results show that both GP and PIPE scale up polynomially with problem size on the simple ORDER problem, but they both scale up exponentially on the deceptive problem. This indicates that while standard recombination is sufficient when no interactions need to be considered, for some problems linkage learning is necessary. These results are in agreement with the lessons learned in the domain of binary-string genetic algorithms (GAs). Furthermore, the paper investigates the effects of introducing utnnecessary and irrelevant primitives on the performance of GP and PIPE.
Compatible Triangulations and Point Partitions by Series-Triangular Graphs
Venue: arXiv cs.CG 2005
Year: 2005

We introduce series-triangular graph embeddings and show how to partition point sets with them. This result is then used to improve the upper bound on the number of Steiner points needed to obtain compatible triangulations of point sets. The problem is generalized to finding compatible triangulations for more than two point sets and we show that such triangulations can be constructed with only a linear number of Steiner points added to each point set.
Generalised Bent Criteria for Boolean Functions (I)
Venue: arXiv cs.IT 2005
Year: 2005

Generalisations of the bent property of a boolean function are presented, by proposing spectral analysis with respect to a well-chosen set of local unitary transforms. Quadratic boolean functions are related to simple graphs and it is shown that the orbit generated by successive Local Complementations on a graph can be found within the transform spectra under investigation. The flat spectra of a quadratic boolean function are related to modified versions of its associated adjacency matrix.
Log Analysis Case Study Using LoGS
Venue: arXiv cs.CR 2005
Year: 2005

A very useful technique a network administrator can use to identify problematic network behavior is careful analysis of logs of incoming and outgoing network flows. The challenge one faces when attempting to undertake this course of action, though, is that large networks tend to generate an extremely large quantity of network traffic in a very short period of time, resulting in very large traffic logs which must be analyzed post-generation with an eye for contextual information which may reveal symptoms of problematic traffic. A better technique is to perform real-time log analysis using a real-time context-generating tool such as LoGS.
Improved Tag Set Design and Multiplexing Algorithms for Universal Arrays
Venue: arXiv cs.DS 2005
Year: 2005

In this paper we address two optimization problems arising in the design of genomic assays based on universal tag arrays. First, we address the universal array tag set design problem. For this problem, we extend previous formulations to incorporate antitag-to-antitag hybridization constraints in addition to constraints on antitag-to-tag hybridization specificity, establish a constructive upper bound on the maximum number of tags satisfying the extended constraints, and propose a simple greedy tag selection algorithm. Second, we give methods for improving the multiplexing rate in large-scale genomic assays by combining primer selection with tag assignment. Experimental results on simulated data show that this integrated optimization leads to reductions of up to 50% in the number of required arrays.
The Complexity of Computing the Size of an Interval
Venue: arXiv cs.CC 2005
Year: 2005

Given a p-order A over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if (x, y) is an element of A then |x| is polynomially bounded by |y|), an interval size function of A returns, for each string x in the universe, the number of strings in the interval between strings b(x) and t(x) (with respect to A), where b(x) and t(x) are functions that are polynomial-time computable in the length of x. By choosing sets of interval size functions based on feasibility requirements for their underlying p-orders, we obtain new characterizations of complexity classes. We prove that the set of all interval size functions whose underlying p-orders are polynomial-time decidable is exactly #P. We show that the interval size functions for orders with polynomial-time adjacency checks are closely related to the class FPSPACE(poly). Indeed, FPSPACE(poly) is exactly the class of all nonnegative functions that are an interval size function minus a polynomial-time computable function. We study two important functions in relation to interval size functions. The function #DIV maps each natural number n to the number of nontrivial divisors of n. We show that #DIV is an interval size function of a polynomial-time decidable partial p-order with polynomial-time adjacency checks. The function #MONSAT maps each monotone boolean formula F to the number of satisfying assignments of F. We show that #MONSAT is an interval size function of a polynomial-time decidable total p-order with polynomial-time adjacency checks. Finally, we explore the related notion of cluster computation.
Master Algorithms for Active Experts Problems based on Increasing Loss Values
Venue: arXiv cs.LG 2005
Year: 2005

We specify an experts algorithm with the following characteristics: (a) it uses only feedback from the actions actually chosen (bandit setup), (b) it can be applied with countably infinite expert classes, and (c) it copes with losses that may grow in time appropriately slowly. We prove loss bounds against an adaptive adversary. From this, we obtain master algorithms for "active experts problems", which means that the master's actions may influence the behavior of the adversary. Our algorithm can significantly outperform standard experts algorithms on such problems. Finally, we combine it with a universal expert class. This results in a (computationally infeasible) universal master algorithm which performs - in a certain sense - almost as well as any computable strategy, for any online problem.
Impulse Radio Systems with Multiple Types of Ultra-Wideband Pulses
Venue: arXiv cs.IT 2005
Year: 2005

Spectral properties and performance of multi-pulse impulse radio ultra-wideband systems with pulse-based polarity randomization are analyzed. Instead of a single type of pulse transmitted in each frame, multiple types of pulses are considered, which is shown to reduce the effects of multiple-access interference. First, the spectral properties of a multi-pulse impulse radio system is investigated. It is shown that the power spectral density is the average of spectral contents of different pulse shapes. Then, approximate closed-form expressions for bit error probability of a multi-pulse impulse radio system are derived for RAKE receivers in asynchronous multiuser environments. The theoretical and simulation results indicate that impulse radio systems that are more robust against multiple-access interference than a "classical" impulse radio system can be designed with multiple types of ultra-wideband pulses.
Fast generation of random connected graphs with prescribed degrees
Venue: arXiv cs.NI 2005
Year: 2005

We address here the problem of generating random graphs uniformly from the set of simple connected graphs having a prescribed degree sequence. Our goal is to provide an algorithm designed for practical use both because of its ability to generate very large graphs (efficiency) and because it is easy to implement (simplicity). We focus on a family of heuristics for which we prove optimality conditions, and show how this optimality can be reached in practice. We then propose a different approach, specifically designed for typical real-world degree distributions, which outperforms the first one. Assuming a conjecture which we state and argue rigorously, we finally obtain an log-linear algorithm, which, in spite of being very simple, improves the best known complexity.
An Objectives-Driven Process for Selecting Methods to Support Requirements Engineering Activities
Venue: arXiv cs.SE 2005
Year: 2005

This paper presents a framework that guides the requirements engineer in the implementation and execution of an effective requirements generation process. We achieve this goal by providing a well-defined requirements engineering model and a criteria based process for optimizing method selection for attendant activities. Our model, unlike other models, addresses the complete requirements generation process and consists of activities defined at more adequate levels of abstraction. Additionally, activity objectives are identified and explicitly stated - not implied as in the current models. Activity objectives are crucial as they drive the selection of methods for each activity. Our model also incorporates a unique approach to verification and validation that enhances quality and reduces the cost of generating requirements. To assist in the selection of methods, we have mapped commonly used methods to activities based on their objectives. In addition, we have identified method selection criteria and prescribed a reduced set of methods that optimize these criteria for each activity defined by our requirements generation process. Thus, the defined approach assists in the task of selecting methods by using selection criteria to reduce a large collection of potential methods to a smaller, manageable set. The model and the set of methods, taken together, provide the much needed guidance for the effective implementation and execution of the requirements generation process.
Minimal chordal sense of direction and circulant graphs
Venue: arXiv cs.DM 2005
Year: 2005

A sense of direction is an edge labeling on graphs that follows a globally consistent scheme and is known to considerably reduce the complexity of several distributed problems. In this paper, we study a particular instance of sense of direction, called a chordal sense of direction (CSD). In special, we identify the class of k-regular graphs that admit a CSD with exactly k labels (a minimal CSD). We prove that connected graphs in this class are Hamiltonian and that the class is equivalent to that of circulant graphs, presenting an efficient (polynomial-time) way of recognizing it when the graphs' degree k is fixed.
Prédiction de Performances pour les Communications Collectives
Venue: arXiv cs.DC 2005
Year: 2005

Des travaux récents visent l'optimisation des opérations de communication collective dans les environnements de type grille de calcul. La solution la plus répandue est la séparation des communications internes et externes à chaque grappe, mais cela n'exclut pas le découpage des communications en plusieurs couches, pratique efficace démontrée par Karonis et al. [10]. Dans les deux cas, la prédiction des performances est un facteur essentiel, soit pour le réglage fin des paramètres de communication, soit pour le calcul de la distribution et de la hiérarchie des communications. Pour cela, il est très important d'avoir des modèles précis des communications collectives, lesquels seront utilisés pour prédire ces performances. Cet article décrit notre expérience sur la modélisation des opérations de communication collective. Nous présentons des modèles de communication pour différents patrons de communication collective comme un vers plusieurs, un vers plusieurs personnalisé et plusieurs vers plusieurs. Pour évaluer la précision des modèles, nous comparons les prédictions obtenues avec les résultats des expérimentations effectuées sur deux environnements réseaux différents, Fast Ethernet et Myrinet.
Duality Bounds on the Cut-Off Rate with Applications to Ricean Fading
Venue: arXiv cs.IT 2005
Year: 2005

We propose a technique to derive upper bounds on Gallager's cost-constrained random coding exponent function. Applying this technique to the non-coherent peak-power or average-power limited discrete time memoryless Ricean fading channel, we obtain the high signal-to-noise ratio (SNR) expansion of this channel's cut-off rate. At high SNR the gap between channel capacity and the cut-off rate approaches a finite limit. This limit is approximately 0.26 nats per channel-use for zero specular component (Rayleigh) fading and approaches 0.39 nats per channel-use for very large specular components. We also compute the asymptotic cut-off rate of a Rayleigh fading channel when the receiver has access to some partial side information concerning the fading. It is demonstrated that the cut-off rate does not utilize the side information as efficiently as capacity, and that the high SNR gap between the two increases to infinity as the imperfect side information becomes more and more precise.
The Effect of Use and Access on Citations
Venue: arXiv cs.DL 2005
Year: 2005

It has been shown (S. Lawrence, 2001, Nature, 411, 521) that journal articles which have been posted without charge on the internet are more heavily cited than those which have not been. Using data from the NASA Astrophysics Data System (ads.harvard.edu) and from the ArXiv e-print archive at Cornell University (arXiv.org) we examine the causes of this effect.
Complexity and Approximation of Fixing Numerical Attributes in Databases Under Integrity Constraints
Venue: arXiv cs.DB 2005
Year: 2005

Consistent query answering is the problem of computing the answers from a database that are consistent with respect to certain integrity constraints that the database as a whole may fail to satisfy. Those answers are characterized as those that are invariant under minimal forms of restoring the consistency of the database. In this context, we study the problem of repairing databases by fixing integer numerical values at the attribute level with respect to denial and aggregation constraints. We introduce a quantitative definition of database fix, and investigate the complexity of several decision and optimization problems, including DFP, i.e. the existence of fixes within a given distance from the original instance, and CQA, i.e. deciding consistency of answers to aggregate conjunctive queries under different semantics. We provide sharp complexity bounds, identify relevant tractable cases; and introduce approximation algorithms for some of those that are intractable. More specifically, we obtain results like undecidability of existence of fixes for aggregation constraints; MAXSNP-hardness of DFP, but a good approximation algorithm for a relevant special case; and intractability but good approximation for CQA for aggregate queries for one database atom denials (plus built-ins).