OpenRaiser/Intern-Atlas huggingface dataset:
About a Discrete Cellular Soliton (computer simulation)
Venue: arXiv cs.DM 2011
Year: 2011

For the first time a mathematical object is presented - a reversible cellular Automaton - with many paradoxical qualities, the main ones among them are: a frequent quickly return to its original state, the presence of a large number of conservation laws and paradoxical "fuzzy" symmetries, which connects the current position of the automaton with its signature Main Integral.
Reduction in X does not agree with Intersection and Union Types (Extended abstract)
Venue: arXiv cs.LO 2011
Year: 2011

This paper defines intersection and union type assignment for the calculus X, a substitution free language that enjoys the Curry-Howard correspondence with respect to Gentzen's sequent calculus for classical logic. We show that this notion is closed for subject-expansion, and show that it needs to be restricted to satisfy subject-reduction as well, making it unsuitable to define a semantics.
Detachable Object Detection: Segmentation and Depth Ordering From Short-Baseline Video
Venue: arXiv cs.CV 2011
Year: 2011

We describe an approach for segmenting an image into regions that correspond to surfaces in the scene that are partially surrounded by the medium. It integrates both appearance and motion statistics into a cost functional, that is seeded with occluded regions and minimized efficiently by solving a linear programming problem. Where a short observation time is insufficient to determine whether the object is detachable, the results of the minimization can be used to seed a more costly optimization based on a longer sequence of video data. The result is an entirely unsupervised scheme to detect and segment an arbitrary and unknown number of objects. We test our scheme to highlight the potential, as well as limitations, of our approach.
Probabilistic prototype models for attributed graphs
Venue: arXiv cs.CV 2011
Year: 2011

This contribution proposes a new approach towards developing a class of probabilistic methods for classifying attributed graphs. The key concept is random attributed graph, which is defined as an attributed graph whose nodes and edges are annotated by random variables. Every node/edge has two random processes associated with it- occurence probability and the probability distribution over the attribute values. These are estimated within the maximum likelihood framework. The likelihood of a random attributed graph to generate an outcome graph is used as a feature for classification. The proposed approach is fast and robust to noise.
A New Approach to Design Graph Based Search Engine for Multiple Domains Using Different Ontologies
Venue: arXiv cs.IR 2011
Year: 2011

Search Engine has become a major tool for searching any information from the World Wide Web (WWW). While searching the huge digital library available in the WWW, every effort is made to retrieve the most relevant results. But in WWW majority of the Web pages are in HTML format and there are no such tags which tells the crawler to find any specific domain. To find more relevant result we use Ontology for that particular domain. If we are working with multiple domains then we use multiple ontologies. Now in order to design a domain specific search engine for multiple domains, crawler must crawl through the domain specific Web pages in the WWW according to the predefined ontologies.
Analysis of first prototype universal intelligence tests: evaluating and comparing AI algorithms and humans
Venue: arXiv cs.AI 2011
Year: 2011

Today, available methods that assess AI systems are focused on using empirical techniques to measure the performance of algorithms in some specific tasks (e.g., playing chess, solving mazes or land a helicopter). However, these methods are not appropriate if we want to evaluate the general intelligence of AI and, even less, if we compare it with human intelligence. The ANYNT project has designed a new method of evaluation that tries to assess AI systems using well known computational notions and problems which are as general as possible. This new method serves to assess general intelligence (which allows us to learn how to solve any new kind of problem we face) and not only to evaluate performance on a set of specific tasks. This method not only focuses on measuring the intelligence of algorithms, but also to assess any intelligent system (human beings, animals, AI, aliens?,...), and letting us to place their results on the same scale and, therefore, to be able to compare them. This new approach will allow us (in the future) to evaluate and compare any kind of intelligent system known or even to build/find, be it artificial or biological. This master thesis aims at ensuring that this new method provides consistent results when evaluating AI algorithms, this is done through the design and implementation of prototypes of universal intelligence tests and their application to different intelligent systems (AI algorithms and humans beings). From the study we analyze whether the results obtained by two different intelligent systems are properly located on the same scale and we propose changes and refinements to these prototypes in order to, in the future, being able to achieve a truly universal intelligence test.
A Semantic Analysis of Key Management Protocols for Wireless Sensor Networks
Venue: arXiv cs.CR 2011
Year: 2011

We propose a simple timed broadcasting process calculus for modelling wireless network protocols. The operational semantics of our calculus is given in terms of a labelled transition semantics which is used to derive a standard (weak) bi-simulation theory. Based on our simulation theory, we reformulate Gorrieri and Martinelli's timed Generalized Non-Deducibility on Compositions (tGNDC) scheme, a well-known general framework for the definition of timed properties of security protocols. We use tGNDC to perform a semantic analysis of three well-known key management protocols for wireless sensor networks: μTESLA, LEAP+ and LiSP. As a main result, we provide a number of attacks to these protocols which, to our knowledge, have not yet appeared in the literature.
Improving the scalability of parallel N-body applications with an event driven constraint based execution model
Venue: arXiv cs.DC 2011
Year: 2011

The scalability and efficiency of graph applications are significantly constrained by conventional systems and their supporting programming models. Technology trends like multicore, manycore, and heterogeneous system architectures are introducing further challenges and possibilities for emerging application domains such as graph applications. This paper explores the space of effective parallel execution of ephemeral graphs that are dynamically generated using the Barnes-Hut algorithm to exemplify dynamic workloads. The workloads are expressed using the semantics of an Exascale computing execution model called ParalleX. For comparison, results using conventional execution model semantics are also presented. We find improved load balancing during runtime and automatic parallelism discovery improving efficiency using the advanced semantics for Exascale computing.
Bias Plus Variance Decomposition for Survival Analysis Problems
Venue: arXiv cs.LG 2011
Year: 2011

Bias - variance decomposition of the expected error defined for regression and classification problems is an important tool to study and compare different algorithms, to find the best areas for their application. Here the decomposition is introduced for the survival analysis problem. In our experiments, we study bias -variance parts of the expected error for two algorithms: original Cox proportional hazard regression and CoxPath, path algorithm for L1-regularized Cox regression, on the series of increased training sets. The experiments demonstrate that, contrary expectations, CoxPath does not necessarily have an advantage over Cox regression.
Achievable Rates for K-user Gaussian Interference Channels
Venue: arXiv cs.IT 2011
Year: 2011

The aim of this paper is to study the achievable rates for a $K$ user Gaussian interference channels for any SNR using a combination of lattice and algebraic codes. Lattice codes are first used to transform the Gaussian interference channel (G-IFC) into a discrete input-output noiseless channel, and subsequently algebraic codes are developed to achieve good rates over this new alphabet. In this context, a quantity called efficiency is introduced which reflects the effectiveness of the algebraic coding strategy. The paper first addresses the problem of finding high efficiency algebraic codes. A combination of these codes with Construction-A lattices is then used to achieve non trivial rates for the original Gaussian interference channel.
Self-Organization of Wireless Ad Hoc Networks as Small Worlds Using Long Range Directional Beams
Venue: arXiv cs.NI 2011
Year: 2011

We study how long range directional beams can be used for self-organization of a wireless network to exhibit small world properties. Using simulation results for randomized beamforming as a guideline, we identify crucial design issues for algorithm design. Subsequently, we propose an algorithm for deterministic creation of small worlds. We define a new centrality measure that estimates the structural importance of nodes based on traffic flow in the network, which is used to identify the optimum nodes for beamforming. This results in significant reduction in path length while maintaining connectivity.
The capacity for the linear time-invariant Gaussian relay channel
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, the Gaussian relay channel with linear time-invariant relay filtering is considered. Based on spectral theory for stationary processes, the maximum achievable rate for this subclass of linear Gaussian relay operation is obtained in finite-letter characterization. The maximum rate can be achieved by dividing the overall frequency band into at most eight subbands and by making the relay behave as an instantaneous amplify-and-forward relay at each subband. Numerical results are provided to evaluate the performance of LTI relaying.
Recovery of Block-Sparse Representations from Noisy Observations via Orthogonal Matching Pursuit
Venue: arXiv cs.IT 2011
Year: 2011

We study the problem of recovering the sparsity pattern of block-sparse signals from noise-corrupted measurements. A simple, efficient recovery method, namely, a block-version of the orthogonal matching pursuit (OMP) method, is considered in this paper and its behavior for recovering the block-sparsity pattern is analyzed. We provide sufficient conditions under which the block-version of the OMP can successfully recover the block-sparse representations in the presence of noise. Our analysis reveals that exploiting block-sparsity can improve the recovery ability and lead to a guaranteed recovery for a higher sparsity level. Numerical results are presented to corroborate our theoretical claim.
Static Dependency Pair Method based on Strong Computability for Higher-Order Rewrite Systems
Venue: arXiv cs.LO 2011
Year: 2011

Higher-order rewrite systems (HRSs) and simply-typed term rewriting systems (STRSs) are computational models of functional programs. We recently proposed an extremely powerful method, the static dependency pair method, which is based on the notion of strong computability, in order to prove termination in STRSs. In this paper, we extend the method to HRSs. Since HRSs include λ-abstraction but STRSs do not, we restructure the static dependency pair method to allow λ-abstraction, and show that the static dependency pair method also works well on HRSs without new restrictions.
On the Simulation of Time-Triggered Systems on a Chip with BIP
Venue: arXiv cs.SE 2011
Year: 2011

In this report, we present functional models for software and hardware components of Time-Triggered Systems on a Chip (TTSoC). These are modeled in the asynchronous component based language BIP. We demonstrate the usability of our components for simulation of software which is developed for the TTSoC. Our software comprises services and an application part. Our approach allows us to simulate and validate aspects of the software system at an early stage in the development process and without the need to have the TTSoC hardware at hand.
Shared Memory Concurrent System Verification using Kronecker Algebra
Venue: arXiv cs.LO 2011
Year: 2011

The verification of multithreaded software is still a challenge. This comes mainly from the fact that the number of thread interleavings grows exponentially in the number of threads. The idea that thread interleavings can be studied with a matrix calculus is a novel approach in this research area. Our sparse matrix representations of the program are manipulated using a lazy implementation of Kronecker algebra. One goal is the generation of a data structure called Concurrent Program Graph (CPG) which describes all possible interleavings and incorporates synchronization while preserving completeness. We prove that CPGs in general can be represented by sparse adjacency matrices. Thus the number of entries in the matrices is linear in their number of lines. Hence efficient algorithms can be applied to CPGs. In addition, due to synchronization only very small parts of the resulting matrix are actually needed, whereas the rest is unreachable in terms of automata. Thanks to the lazy implementation of the matrix operations the unreachable parts are never calculated. This speeds up processing significantly and shows that this approach is very promising. Various applications including data flow analysis can be performed on CPGs. Furthermore, the structure of the matrices can be used to prove properties of the underlying program for an arbitrary number of threads. For example, deadlock freedom is proved for a large class of programs.
Queries mining for efficient routing in P2P communities
Venue: arXiv cs.PF 2011
Year: 2011

Peer-to-peer (P2P) computing is currently attracting enormous attention. In P2P systems a very large number of autonomous computing nodes (the peers) pool together their resources and rely on each other for data and services. Peer-to-peer (P2P) Data-sharing systems now generate a significant portion of Internet traffic. Examples include P2P systems for network storage, web caching, searching and indexing of relevant documents and distributed network-threat analysis. Requirements for widely distributed information systems supporting virtual organizations have given rise to a new category of P2P systems called schema-based. In such systems each peer exposes its own schema and the main objective is the efficient search across the P2P network by processing each incoming query without overly consuming bandwidth. The usability of these systems depends on effective techniques to find and retrieve data; however, efficient and effective routing of content-based queries is a challenging problem in P2P networks. This work was attended as an attempt to motivate the use of mining algorithms and hypergraphs context to develop two different methods that improve significantly the efficiency of P2P communications. The proposed query routing methods direct the query to a set of relevant peers in such way as to avoid network traffic and bandwidth consumption. We compare the performance of the two proposed methods with the baseline one and our experimental results prove that our proposed methods generate impressive levels of performance and scalability.
Dynamic Local Search for the Maximum Clique Problem
Venue: arXiv cs.AI 2011
Year: 2011

In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices are added to the current clique, and plateau search, during which vertices of the current clique are swapped with vertices not contained in the current clique. The selection of vertices is solely based on vertex penalties that are dynamically adjusted during the search, and a perturbation mechanism is used to overcome search stagnation. The behaviour of DLS-MC is controlled by a single parameter, penalty delay, which controls the frequency at which vertex penalties are reduced. We show empirically that DLS-MC achieves substantial performance improvements over state-of-the-art algorithms for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances.
SLPA: Uncovering Overlapping Communities in Social Networks via A Speaker-listener Interaction Dynamic Process
Venue: arXiv cs.SI 2011
Year: 2011

Overlap is one of the characteristics of social networks, in which a person may belong to more than one social group. For this reason, discovering overlapping structures is necessary for realistic social analysis. In this paper, we present a novel, general framework to detect and analyze both individual overlapping nodes and entire communities. In this framework, nodes exchange labels according to dynamic interaction rules. A specific implementation called Speaker-listener Label Propagation Algorithm (SLPA1) demonstrates an excellent performance in identifying both overlapping nodes and overlapping communities with different degrees of diversity.
Cooperative and Distributed Localization for Wireless Sensor Networks in Multipath Environments
Venue: arXiv cs.DC 2011
Year: 2011

We consider the problem of sensor localization in a wireless network in a multipath environment, where time and angle of arrival information are available at each sensor. We propose a distributed algorithm based on belief propagation, which allows sensors to cooperatively self-localize with respect to one single anchor in a multihop network. The algorithm has low overhead and is scalable. Simulations show that although the network is loopy, the proposed algorithm converges, and achieves good localization accuracy.
On the control of the load increments for a proper description of multiple delamination in a domain decomposition framework
Venue: arXiv cs.NA 2011
Year: 2011

In quasi-static nonlinear time-dependent analysis, the choice of the time discretization is a complex issue. The most basic strategy consists in determining a value of the load increment that ensures the convergence of the solution with respect to time on the base of preliminary simulations. In more advanced applications, the load increments can be controlled for instance by prescribing the number of iterations of the nonlinear resolution procedure, or by using an arc-length algorithm. These techniques usually introduce a parameter whose correct value is not easy to obtain. In this paper, an alternative procedure is proposed. It is based on the continuous control of the residual of the reference problem over time, whose measure is easy to interpret. This idea is applied in the framework of a multiscale domain decomposition strategy in order to perform 3D delamination analysis.
Probabilistic Hybrid Action Models for Predicting Concurrent Percept-driven Robot Behavior
Venue: arXiv cs.AI 2011
Year: 2011

This article develops Probabilistic Hybrid Action Models (PHAMs), a realistic causal model for predicting the behavior generated by modern percept-driven robot plans. PHAMs represent aspects of robot behavior that cannot be represented by most action models used in AI planning: the temporal structure of continuous control processes, their non-deterministic effects, several modes of their interferences, and the achievement of triggering conditions in closed-loop robot plans. The main contributions of this article are: (1) PHAMs, a model of concurrent percept-driven behavior, its formalization, and proofs that the model generates probably, qualitatively accurate predictions; and (2) a resource-efficient inference method for PHAMs based on sampling projections from probabilistic action models and state descriptions. We show how PHAMs can be applied to planning the course of action of an autonomous robot office courier based on analytical and experimental results.
Fractal String Generation and Its Application in Music Composition
Venue: arXiv cs.SD 2011
Year: 2011

Music is a string of some of the notes out of 12 notes (Sa, Komal_re, Re, Komal_ga, Ga, Ma, Kari_ma, Pa, Komal_dha, Dha, Komal_ni, Ni) and their harmonics. Each note corresponds to a particular frequency. When such strings are encoded to form discrete sequences, different frequencies present in the music corresponds to different amplitude levels (value) of the discrete sequence. Initially, a class of discrete sequences has been generated using logistic map. All these discrete sequences have at most n-different amplitude levels (value) (depending on the particular raga). Without loss of generality, we have chosen two discrete sequences of two types of Indian raga viz. Bhairabi and Bhupali having same number of amplitude levels to obtain/search close relatives from the class. The relative / closeness can be assured through correlation coefficient.The search is unbiased, random and non-adaptive. The obtained string is that which maximally resembles the given two sequences. The same can be thought of as a music composition of the given two strings. It is to be noted that all these string are fractal string which can be persuaded by fractal dimension.
When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial
Venue: arXiv cs.SC 2011
Year: 2011

We introduce a new algorithm denoted DSC2 to isolate the real roots of a univariate square-free polynomial f with integer coefficients. The algorithm iteratively subdivides an initial interval which is known to contain all real roots of f. The main novelty of our approach is that we combine Descartes' Rule of Signs and Newton iteration. More precisely, instead of using a fixed subdivision strategy such as bisection in each iteration, a Newton step based on the number of sign variations for an actual interval is considered, and, only if the Newton step fails, we fall back to bisection. Following this approach, our analysis shows that, for most iterations, we can achieve quadratic convergence towards the real roots. In terms of complexity, our method induces a recursion tree of almost optimal size O(nlog(n tau)), where n denotes the degree of the polynomial and tau the bitsize of its coefficients. The latter bound constitutes an improvement by a factor of tau upon all existing subdivision methods for the task of isolating the real roots. In addition, we provide a bit complexity analysis showing that DSC2 needs only \tilde{O}(n^3tau) bit operations to isolate all real roots of f. This matches the best bound known for this fundamental problem. However, in comparison to the much more involved algorithms by Pan and Schönhage (for the task of isolating all complex roots) which achieve the same bit complexity, DSC2 focuses on real root isolation, is very easy to access and easy to implement.
The Dispersion of Joint Source-Channel Coding
Venue: arXiv cs.IT 2011
Year: 2011

In this work we investigate the behavior of the distortion threshold that can be guaranteed in joint source-channel coding, to within a prescribed excess-distortion probability. We show that the gap between this threshold and the optimal average distortion is governed by a constant that we call the joint source-channel dispersion. This constant can be easily computed, since it is the sum of the source and channel dispersions, previously derived. The resulting performance is shown to be better than that of any separation-based scheme. For the proof, we use unequal error protection channel coding, thus we also evaluate the dispersion of that setting.