OpenRaiser/Intern-Atlas huggingface dataset:
Mapping Equivalence for Symbolic Sequences: Theory and Applications
Venue: arXiv cs.IT 2009
Year: 2009

Processing of symbolic sequences represented by mapping of symbolic data into numerical signals is commonly used in various applications. It is a particularly popular approach in genomic and proteomic sequence analysis. Numerous mappings of symbolic sequences have been proposed for various applications. It is unclear however whether the processing of symbolic data provides an artifact of the numerical mapping or is an inherent property of the symbolic data. This issue has been long ignored in the engineering and scientific literature. It is possible that many of the results obtained in symbolic signal processing could be a byproduct of the mapping and might not shed any light on the underlying properties embedded in the data. Moreover, in many applications, conflicting conclusions may arise due to the choice of the mapping used for numerical representation of symbolic data. In this paper, we present a novel framework for the analysis of the equivalence of the mappings used for numerical representation of symbolic data. We present strong and weak equivalence properties and rely on signal correlation to characterize equivalent mappings. We derive theoretical results which establish conditions for consistency among numerical mappings of symbolic data. Furthermore, we introduce an abstract mapping model for symbolic sequences and extend the notion of equivalence to an algebraic framework. Finally, we illustrate our theoretical results by application to DNA sequence analysis.
Dirty Paper Coding for the MIMO Cognitive Radio Channel with Imperfect CSIT
Venue: arXiv cs.IT 2009
Year: 2009

A Dirty Paper Coding (DPC) based transmission scheme for the Gaussian multiple-input multiple-output (MIMO) cognitive radio channel (CRC) is studied when there is imperfect and perfect channel knowledge at the transmitters (CSIT) and the receivers, respectively. In particular, the problem of optimizing the sum-rate of the MIMO CRC over the transmit covariance matrices is dealt with. Such an optimization, under the DPC-based transmission strategy, needs to be performed jointly with an optimization over the inflation factor. To this end, first the problem of determination of inflation factor over the MIMO channel $Y=H_1 X + H_2 S + Z$ with imperfect CSIT is investigated. For this problem, two iterative algorithms, which generalize the corresponding algorithms proposed for the channel $Y=H(X+S)+Z$, are developed. Later, the necessary conditions for maximizing the sum-rate of the MIMO CRC over the transmit covariances for a given choice of inflation factor are derived. Using these necessary conditions and the algorithms for the determination of the inflation factor, an iterative, numerical algorithm for the joint optimization is proposed. Some interesting observations are made from the numerical results obtained from the algorithm. Furthermore, the high-SNR sum-rate scaling factor achievable over the CRC with imperfect CSIT is obtained.
A Neural Network Classifier of Volume Datasets
Venue: arXiv cs.GR 2009
Year: 2009

Many state-of-the art visualization techniques must be tailored to the specific type of dataset, its modality (CT, MRI, etc.), the recorded object or anatomical region (head, spine, abdomen, etc.) and other parameters related to the data acquisition process. While parts of the information (imaging modality and acquisition sequence) may be obtained from the meta-data stored with the volume scan, there is important information which is not stored explicitly (anatomical region, tracing compound). Also, meta-data might be incomplete, inappropriate or simply missing. This paper presents a novel and simple method of determining the type of dataset from previously defined categories. 2D histograms based on intensity and gradient magnitude of datasets are used as input to a neural network, which classifies it into one of several categories it was trained with. The proposed method is an important building block for visualization systems to be used autonomously by non-experts. The method has been tested on 80 datasets, divided into 3 classes and a "rest" class. A significant result is the ability of the system to classify datasets into a specific class after being trained with only one dataset of that class. Other advantages of the method are its easy implementation and its high computational performance.
Longest Wait First for Broadcast Scheduling
Venue: arXiv cs.DS 2009
Year: 2009

We consider online algorithms for broadcast scheduling. In the pull-based broadcast model there are $n$ unit-sized pages of information at a server and requests arrive online for pages. When the server transmits a page $p$, all outstanding requests for that page are satisfied. The longest-wait-first} (LWF) algorithm is a natural algorithm that has been shown to have good empirical performance. In this paper we make two main contributions to the analysis of LWF and broadcast scheduling. \begin{itemize} \item We give an intuitive and easy to understand analysis of LWF which shows that it is $O(1/\eps^2)$-competitive for average flow-time with $(4+\eps)$ speed. Using a more involved analysis, we show that LWF is $O(1/\eps^3)$-competitive for average flow-time with $(3.4+ε)$ speed. \item We show that a natural extension of LWF is O(1)-speed O(1)-competitive for more general objective functions such as average delay-factor and $L_k$ norms of delay-factor (for fixed $k$). \end{itemize}
Oscillations and Random Perturbations of a FitzHugh-Nagumo System
Venue: arXiv cs.DS 2009
Year: 2009

We consider a stochastic perturbation of a FitzHugh-Nagumo system. We show that it is possible to generate oscillations for values of parameters which do not allow oscillations for the deterministic system. We also study the appearance of a new equilibrium point and new bifurcation parameters due to the noisy component.
Disjoint LDPC Coding for Gaussian Broadcast Channels
Venue: arXiv cs.IT 2009
Year: 2009

Low-density parity-check (LDPC) codes have been used for communication over a two-user Gaussian broadcast channel. It has been shown in the literature that the optimal decoding of such system requires joint decoding of both user messages at each user. Also, a joint code design procedure should be performed. We propose a method which uses a novel labeling strategy and is based on the idea behind the bit-interleaved coded modulation. This method does not require joint decoding and/or joint code optimization. Thus, it reduces the overall complexity of near-capacity coding in broadcast channels. For different rate pairs on the boundary of the capacity region, pairs of LDPC codes are designed to demonstrate the success of this technique.
Predicate Transformers, (co)Monads and Resolutions
Venue: arXiv cs.LO 2009
Year: 2009

This short note contains random thoughts about a factorization theorem for closure/interior operators on a powerset which is reminiscent to the notion of resolution for a monad/comonad. The question originated from formal topology but is interesting in itself. The result holds constructively (even if it classically has several variations); but usually not predicatively (in the sense that the interpolant will no be given by a set). For those not familiar with predicativity issues, we look at a ``classical'' version where we bound the size of the interpolant.
Lower Bounds for Pinning Lines by Balls
Venue: arXiv cs.CG 2009
Year: 2009

A line L is a transversal to a family F of convex objects in R^d if it intersects every member of F. In this paper we show that for every integer d>2 there exists a family of 2d-1 pairwise disjoint unit balls in R^d with the property that every subfamily of size 2d-2 admits a transversal, yet any line misses at least one member of the family. This answers a question of Danzer from 1957.
Approximating Scheduling Machines with Capacity Constraints
Venue: arXiv cs.DS 2009
Year: 2009

In the Scheduling Machines with Capacity Constraints problem, we are given k identical machines, each of which can process at most m_i jobs. M jobs are also given, where job j has a non-negative processing time length t_j >= 0. The task is to find a schedule such that the makespan is minimized and the capacity constraints are met. In this paper, we present a 3-approximation algorithm using an extension of Iterative Rounding Method introduced by Jain. To the best of the authors' knowledge, this is the first attempt to apply Iterative Rounding Method to scheduling problem with capacity constraints.
Deformable Model with a Complexity Independent from Image Resolution
Venue: arXiv cs.CV 2009
Year: 2009

We present a parametric deformable model which recovers image components with a complexity independent from the resolution of input images. The proposed model also automatically changes its topology and remains fully compatible with the general framework of deformable models. More precisely, the image space is equipped with a metric that expands salient image details according to their strength and their curvature. During the whole evolution of the model, the sampling of the contour is kept regular with respect to this metric. By this way, the vertex density is reduced along most parts of the curve while a high quality of shape representation is preserved. The complexity of the deformable model is thus improved and is no longer influenced by feature-preserving changes in the resolution of input images. Building the metric requires a prior estimation of contour curvature. It is obtained using a robust estimator which investigates the local variations in the orientation of image gradient. Experimental results on both computer generated and biomedical images are presented to illustrate the advantages of our approach.
Convex shapes and convergence speed of discrete tangent estimators
Venue: arXiv cs.DM 2009
Year: 2009

Discrete geometric estimators aim at estimating geometric characteristics of a shape with only its digitization as input data. Such an estimator is multigrid convergent when its estimates tend toward the geometric characteristics of the shape as the digitization step h tends toward 0. This paper studies the multigrid convergence of tangent estimators based on maximal digital straight segment recognition. We show that such estimators are multigrid convergent for some family of convex shapes and that their speed of convergence is on average O(h^(2/3)). Experiments confirm this result and suggest that the bound is tight.
Computational Power of P Systems with Small Size Insertion and Deletion Rules
Venue: arXiv cs.CC 2009
Year: 2009

Recent investigations show insertion-deletion systems of small size that are not complete and cannot generate all recursively enumerable languages. However, if additional computational distribution mechanisms like P systems are added, then the computational completeness is achieved in some cases. In this article we take two insertion-deletion systems that are not computationally complete, consider them in the framework of P systems and show that the computational power is strictly increased by proving that any recursively enumerable language can be generated. At the end some open problems are presented.
Small Turing universal signal machines
Venue: arXiv cs.CC 2009
Year: 2009

This article aims at providing signal machines as small as possible able to perform any computation (in the classical understanding). After presenting signal machines, it is shown how to get universal ones from Turing machines, cellular-automata and cyclic tag systems. Finally a halting universal signal machine with 13 meta-signals and 21 collision rules is presented.
Goal-oriented Data Warehouse Quality Measurement
Venue: arXiv cs.SE 2009
Year: 2009

Requirements engineering is known to be a key factor for the success of software projects. Inside this discipline, goal-oriented requirements engineering approaches have shown specially suitable to deal with projects where it is necessary to capture the alignment between system requirements and stakeholders' needs, as is the case of data-warehousing projects. However, the mere alignment of data-warehouse system requirements with business goals is not enough to assure better data-warehousing products; measures and techniques are also needed to assure the data-warehouse quality. In this paper, we provide a modelling framework for data-warehouse quality measurement (i*DWQM). This framework, conceived as an i* extension, provides support for the definition of data-warehouse requirements analysis models that include quantifiable quality scenarios, defined in terms of well-formed measures. This extension has been defined by means of a UML profiling architecture. The resulting framework has been implemented in the Eclipse development platform.
The Pagoda Sequence: a Ramble through Linear Complexity, Number Walls, D0L Sequences, Finite State Automata, and Aperiodic Tilings
Venue: arXiv cs.DM 2009
Year: 2009

We review the concept of the number wall as an alternative to the traditional linear complexity profile (LCP), and sketch the relationship to other topics such as linear feedback shift-register (LFSR) and context-free Lindenmayer (D0L) sequences. A remarkable ternary analogue of the Thue-Morse sequence is introduced having deficiency 2 modulo 3, and this property verified via the re-interpretation of the number wall as an aperiodic plane tiling.
Optimal Constrained Resource Allocation Strategies under Low Risk Circumstances
Venue: arXiv cs.DS 2009
Year: 2009

In this paper we consider multiple constrained resource allocation problems, where the constraints can be specified by formulating activity dependency restrictions or by using game-theoretic models. All the problems are focused on generic resources, with a few exceptions which consider financial resources in particular. The problems consider low-risk circumstances and the values of the uncertain variables which are used by the algorithms are the expected values of the variables. For each of the considered problems we propose novel algorithmic solutions for computing optimal resource allocation strategies. The presented solutions are optimal or near-optimal from the perspective of their time complexity. The considered problems have applications in a broad range of domains, like workflow scheduling in industry (e.g. in the mining and metallurgical industry) or the financial sector, motion planning, facility location and data transfer or job scheduling and resource management in Grids, clouds or other distributed systems.
On the Beamforming Design for Efficient Interference Alignment
Venue: arXiv cs.IT 2009
Year: 2009

An efficient interference alignment (IA) scheme is developed for $K$-user single-input single-output frequency selective fading interference channels. The main idea is to steer the transmit beamforming matrices such that at each receiver the subspace dimensions occupied by interference-free desired streams are asymptotically the same as those occupied by all interferences. Our proposed scheme achieves a higher multiplexing gain at any given number of channel realizations in comparison with the original IA scheme, which is known to achieve the optimal multiplexing gain asymptotically.
High Transmission Bit Rate of A thermal Arrayed Waveguide Grating (AWG) Module in Passive Optical Networks
Venue: arXiv cs.NI 2009
Year: 2009

In the present paper, high transmission bit rate of a thermal arrayed waveguide grating (AWG) which is composed of lithium niobate (LiNbO3)/polymethyl metha acrylate (PMMA) hybrid materials on a silicon substrate in Passive Optical Networks (PONs) has parametrically analyzed and investigated over wide range of the affecting parameters. We have theoretically investigated the temperature dependent wavelength shift of the arrayed waveguide grating (AWG) depends on the refractive-indices of the materials and the size of the waveguide. A thermalization of the AWG can be realized by selecting proper values of the material and structural parameters of the device. Moreover, we have analyzed the data transmission bit rate of a thermal AWG in passsive optical networks (PONs) based on Maximum Time Division Multiplexing (MTDM) technique.
Energy Efficiency in the Low-SNR Regime under Queueing Constraints and Channel Uncertainty
Venue: arXiv cs.IT 2009
Year: 2009

Energy efficiency of fixed-rate transmissions is studied in the presence of queueing constraints and channel uncertainty. It is assumed that neither the transmitter nor the receiver has channel side information prior to transmission. The channel coefficients are estimated at the receiver via minimum mean-square-error (MMSE) estimation with the aid of training symbols. It is further assumed that the system operates under statistical queueing constraints in the form of limitations on buffer violation probabilities. The optimal fraction of power allocated to training is identified. Spectral efficiency--bit energy tradeoff is analyzed in the low-power and wideband regimes by employing the effective capacity formulation. In particular, it is shown that the bit energy increases without bound in the low-power regime as the average power vanishes. A similar conclusion is reached in the wideband regime if the number of noninteracting subchannels grow without bound with increasing bandwidth. On the other hand, it is proven that if the number of resolvable independent paths and hence the number of noninteracting subchannels remain bounded as the available bandwidth increases, the bit energy diminishes to its minimum value in the wideband regime. For this case, expressions for the minimum bit energy and wideband slope are derived. Overall, energy costs of channel uncertainty and queueing constraints are identified, and the impact of multipath richness and sparsity is determined.
Using the General Intensional Programming System (GIPSY) for Evaluation of Higher-Order Intensional Logic (HOIL) Expressions
Venue: arXiv cs.PL 2009
Year: 2009

The General Intensional Programming System (GIPSY) has been built around the Lucid family of intensional programming languages that rely on the higher-order intensional logic (HOIL) to provide context-oriented multidimensional reasoning of intensional expressions. HOIL combines functional programming with various intensional logics to allow explicit context expressions to be evaluated as first-class values that can be passed as parameters to functions and return as results with an appropriate set of operators defined on contexts. GIPSY's frameworks are implemented in Java as a collection of replaceable components for the compilers of various Lucid dialects and the demand-driven eductive evaluation engine that can run distributively. GIPSY provides support for hybrid programming models that couple intensional and imperative languages for a variety of needs. Explicit context expressions limit the scope of evaluation of math expressions (effectively a Lucid program is a mathematics or physics expression constrained by the context) in tensor physics, regular math in multiple dimensions, etc., and for cyberforensic reasoning as one of the use-cases of interest. Thus, GIPSY is a support testbed for HOIL-based languages some of which enable such reasoning, as in formal cyberforensic case analysis with event reconstruction. In this paper we discuss the GIPSY architecture, its evaluation engine and example use-cases.
Reasoning About a Service-oriented Programming Paradigm
Venue: arXiv cs.PL 2009
Year: 2009

This paper is about a new way for programming distributed applications: the service-oriented one. It is a concept paper based upon our experience in developing a theory and a language for programming services. Both the theoretical formalization and the language interpreter showed us the evidence that a new programming paradigm exists. In this paper we illustrate the basic features it is characterized by.
Fairness as a QoS Measure for Web Services
Venue: arXiv cs.SE 2009
Year: 2009

Service Oriented Architectures (SOAs) are component-based architectures, characterized by reusability, modularization and composition, usually offered by HTTP (web services) and often equipped with a Quality of Services (QoS) measure. In order to guarantee the fairness property to each client requesting a service, we propose a fair version of the (Soft) Concurrent Constraint language to deal with the negotiation phases of the Service Level Agreement (SLA) protocol.
Quantitative testing semantics for non-interleaving
Venue: arXiv cs.LO 2009
Year: 2009

This paper presents a non-interleaving denotational semantics for the ?-calculus. The basic idea is to define a notion of test where the outcome is not only whether a given process passes a given test, but also in how many different ways it can pass it. More abstractly, the set of possible outcomes for tests forms a semiring, and the set of process interpretations appears as a module over this semiring, in which basic syntactic constructs are affine operators. This notion of test leads to a trace semantics in which traces are partial orders, in the style of Mazurkiewicz traces, extended with readiness information. Our construction has standard may- and must-testing as special cases.
Automatic Spatially-Adaptive Balancing of Energy Terms for Image Segmentation
Venue: arXiv cs.CV 2009
Year: 2009

Image segmentation techniques are predominately based on parameter-laden optimization. The objective function typically involves weights for balancing competing image fidelity and segmentation regularization cost terms. Setting these weights suitably has been a painstaking, empirical process. Even if such ideal weights are found for a novel image, most current approaches fix the weight across the whole image domain, ignoring the spatially-varying properties of object shape and image appearance. We propose a novel technique that autonomously balances these terms in a spatially-adaptive manner through the incorporation of image reliability in a graph-based segmentation framework. We validate on synthetic data achieving a reduction in mean error of 47% (p-value << 0.05) when compared to the best fixed parameter segmentation. We also present results on medical images (including segmentations of the corpus callosum and brain tissue in MRI data) and on natural images.
Reasoning About Knowledge of Unawareness Revisited
Venue: arXiv cs.AI 2009
Year: 2009

In earlier work, we proposed a logic that extends the Logic of General Awareness of Fagin and Halpern [1988] by allowing quantification over primitive propositions. This makes it possible to express the fact that an agent knows that there are some facts of which he is unaware. In that logic, it is not possible to model an agent who is uncertain about whether he is aware of all formulas. To overcome this problem, we keep the syntax of the earlier paper, but allow models where, with each world, a possibly different language is associated. We provide a sound and complete axiomatization for this logic and show that, under natural assumptions, the quantifier-free fragment of the logic is characterized by exactly the same axioms as the logic of Heifetz, Meier, and Schipper [2008].
A Logical Characterization of Iterated Admissibility
Venue: arXiv cs.AI 2009
Year: 2009

Brandenburger, Friedenberg, and Keisler provide an epistemic characterization of iterated admissibility (i.e., iterated deletion of weakly dominated strategies) where uncertainty is represented using LPSs (lexicographic probability sequences). Their characterization holds in a rich structure called a complete structure, where all types are possible. Here, a logical charaacterization of iterated admisibility is given that involves only standard probability and holds in all structures, not just complete structures. A stronger notion of strong admissibility is then defined. Roughly speaking, strong admissibility is meant to capture the intuition that "all the agent knows" is that the other agents satisfy the appropriate rationality assumptions. Strong admissibility makes it possible to relate admissibility, canonical structures (as typically considered in completeness proofs in modal logic), complete structures, and the notion of ``all I know''.