OpenRaiser/Intern-Atlas huggingface dataset:
Polyomino-Based Digital Halftoning
Venue: arXiv cs.GR 2008
Year: 2008

In this work, we present a new method for generating a threshold structure. This kind of structure can be advantageously used in various halftoning algorithms such as clustered-dot or dispersed-dot dithering, error diffusion with threshold modulation, etc. The proposed method is based on rectifiable polyominoes -- a non-periodic hierarchical structure, which tiles the Euclidean plane with no gaps. Each polyomino contains a fixed number of discrete threshold values. Thanks to its inherent non-periodic nature combined with off-line optimization of threshold values, our polyomino-based threshold structure shows blue-noise spectral properties. The halftone images produced with this threshold structure have high visual quality. Although the proposed method is general, and can be applied on any polyomino tiling, we consider one particular case: tiling with G-hexominoes. We compare our polyomino-based threshold structure with the best known state-of-the-art methods for generation threshold matrices, and conclude considerable improvement achieved with our method.
The Wadge Hierarchy of Deterministic Tree Languages
Venue: arXiv cs.LO 2008
Year: 2008

We provide a complete description of the Wadge hierarchy for deterministically recognisable sets of infinite trees. In particular we give an elementary procedure to decide if one deterministic tree language is continuously reducible to another. This extends Wagner's results on the hierarchy of omega-regular languages of words to the case of trees.
The Impact of QoS Constraints on the Energy Efficiency of Fixed-Rate Wireless Transmissions
Venue: arXiv cs.IT 2008
Year: 2008

Transmission over wireless fading channels under quality of service (QoS) constraints is studied when only the receiver has channel side information. Being unaware of the channel conditions, transmitter is assumed to send the information at a fixed rate. Under these assumptions, a two-state (ON-OFF) transmission model is adopted, where information is transmitted reliably at a fixed rate in the ON state while no reliable transmission occurs in the OFF state. QoS limitations are imposed as constraints on buffer violation probabilities, and effective capacity formulation is used to identify the maximum throughput that a wireless channel can sustain while satisfying statistical QoS constraints. Energy efficiency is investigated by obtaining the bit energy required at zero spectral efficiency and the wideband slope in both wideband and low-power regimes assuming that the receiver has perfect channel side information (CSI). In both wideband and low-power regimes, the increased energy requirements due to the presence of QoS constraints are quantified. Comparisons with variable-rate/fixed-power and variable-rate/variable-power cases are given. Energy efficiency is further analyzed in the presence of channel uncertainties. The optimal fraction of power allocated to training is identified under QoS constraints. It is proven that the minimum bit energy in the low-power regime is attained at a certain nonzero power level below which bit energy increases without bound with vanishing power.
Identification of parameters underlying emotions and a classification of emotions
Venue: arXiv cs.AI 2008
Year: 2008

The standard classification of emotions involves categorizing the expression of emotions. In this paper, parameters underlying some emotions are identified and a new classification based on these parameters is suggested.
The convex hull of a regular set of integer vectors is polyhedral and effectively computable
Venue: arXiv cs.CG 2008
Year: 2008

Number Decision Diagrams (NDD) provide a natural finite symbolic representation for regular set of integer vectors encoded as strings of digit vectors (least or most significant digit first). The convex hull of the set of vectors represented by a NDD is proved to be an effectively computable convex polyhedron.
Control software analysis, part II: Closed-loop analysis
Venue: arXiv cs.SE 2008
Year: 2008

The analysis and proper documentation of the properties of closed-loop control software presents many distinct aspects from the analysis of the same software running open-loop. Issues of physical system representations arise, and it is desired that such representations remain independent from the representations of the control program. For that purpose, a concurrent program representation of the plant and the control processes is proposed, although the closed-loop system is sufficiently serialized to enable a sequential analysis. While dealing with closed-loop system properties, it is also shown by means of examples how special treatment of nonlinearities extends from the analysis of control specifications to code analysis.
A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two
Venue: arXiv cs.CC 2008
Year: 2008

We design a 3/2 approximation algorithm for the Generalized Steiner Tree problem (GST) in metrics with distances 1 and 2. This is the first polynomial time approximation algorithm for a wide class of non-geometric metric GST instances with approximation factor below 2.
A Sparse Flat Extension Theorem for Moment Matrices
Venue: arXiv cs.SC 2008
Year: 2008

In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its border, assuming that this set is connected to 1. When formulated in a basis-free setting, this gives an equivalent result for truncated Hankel operators.
Learning Low Rank Matrices from O(n) Entries
Venue: arXiv cs.DS 2008
Year: 2008

How many random entries of an n by m, rank r matrix are necessary to reconstruct the matrix within an accuracy d? We address this question in the case of a random matrix with bounded rank, whereby the observed entries are chosen uniformly at random. We prove that, for any d>0, C(r,d)n observations are sufficient. Finally we discuss the question of reconstructing the matrix efficiently, and demonstrate through extensive simulations that this task can be accomplished in nPoly(log n) operations, for small rank.
Prediction of Platinum Prices Using Dynamically Weighted Mixture of Experts
Venue: arXiv cs.AI 2008
Year: 2008

Neural networks are powerful tools for classification and regression in static environments. This paper describes a technique for creating an ensemble of neural networks that adapts dynamically to changing conditions. The model separates the input space into four regions and each network is given a weight in each region based on its performance on samples from that region. The ensemble adapts dynamically by constantly adjusting these weights based on the current performance of the networks. The data set used is a collection of financial indicators with the goal of predicting the future platinum price. An ensemble with no weightings does not improve on the naive estimate of no weekly change; our weighting algorithm gives an average percentage error of 63% for twenty weeks of prediction.
Sparse Component Analysis (SCA) in Random-valued and Salt and Pepper Noise Removal
Venue: arXiv cs.CV 2008
Year: 2008

In this paper, we propose a new method for impulse noise removal from images. It uses the sparsity of images in the Discrete Cosine Transform (DCT) domain. The zeros in this domain give us the exact mathematical equation to reconstruct the pixels that are corrupted by random-value impulse noises. The proposed method can also detect and correct the corrupted pixels. Moreover, in a simpler case that salt and pepper noise is the brightest and darkest pixels in the image, we propose a simpler version of our method. In addition to the proposed method, we suggest a combination of the traditional median filter method with our method to yield better results when the percentage of the corrupted samples is high.
New parallel programming language design: a bridge between brain models and multi-core/many-core computers?
Venue: arXiv cs.PL 2008
Year: 2008

The recurrent theme of this paper is that sequences of long temporal patterns as opposed to sequences of simple statements are to be fed into computation devices, being them (new proposed) models for brain activity or multi-core/many-core computers. In such models, parts of these long temporal patterns are already committed while other are predicted. This combination of matching patterns and making predictions appears as a key element in producing intelligent processing in brain models and getting efficient speculative execution on multi-core/many-core computers. A bridge between these far-apart models of computation could be provided by appropriate design of massively parallel, interactive programming languages. Agapia is a recently proposed language of this kind, where user controlled long high-level temporal structures occur at the interaction interfaces of processes. In this paper Agapia is used to link HTMs brain models with TRIPS multi-core/many-core architectures.
Tree-width of hypergraphs and surface duality
Venue: arXiv cs.DM 2008
Year: 2008

In Graph Minor III, Robertson and Seymour conjecture that the tree-width of a planar graph and that of its dual differ by at most one. We prove that given a hypergraph H on a surface of Euler genus k, the tree-width of H^* is at most the maximum of tw(H) + 1 + k and the maximum size of a hyperedge of H^*.
A Computational Model to Disentangle Semantic Information Embedded in Word Association Norms
Venue: arXiv cs.CL 2008
Year: 2008

Two well-known databases of semantic relationships between pairs of words used in psycholinguistics, feature-based and association-based, are studied as complex networks. We propose an algorithm to disentangle feature based relationships from free association semantic networks. The algorithm uses the rich topology of the free association semantic network to produce a new set of relationships between words similar to those observed in feature production norms.
Mode Switching for MIMO Broadcast Channel Based on Delay and Channel Quantization
Venue: arXiv cs.IT 2008
Year: 2008

Imperfect channel state information degrades the performance of multiple-input multiple-output (MIMO) communications; its effect on single-user (SU) and multi-user (MU) MIMO transmissions are quite different. In particular, MU-MIMO suffers from residual inter-user interference due to imperfect channel state information while SU-MIMO only suffers from a power loss. This paper compares the throughput loss of both SU and MU MIMO on the downlink due to delay and channel quantization. Accurate closed-form approximations are derived for the achievable rates for both SU and MU MIMO. It is shown that SU-MIMO is relatively robust to delayed and quantized channel information, while MU MIMO with zero-forcing precoding loses spatial multiplexing gain with a fixed delay or fixed codebook size. Based on derived achievable rates, a mode switching algorithm is proposed that switches between SU and MU MIMO modes to improve the spectral efficiency, based on the average signal-to-noise ratio (SNR), the normalized Doppler frequency, and the channel quantization codebook size. The operating regions for SU and MU modes with different delays and codebook sizes are determined, which can be used to select the preferred mode. It is shown that the MU mode is active only when the normalized Doppler frequency is very small and the codebook size is large.
Approximate conditional distributions of distances between nodes in a two-dimensional sensor network
Venue: arXiv cs.NI 2008
Year: 2008

When we represent a network of sensors in Euclidean space by a graph, there are two distances between any two nodes that we may consider. One of them is the Euclidean distance. The other is the distance between the two nodes in the graph, defined to be the number of edges on a shortest path between them. In this paper, we consider a network of sensors placed uniformly at random in a two-dimensional region and study two conditional distributions related to these distances. The first is the probability distribution of distances in the graph, conditioned on Euclidean distances; the other is the probability density function associated with Euclidean distances, conditioned on distances in the graph. We study these distributions both analytically (when feasible) and by means of simulations. To the best of our knowledge, our results constitute the first of their kind and open up the possibility of discovering improved solutions to certain sensor-network problems, as for example sensor localization.
On Successive Refinement for the Kaspi/Heegard-Berger Problem
Venue: arXiv cs.IT 2008
Year: 2008

Consider a source that produces independent copies of a triplet of jointly distributed random variables, $\{X_{i},Y_{i},Z_{i}\}_{i=1}^{\infty}$. The process $\{X_{i}\}$ is observed at the encoder, and is supposed to be reproduced at two decoders, where $\{Y_{i}\}$ and $\{Z_{i}\}$ are observed, in either a causal or non-causal manner. The communication between the encoder and the decoders is carried in two successive stages. In the first stage, the transmission is available to both decoders and the source is reconstructed according to the received bit-stream and the individual side information (SI). In the second stage, additional information is sent to both decoders and the source reconstructions are refined according to the transmissions at both stages and the available SI. It is desired to find the necessary and sufficient conditions on the communication rates between the encoder and decoders, so that the distortions incurred (at each stage) will not exceed given thresholds. For the case of non-degraded causal SI at the decoders, an exact single-letter characterization of the achievable region is derived for the case of pure source-coding. Then, for the case of communication carried over independent DMS's with random states known causally/non-causally at the encoder and with causal SI about the source at the decoders, a single-letter characterization of all achievable distortion in both stages is provided and it is shown that the separation theorem holds. Finally, for non-causal degraded SI, inner and outer bounds to the achievable rate-distortion region are derived. These bounds are shown to be tight for certain cases of reconstruction requirements at the decoders, thereby shading some light on the problem of successive refinement with non-degraded SI at the decoders.
Worst-Case Optimal Adaptive Prefix Coding
Venue: arXiv cs.IT 2008
Year: 2008

A common complaint about adaptive prefix coding is that it is much slower than static prefix coding. Karpinski and Nekrich recently took an important step towards resolving this: they gave an adaptive Shannon coding algorithm that encodes each character in (O (1)) amortized time and decodes it in (O (\log H)) amortized time, where $H$ is the empirical entropy of the input string $s$. For comparison, Gagie's adaptive Shannon coder and both Knuth's and Vitter's adaptive Huffman coders all use (Θ(H)) amortized time for each character. In this paper we give an adaptive Shannon coder that both encodes and decodes each character in (O (1)) worst-case time. As with both previous adaptive Shannon coders, we store $s$ in at most ((H + 1) |s| + o (|s|)) bits. We also show that this encoding length is worst-case optimal up to the lower order term.
Automatic Construction of Lightweight Domain Ontologies for Chemical Engineering Risk Management
Venue: arXiv cs.AI 2008
Year: 2008

The need for domain ontologies in mission critical applications such as risk management and hazard identification is becoming more and more pressing. Most research on ontology learning conducted in the academia remains unrealistic for real-world applications. One of the main problems is the dependence on non-incremental, rare knowledge and textual resources, and manually-crafted patterns and rules. This paper reports work in progress aiming to address such undesirable dependencies during ontology construction. Initial experiments using a working prototype of the system revealed promising potentials in automatically constructing high-quality domain ontologies using real-world texts.
Business processes integration and performance indicators in a PLM
Venue: arXiv cs.DB 2008
Year: 2008

In an economic environment more and more competitive, the effective management of information and knowledge is a strategic issue for industrial enterprises. In the global marketplace, companies must use reactive strategies and reduce their products development cycle. In this context, the PLM (Product Lifecycle Management) is considered as a key component of the information system. The aim of this paper is to present an approach to integrate Business Processes in a PLM system. This approach is implemented in automotive sector with second-tier subcontractor
Context-aware adaptation for group communication support applications with dynamic architecture
Venue: arXiv cs.SE 2008
Year: 2008

In this paper, we propose a refinement-based adaptation approach for the architecture of distributed group communication support applications. Unlike most of previous works, our approach reaches implementable, context-aware and dynamically adaptable architectures. To model the context, we manage simultaneously four parameters that influence Qos provided by the application. These parameters are: the available bandwidth, the exchanged data communication priority, the energy level and the available memory for processing. These parameters make it possible to refine the choice between the various architectural configurations when passing from a given abstraction level to the lower level which implements it. Our approach allows the importance degree associated with each parameter to be adapted dynamically. To implement adaptation, we switch between the various configurations of the same level, and we modify the state of the entities of a given configuration when necessary. We adopt the direct and mediated Producer- Consumer architectural styles and graphs for architecture modelling. In order to validate our approach we elaborate a simulation model.
Finding Still Lifes with Memetic/Exact Hybrid Algorithms
Venue: arXiv cs.NE 2008
Year: 2008

The maximum density still life problem (MDSLP) is a hard constraint optimization problem based on Conway's game of life. It is a prime example of weighted constrained optimization problem that has been recently tackled in the constraint-programming community. Bucket elimination (BE) is a complete technique commonly used to solve this kind of constraint satisfaction problem. When the memory required to apply BE is too high, a heuristic method based on it (denominated mini-buckets) can be used to calculate bounds for the optimal solution. Nevertheless, the curse of dimensionality makes these techniques unpractical for large size problems. In response to this situation, we present a memetic algorithm for the MDSLP in which BE is used as a mechanism for recombining solutions, providing the best possible child from the parental set. Subsequently, a multi-level model in which this exact/metaheuristic hybrid is further hybridized with branch-and-bound techniques and mini-buckets is studied. Extensive experimental results analyze the performance of these models and multi-parent recombination. The resulting algorithm consistently finds optimal patterns for up to date solved instances in less time than current approaches. Moreover, it is shown that this proposal provides new best known solutions for very large instances.
XML Rewriting Attacks: Existing Solutions and their Limitations
Venue: arXiv cs.CR 2008
Year: 2008

Web Services are web-based applications made available for web users or remote Web-based programs. In order to promote interoperability, they publish their interfaces in the so-called WSDL file and allow remote call over the network. Although Web Services can be used in different ways, the industry standard is the Service Oriented Architecture Web Services that doesn't rely on the implementation details. In this architecture, communication is performed through XML-based messages called SOAP messages. However, those messages are prone to attacks that can lead to code injection, unauthorized accesses, identity theft, etc. This type of attacks, called XML Rewriting Attacks, are all based on unauthorized, yet possible, modifications of SOAP messages. We present in this paper an explanation of this kind of attack, review the existing solutions, and show their limitations. We also propose some ideas to secure SOAP messages, as well as implementation ideas.
Solution of Peter Winkler's Pizza Problem
Venue: arXiv cs.DM 2008
Year: 2008

Bob cuts a pizza into slices of not necessarily equal size and shares it with Alice by alternately taking turns. One slice is taken in each turn. The first turn is Alice's. She may choose any of the slices. In all other turns only those slices can be chosen that have a neighbor slice already eaten. We prove a conjecture of Peter Winkler by showing that Alice has a strategy for obtaining 4/9 of the pizza. This is best possible, that is, there is a cutting and a strategy for Bob to get 5/9 of the pizza. We also give a characterization of Alice's best possible gain depending on the number of slices. For a given cutting of the pizza, we describe a linear time algorithm that computes Alice's strategy gaining at least 4/9 of the pizza and another algorithm that computes the optimal strategy for both players in any possible position of the game in quadratic time. We distinguish two types of turns, shifts and jumps. We prove that Alice can gain 4/9, 7/16 and 1/3 of the pizza if she is allowed to make at most two jumps, at most one jump and no jump, respectively, and the three constants are the best possible.
On Some Classes of Functions and Hypercubes
Venue: arXiv cs.DM 2008
Year: 2008

In this paper, some classes of discrete functions of $k$-valued logic are considered, that depend on sets of their variables in a particular way. Obtained results allow to "construct" these functions and to present them in their tabular, analytical or matrix form, that is, as hypercubes, and in particular Latin hypercubes. Results connected with identifying of variables of some classes of functions are obtained.
Delay-Throughput Tradeoff for Supportive Two-Tier Networks
Venue: arXiv cs.IT 2008
Year: 2008

Consider a static wireless network that has two tiers with different priorities: a primary tier vs. a secondary tier. The primary tier consists of randomly distributed legacy nodes of density $n$, which have an absolute priority to access the spectrum. The secondary tier consists of randomly distributed cognitive nodes of density $m=n^β$ with $β\geq 2$, which can only access the spectrum opportunistically to limit the interference to the primary tier. By allowing the secondary tier to route the packets for the primary tier, we show that the primary tier can achieve a throughput scaling of $λ_p(n)=Θ(1/\log n)$ per node and a delay-throughput tradeoff of $D_p(n)=Θ(\sqrt{n^β\log n}λ_p(n))$ for $λ_p(n)=O(1/\log n)$, while the secondary tier still achieves the same optimal delay-throughput tradeoff as a stand-alone network.