OpenRaiser/Intern-Atlas huggingface dataset:
Undithering using linear filtering and non-linear diffusion techniques
Venue: arXiv cs.CV 2011
Year: 2011

Data compression is a method of improving the efficiency of transmission and storage of images. Dithering, as a method of data compression, can be used to convert an 8-bit gray level image into a 1-bit / binary image. Undithering is the process of reconstruction of gray image from binary image obtained from dithering of gray image. In the present paper, I propose a method of undithering using linear filtering followed by anisotropic diffusion which brings the advantage of smoothing and edge enhancement. First-order statistical parameters, second-order statistical parameters, mean-squared error (MSE) between reconstructed image and the original image before dithering, and peak signal to noise ratio (PSNR) are evaluated at each step of diffusion. Results of the experiments show that the reconstructed image is not as sharp as the image before dithering but a large number of gray values are reproduced with reference to those of the original image prior to dithering.
Classification of Emergency Scenarios
Venue: arXiv cs.OH 2011
Year: 2011

In most of today's emergency scenarios information plays a crucial role. Therefore, information has to be constantly collected and shared among all rescue team members and this requires new innovative technologies. In this paper a classification of emergency scenarios is presented, describing their special characteristics and common strategies employed by rescue units to handle them. Based on interviews with professional firefighters, requirements for new systems are listed. The goal of this article is to support developers designing new systems by providing them a deeper look into the work of first responders.
A New General-Purpose Method to Multiply 3x3 Matrices Using Only 23 Multiplications
Venue: arXiv cs.SC 2011
Year: 2011

One of the most famous conjectures in computer algebra is that matrix multiplication might be feasible in not much more than quadratic time. The best known exponent is 2.376, due to Coppersmith and Winograd. Many attempts to solve this problems in the literature work by solving, fixed-size problems and then apply the solution recursively. This leads to pure combinatorial optimisation problems with fixed size. These problems are unlikely to be solvable in polynomial time. In 1976 Laderman published a method to multiply two 3x3 matrices using only 23 multiplications. This result is non-commutative, and therefore can be applied recursively to smaller sub-matrices. In 35 years nobody was able to do better and it remains an open problem if this can be done with 22 multiplications. We proceed by solving the so called Brent equations [7]. We have implemented a method to converting this very hard problem to a SAT problem, and we have attempted to solve it, with our portfolio of some 500 SAT solvers. With this new method we were able to produce new solutions to the Laderman's problem. We present a new fully general non-commutative solution with 23 multiplications and show that this solution is new and is NOT an equivalent variant of the Laderman's original solution. This result demonstrates that the space of solutions to Laderman's problem is larger than expected, and therefore it becomes now more plausible that a solution with 22 multiplications exists. If it exists, we might be able to find it soon just by running our algorithms longer, or due to further improvements in the SAT solver algorithms.
Structure Theorems for Real-Time Variable-Rate Coding With and Without Side Information
Venue: arXiv cs.IT 2011
Year: 2011

The output of a discrete Markov source is to be encoded instantaneously by a variable-rate encoder and decoded by a finite-state decoder. Our performance measure is a linear combination of the distortion and the instantaneous rate. Structure theorems, pertaining to the encoder and next-state functions are derived for every given finite-state decoder, which can have access to side information.
User Scheduling for Heterogeneous Multiuser MIMO Systems: A Subspace Viewpoint
Venue: arXiv cs.IT 2011
Year: 2011

In downlink multiuser multiple-input multiple-output (MU-MIMO) systems, users are practically heterogeneous in nature. However, most of the existing user scheduling algorithms are designed with an implicit assumption that the users are homogeneous. In this paper, we revisit the problem by exploring the characteristics of heterogeneous users from a subspace point of view. With an objective of minimizing interference non-orthogonality among users, three new angular-based user scheduling criteria that can be applied in various user scheduling algorithms are proposed. While the first criterion is heuristically determined by identifying the incapability of largest principal angle to characterize the subspace correlation and hence the interference non-orthogonality between users, the second and third ones are derived by using, respectively, the sum rate capacity bounds with block diagonalization and the change in capacity by adding a new user into an existing user subset. Aiming at capturing fairness among heterogeneous users while maintaining multiuser diversity gain, two new hybrid user scheduling algorithms are also proposed whose computational complexities are only linearly proportional to the number of users. We show by simulations that the effectiveness of our proposed user scheduling criteria and algorithms with respect to those commonly used in homogeneous environment.
Axiomatizing GSOS with Predicates
Venue: arXiv cs.LO 2011
Year: 2011

In this paper, we introduce an extension of the GSOS rule format with predicates such as termination, convergence and divergence. For this format we generalize the technique proposed by Aceto, Bloom and Vaandrager for the automatic generation of ground-complete axiomatizations of bisimilarity over GSOS systems. Our procedure is implemented in a tool that receives SOS specifications as input and derives the corresponding axiomatizations automatically. This paves the way to checking strong bisimilarity over process terms by means of theorem-proving techniques.
Stability Conditions for Online Learnability
Venue: arXiv cs.LG 2011
Year: 2011

Stability is a general notion that quantifies the sensitivity of a learning algorithm's output to small change in the training dataset (e.g. deletion or replacement of a single training sample). Such conditions have recently been shown to be more powerful to characterize learnability in the general learning setting under i.i.d. samples where uniform convergence is not necessary for learnability, but where stability is both sufficient and necessary for learnability. We here show that similar stability conditions are also sufficient for online learnability, i.e. whether there exists a learning algorithm such that under any sequence of examples (potentially chosen adversarially) produces a sequence of hypotheses that has no regret in the limit with respect to the best hypothesis in hindsight. We introduce online stability, a stability condition related to uniform-leave-one-out stability in the batch setting, that is sufficient for online learnability. In particular we show that popular classes of online learners, namely algorithms that fall in the category of Follow-the-(Regularized)-Leader, Mirror Descent, gradient-based methods and randomized algorithms like Weighted Majority and Hedge, are guaranteed to have no regret if they have such online stability property. We provide examples that suggest the existence of an algorithm with such stability condition might in fact be necessary for online learnability. For the more restricted binary classification setting, we establish that such stability condition is in fact both sufficient and necessary. We also show that for a large class of online learnable problems in the general learning setting, namely those with a notion of sub-exponential covering, no-regret online algorithms that have such stability condition exists.
Bounding Procedures for Stochastic Dynamic Programs with Application to the Perimeter Patrol Problem
Venue: arXiv cs.SY 2011
Year: 2011

One often encounters the curse of dimensionality in the application of dynamic programming to determine optimal policies for controlled Markov chains. In this paper, we provide a method to construct sub-optimal policies along with a bound for the deviation of such a policy from the optimum via a linear programming approach. The state-space is partitioned and the optimal cost-to-go or value function is approximated by a constant over each partition. By minimizing a non-negative cost function defined on the partitions, one can construct an approximate value function which also happens to be an upper bound for the optimal value function of the original Markov Decision Process (MDP). As a key result, we show that this approximate value function is {\it independent} of the non-negative cost function (or state dependent weights as it is referred to in the literature) and moreover, this is the least upper bound that one can obtain once the partitions are specified. Furthermore, we show that the restricted system of linear inequalities also embeds a family of MDPs of lower dimension, one of which can be used to construct a lower bound on the optimal value function. The construction of the lower bound requires the solution to a combinatorial problem. We apply the linear programming approach to a perimeter surveillance stochastic optimal control problem and obtain numerical results that corroborate the efficacy of the proposed methodology.
A Spatial Calculus of Wrapped Compartments
Venue: arXiv cs.LO 2011
Year: 2011

The Calculus of Wrapped Compartments (CWC) is a recently proposed modelling language for the representation and simulation of biological systems behaviour. Although CWC has no explicit structure modelling a spatial geometry, its compartment labelling feature can be exploited to model various examples of spatial interactions in a natural way. However, specifying large networks of compartments may require a long modelling phase. In this work we present a surface language for CWC that provides basic constructs for modelling spatial interactions. These constructs can be compiled away to obtain a standard CWC model, thus exploiting the existing CWC simulation tool. A case study concerning the modelling of Arbuscular Mychorrizal fungi growth is discussed.
Further Results on Languages of Membrane Structures
Venue: arXiv cs.DC 2011
Year: 2011

P systems with active membranes were used to generate languages, in the sense of languages associated with the structure of membrane systems. Here, we analyze the power of P systems with membrane creation and dissolution restricted to elementary membranes, P systems without membrane dissolution operating according to certain output modes. This leads us to characterizations of recursively enumerable languages.
Interactions between Digital Geometry and Combinatorics on Words
Venue: arXiv cs.CG 2011
Year: 2011

We review some recent results in digital geometry obtained by using a combinatorics on words approach to discrete geometry. Motivated on the one hand by the well-known theory of Sturmian words which model conveniently discrete lines in the plane, and on the other hand by the development of digital geometry, this study reveals strong links between the two fields. Discrete figures are identified with polyominoes encoded by words. The combinatorial tools lead to elegant descriptions of geometrical features and efficient algorithms. Among these, radix-trees are useful for efficiently detecting path intersection, Lyndon and Christoffel words appear as the main tools for describing digital convexity; equations on words allow to better understand tilings by translations.
Pattern Avoidability with Involution
Venue: arXiv cs.FL 2011
Year: 2011

An infinte word w avoids a pattern p with the involution t if there is no substitution for the variables in p and no involution t such that the resulting word is a factor of w. We investigate the avoidance of patterns with respect to the size of the alphabet. For example, it is shown that the pattern a t(a) a can be avoided over three letters but not two letters, whereas it is well known that a a a is avoidable over two letters.
Dynamical generalizations of the Lagrange spectrum
Venue: arXiv cs.FL 2011
Year: 2011

We compute two invariants of topological conjugacy, the upper and lower limits of the inverse of Boshernitzan's ne_n, where e_n is the smallest measure of a cylinder of length n, for three families of symbolic systems, the natural codings of rotations and three-interval exchanges and the Arnoux-Rauzy systems. The sets of values of these invariants for a given family of systems generalize the Lagrange spectrum, which is what we get for the family of rotations with the upper limit of 1/ne_n.
A Classification of Trapezoidal Words
Venue: arXiv cs.FL 2011
Year: 2011

Trapezoidal words are finite words having at most n+1 distinct factors of length n, for every n>=0. They encompass finite Sturmian words. We distinguish trapezoidal words into two disjoint subsets: open and closed trapezoidal words. A trapezoidal word is closed if its longest repeated prefix has exactly two occurrences in the word, the second one being a suffix of the word. Otherwise it is open. We show that open trapezoidal words are all primitive and that closed trapezoidal words are all Sturmian. We then show that trapezoidal palindromes are closed (and therefore Sturmian). This allows us to characterize the special factors of Sturmian palindromes. We end with several open problems.
On Pansiot Words Avoiding 3-Repetitions
Venue: arXiv cs.FL 2011
Year: 2011

The recently confirmed Dejean's conjecture about the threshold between avoidable and unavoidable powers of words gave rise to interesting and challenging problems on the structure and growth of threshold words. Over any finite alphabet with k >= 5 letters, Pansiot words avoiding 3-repetitions form a regular language, which is a rather small superset of the set of all threshold words. Using cylindric and 2-dimensional words, we prove that, as k approaches infinity, the growth rates of complexity for these regular languages tend to the growth rate of complexity of some ternary 2-dimensional language. The numerical estimate of this growth rate is about 1.2421.
Self-Organizing Mixture Networks for Representation of Grayscale Digital Images
Venue: arXiv cs.AI 2011
Year: 2011

Self-Organizing Maps are commonly used for unsupervised learning purposes. This paper is dedicated to the certain modification of SOM called SOMN (Self-Organizing Mixture Networks) used as a mechanism for representing grayscale digital images. Any grayscale digital image regarded as a distribution function can be approximated by the corresponding Gaussian mixture. In this paper, the use of SOMN is proposed in order to obtain such approximations for input grayscale images in unsupervised manner.
Coding in the Presence of Semantic Value of Information: Unequal Error Protection Using Poset Decoders
Venue: arXiv cs.IT 2011
Year: 2011

In this work we explore possibilities for coding when information worlds have different (semantic) values. We introduce a loss function that expresses the overall performance of a coding scheme for discrete channels and exchange the usual goal of minimizing the error probability to that of minimizing the expected loss. In this environment we explore the possibilities of using poset-decoders to make a message-wise unequal error protection (UEP), where the most valuable information is protected by placing in its proximity information words that differ by small valued information. Similar definitions and results are shortly presented also for signal constellations in Euclidean space.
The Diversity Potential of Relay Selection with Practical Channel Estimation
Venue: arXiv cs.IT 2011
Year: 2011

We investigate the diversity order of decode-and-forward relay selection in Nakagami-m fading, in cases where practical channel estimation techniques are applied. In this respect, we introduce a unified model for the imperfect channel estimates, where the effects of noise, time-varying channels, and feedback delays are jointly considered. Based on this model, the correlation between the actual and the estimated channel values, ρ, is expressed as a function of the signal-to-noise ratio (SNR), yielding closed-form expressions for the overall outage probability as a function of ρ. The resulting diversity order and power gain reveal a high dependence of the performance of relay selection on the high SNR behavior of ρ, thus shedding light onto the effect of channel estimation on the overall performance. It is shown that when the channel estimates are not frequently updated in applications involving time-varying channels, or when the amount of power allocated for channel estimation is not sufficiently high, the diversity potential of relay selection is severely degraded. In short, the main contribution of this paper lies in answering the following question: How fast should ρtend to one, as the SNR tends to infinity, so that relay selection does not experience any diversity loss?
A graphical environment to express the semantics of control systems
Venue: arXiv cs.SY 2011
Year: 2011

We present the concept of a unified graphical environment for expressing the semantics of control systems. The graphical control system design environment in Simulink already allows engineers to insert a variety of assertions aimed the verification and validation of the control software. We propose extensions to a Simulink-like environment's annotation capabilities to include formal control system stability, performance properties and their proofs. We provide a conceptual description of a tool, that takes in a Simulink-like diagram of the control system as the input, and generates a graphically annotated control system diagram as the output. The annotations can either be inserted by the user or generated automatically by a third party control analysis software such as IQC$β$ or $μ$-tool. We finally describe how the graphical representation of the system and its properties can be translated to annotated programs in a programming language used in verification and validation such as Lustre or C.
Query Expansion: Term Selection using the EWC Semantic Relatedness Measure
Venue: arXiv cs.CL 2011
Year: 2011

This paper investigates the efficiency of the EWC semantic relatedness measure in an ad-hoc retrieval task. This measure combines the Wikipedia-based Explicit Semantic Analysis measure, the WordNet path measure and the mixed collocation index. In the experiments, the open source search engine Terrier was utilised as a tool to index and retrieve data. The proposed technique was tested on the NTCIR data collection. The experiments demonstrated promising results.
Multisensor Images Fusion Based on Feature-Level
Venue: arXiv cs.CV 2011
Year: 2011

Until now, of highest relevance for remote sensing data processing and analysis have been techniques for pixel level image fusion. So, This paper attempts to undertake the study of Feature-Level based image fusion. For this purpose, feature based fusion techniques, which are usually based on empirical or heuristic rules, are employed. Hence, in this paper we consider feature extraction (FE) for fusion. It aims at finding a transformation of the original space that would produce such new features, which preserve or improve as much as possible. This study introduces three different types of Image fusion techniques including Principal Component Analysis based Feature Fusion (PCA), Segment Fusion (SF) and Edge fusion (EF). This paper also devotes to concentrate on the analytical techniques for evaluating the quality of image fusion (F) by using various methods including (SD), (En), (CC), (SNR), (NRMSE) and (DI) to estimate the quality and degree of information improvement of a fused image quantitatively.
Modeling Smart Grid using Generalized Stochastic Petri Net
Venue: arXiv cs.OH 2011
Year: 2011

Building smart grid for power system is a major challenge for safe, automated and energy efficient usage of electricity. The full implementation of the smart grid will evolve over time. However, before a new set of infrastructures are invested to build the smart grid, proper modeling and analysis is needed to avoid wastage of resources. Modeling also helps to identify and prioritize appropriate systems parameters. In this paper, an all comprehensive model of smart grid have been proposed using Generalized Stochastic Petri Nets (GSPN). The model is used to analyze the constraints and deliverables of the smart power grid of future.
On Sequences with a Perfect Linear Complexity Profile
Venue: arXiv cs.IT 2011
Year: 2011

We derive Bézout identities for the minimal polynomials of a finite sequence and use them to prove a theorem of Wang and Massey on binary sequences with a perfect linear complexity profile. We give a new proof of Rueppel's conjecture and simplify Dai's original proof. We obtain short proofs of results of Niederreiter relating the linear complexity of a sequence s and K(s), which was defined using continued fractions. We give an upper bound for the sum of the linear complexities of any sequence. This bound is tight for sequences with a perfect linear complexity profile and we apply it to characterise these sequences in two new ways.
Coquet: a Coq library for verifying hardware
Venue: arXiv cs.LO 2011
Year: 2011

We propose a new library to model and verify hardware circuits in the Coq proof assistant. This library allows one to easily build circuits by following the usual pen-and-paper diagrams. We define a deep-embedding: we use a (dependently typed) data-type that models the architecture of circuits, and a meaning function. We propose tactics that ease the reasoning about the behavior of the circuits, and we demonstrate that our approach is practicable by proving the correctness of various circuits: a text-book divide and conquer adder of parametric size, some higher-order combinators of circuits, and some sequential circuits: a buffer, and a register.
Detection and emergence
Venue: arXiv cs.AI 2011
Year: 2011

Two different conceptions of emergence are reconciled as two instances of the phenomenon of detection. In the process of comparing these two conceptions, we find that the notions of complexity and detection allow us to form a unified definition of emergence that clearly delineates the role of the observer.
Soft Session Types
Venue: arXiv cs.LO 2011
Year: 2011

We show how systems of session types can enforce interactions to be bounded for all typable processes. The type system we propose is based on Lafont's soft linear logic and is strongly inspired by recent works about session types as intuitionistic linear logic formulas. Our main result is the existence, for every typable process, of a polynomial bound on the length of any reduction sequence starting from it and on the size of any of its reducts.
Ant Colony Optimization of Rough Set for HV Bushings Fault Detection
Venue: arXiv cs.NE 2011
Year: 2011

Most transformer failures are attributed to bushings failures. Hence it is necessary to monitor the condition of bushings. In this paper three methods are developed to monitor the condition of oil filled bushing. Multi-layer perceptron (MLP), Radial basis function (RBF) and Rough Set (RS) models are developed and combined through majority voting to form a committee. The MLP performs better that the RBF and the RS is terms of classification accuracy. The RBF is the fasted to train. The committee performs better than the individual models. The diversity of models is measured to evaluate their similarity when used in the committee.
dynPARTIX - A Dynamic Programming Reasoner for Abstract Argumentation
Venue: arXiv cs.AI 2011
Year: 2011

The aim of this paper is to announce the release of a novel system for abstract argumentation which is based on decomposition and dynamic programming. We provide first experimental evaluations to show the feasibility of this approach.