OpenRaiser/Intern-Atlas huggingface dataset:
Exact Computation of Kullback-Leibler Distance for Hidden Markov Trees and Models
Venue: arXiv cs.IT 2012
Year: 2012

We suggest new recursive formulas to compute the exact value of the Kullback-Leibler distance (KLD) between two general Hidden Markov Trees (HMTs). For homogeneous HMTs with regular topology, such as homogeneous Hidden Markov Models (HMMs), we obtain a closed-form expression for the KLD when no evidence is given. We generalize our recursive formulas to the case of HMMs conditioned on the observable variables. Our proposed formulas are validated through several numerical examples in which we compare the exact KLD value with Monte Carlo estimations.
Conjoining Speeds up Information Diffusion in Overlaying Social-Physical Networks
Venue: arXiv cs.SI 2012
Year: 2012

We study the diffusion of information in an overlaying social-physical network. Specifically, we consider the following set-up: There is a physical information network where information spreads amongst people through conventional communication media (e.g., face-to-face communication, phone calls), and conjoint to this physical network, there are online social networks where information spreads via web sites such as Facebook, Twitter, FriendFeed, YouTube, etc. We quantify the size and the critical threshold of information epidemics in this conjoint social-physical network by assuming that information diffuses according to the SIR epidemic model. One interesting finding is that even if there is no percolation in the individual networks, percolation (i.e., information epidemics) can take place in the conjoint social-physical network. We also show, both analytically and experimentally, that the fraction of individuals who receive an item of information (started from an arbitrary node) is significantly larger in the conjoint social-physical network case, as compared to the case where the networks are disjoint. These findings reveal that conjoining the physical network with online social networks can have a dramatic impact on the speed and scale of information diffusion.
Fuzzy cellular model of signal controlled traffic stream
Venue: arXiv cs.DM 2012
Year: 2012

Microscopic traffic models have recently gained considerable importance as a mean of optimising traffic control strategies. Computationally efficient and sufficiently accurate microscopic traffic models have been developed based on the cellular automata theory. However, the real-time application of the available cellular automata models in traffic control systems is a difficult task due to their discrete and stochastic nature. This paper introduces a novel method of traffic streams modelling, which combines cellular automata and fuzzy calculus. The introduced fuzzy cellular traffic model eliminates main drawbacks of the cellular automata approach i.e. necessity of multiple Monte Carlo simulations and calibration issues. Experimental results show that the evolution of a simulated traffic stream in the proposed fuzzy cellular model is consistent with that observed for stochastic cellular automata. The comparison of both methods confirms that the computational cost of traffic simulation is considerably lower for the proposed model. The model is suitable for real-time applications in traffic control systems.
On the Complexity of the Equivalence Problem for Probabilistic Automata
Venue: arXiv cs.FL 2012
Year: 2012

Checking two probabilistic automata for equivalence has been shown to be a key problem for efficiently establishing various behavioural and anonymity properties of probabilistic systems. In recent experiments a randomised equivalence test based on polynomial identity testing outperformed deterministic algorithms. In this paper we show that polynomial identity testing yields efficient algorithms for various generalisations of the equivalence problem. First, we provide a randomized NC procedure that also outputs a counterexample trace in case of inequivalence. Second, we show how to check for equivalence two probabilistic automata with (cumulative) rewards. Our algorithm runs in deterministic polynomial time, if the number of reward counters is fixed. Finally we show that the equivalence problem for probabilistic visibly pushdown automata is logspace equivalent to the Arithmetic Circuit Identity Testing problem, which is to decide whether a polynomial represented by an arithmetic circuit is identically zero.
Deciding Whether a Regular Language is Generated by a Splicing System
Venue: arXiv cs.FL 2012
Year: 2012

Splicing as a binary word/language operation is inspired by the DNA recombination under the action of restriction enzymes and ligases, and was first introduced by Tom Head in 1987. Shortly thereafter, it was proven that the languages generated by (finite) splicing systems form a proper subclass of the class of regular languages. However, the question of whether or not one can decide if a given regular language is generated by a splicing system remained open. In this paper we give a positive answer to this question. Namely, we prove that, if a language is generated by a splicing system, then it is also generated by a splicing system whose size is a function of the size of the syntactic monoid of the input language, and which can be effectively constructed.
Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
Venue: arXiv cs.MS 2012
Year: 2012

Transforming a matrix over a field to echelon form, or decomposing the matrix as a product of structured matrices that reveal the rank profile, is a fundamental building block of computational exact linear algebra. This paper surveys the well known variations of such decompositions and transformations that have been proposed in the literature. We present an algorithm to compute the CUP decomposition of a matrix, adapted from the LSP algorithm of Ibarra, Moran and Hui (1982), and show reductions from the other most common Gaussian elimination based matrix transformations and decompositions to the CUP decomposition. We discuss the advantages of the CUP algorithm over other existing algorithms by studying time and space complexities: the asymptotic time complexity is rank sensitive, and comparing the constants of the leading terms, the algorithms for computing matrix invariants based on the CUP decomposition are always at least as good except in one case. We also show that the CUP algorithm, as well as the computation of other invariants such as transformation to reduced column echelon form using the CUP algorithm, all work in place, allowing for example to compute the inverse of a matrix on the same storage as the input matrix.
Semantics and Algorithms for Parametric Monitoring
Venue: arXiv cs.PL 2012
Year: 2012

Analysis of execution traces plays a fundamental role in many program analysis approaches, such as runtime verification, testing, monitoring, and specification mining. Execution traces are frequently parametric, i.e., they contain events with parameter bindings. Each parametric trace usually consists of many meaningful trace slices merged together, each slice corresponding to one parameter binding. This gives a semantics-based solution to parametric trace analysis. A general-purpose parametric trace slicing technique is introduced, which takes each event in the parametric trace and dispatches it to its corresponding trace slices. This parametric trace slicing technique can be used in combination with any conventional, non-parametric trace analysis technique, by applying the later on each trace slice. As an instance, a parametric property monitoring technique is then presented. The presented parametric trace slicing and monitoring techniques have been implemented and extensively evaluated. Measurements of runtime overhead confirm that the generality of the discussed techniques does not come at a performance expense when compared with existing parametric trace monitoring systems.
Characterizing Continuous Time Random Walks on Time Varying Graphs
Venue: arXiv cs.SI 2012
Year: 2012

In this paper we study the behavior of a continuous time random walk (CTRW) on a stationary and ergodic time varying dynamic graph. We establish conditions under which the CTRW is a stationary and ergodic process. In general, the stationary distribution of the walker depends on the walker rate and is difficult to characterize. However, we characterize the stationary distribution in the following cases: i) the walker rate is significantly larger or smaller than the rate in which the graph changes (time-scale separation), ii) the walker rate is proportional to the degree of the node that it resides on (coupled dynamics), and iii) the degrees of node belonging to the same connected component are identical (structural constraints). We provide examples that illustrate our theoretical findings.
Why We Shouldn't Forget Multicast in Name-oriented Publish/Subscribe
Venue: arXiv cs.NI 2012
Year: 2012

Name-oriented networks introduce the vision of an information-centric, secure, globally available publish-subscribe infrastructure. Current approaches concentrate on unicast-based pull mechanisms and thereby fall short in automatically updating content at receivers. In this paper, we argue that an inclusion of multicast will grant additional benefits to the network layer, namely efficient distribution of real-time data, a many-to-many communication model, and simplified rendezvous processes. These aspects are comprehensively reflected by a group-oriented naming concept that integrates the various available group schemes and introduces new use cases. A first draft of this name-oriented multicast access has been implemented in the HAMcast middleware.
Information Carriers and Identification of Information Objects: An Ontological Approach
Venue: arXiv cs.DL 2012
Year: 2012

Even though library and archival practice, as well as Digital Preservation, have a long tradition in identifying information objects, the question of their precise identity under change of carrier or migration is still a riddle to science. The objective of this paper is to provide criteria for the unique identification of some important kinds of information objects, independent from the kind of carrier or specific encoding. Our approach is based on the idea that the substance of some kinds of information objects can completely be described in terms of discrete arrangements of finite numbers of known kinds of symbols, such as those implied by style guides for scientific journal submissions. Our theory is also useful for selecting or describing what has to be preserved. This is a fundamental problem since curators and archivists would like to formally record the decisions of what has to be preserved over time and to decide (or verify) whether a migration (transformation) preserves the intended information content. Furthermore, it is important for reasoning about the authenticity of digital objects, as well as for reducing the cost of digital preservation.
AES Encryption and Decryption Using Direct3D 10 API
Venue: arXiv cs.CR 2012
Year: 2012

Current video cards (GPUs - Graphics Processing Units) are very programmable, have become much more powerful than the CPUs and they are very affordable. In this paper, we present an implementation for the AES algorithm using Direct3D 10 certified GPUs. The graphics API Direct3D 10 is the first version that allows the use of integer operations, making from the traditional GPUs (that works only with floating point numbers), General Purpose GPUs that can be used for a large number of algorithms, including encryption. We present the performance of the symmetric key encryption algorithm - AES, on a middle range GPU and on a middle range quad core CPU. On the testing system, the developed solution is almost 3 times faster on the GPU than on one single core CPU, showing that the GPU can perform as an efficient cryptographic accelerator.
Weaknesses of a dynamic identity based authentication protocol for multi-server architecture
Venue: arXiv cs.CR 2012
Year: 2012

Recently, Li et al. proposed a dynamic identity based authentication protocol for multi-server architecture. They claimed their protocol is secure and can withstand various attacks. But we found some security loopholes in the protocol. Accordingly, the current paper demonstrates that Li et al.'s protocol is vulnerable to the replay attack, the password guessing attack and the masquerade attack.
An Entertaining Example of Using the Concepts of Context-Free Grammar and Pushdown Automation
Venue: arXiv cs.FL 2012
Year: 2012

A formal-linguistic approach for solving an entertaining task is made in this paper. The well-known task of the Hanoi towers is discussed in relation to some concepts of discrete mathematics. A context-free grammar which generate an algorithm for solving this task is described. A deterministic pushdown automation which in its work imitates the work of monks in solving the task of the Hanoi towers is built.
Implicit complexity for coinductive data: a characterization of corecurrence
Venue: arXiv cs.CC 2012
Year: 2012

We propose a framework for reasoning about programs that manipulate coinductive data as well as inductive data. Our approach is based on using equational programs, which support a seamless combination of computation and reasoning, and using productivity (fairness) as the fundamental assertion, rather than bi-simulation. The latter is expressible in terms of the former. As an application to this framework, we give an implicit characterization of corecurrence: a function is definable using corecurrence iff its productivity is provable using coinduction for formulas in which data-predicates do not occur negatively. This is an analog, albeit in weaker form, of a characterization of recurrence (i.e. primitive recursion) in [Leivant, Unipolar induction, TCS 318, 2004].
Method of the Multidimensional Sieve in the Practical Realization of some Combinatorial Algorithms
Venue: arXiv cs.DS 2012
Year: 2012

Some difficulties regarding the application of the well-known sieve method are considered in the case when a practical (program) realization of selecting elements, having a particular property among the elements of a set with a sufficiently great cardinal number(cardinality). In this paper the problem has been resolved by using a modified version of the method, utilizing multidimensional arrays. As a theoretical illustration of the method of the multidimensional sieve, the problem of obtaining a single representative of each equivalence class with respect to a given relation of equivalence and obtaining the cardinality of the respective factor set is considered with relevant mathematical proofs.
Computational Tutorial on Gröbner bases embedding Sage in LaTeX with SageTEX
Venue: arXiv cs.SC 2012
Year: 2012

Elementary tutorial on implementation aspects of Gröbner bases computation.
Probabilistic Motion Estimation Based on Temporal Coherence
Venue: arXiv cs.CV 2012
Year: 2012

We develop a theory for the temporal integration of visual motion motivated by psychophysical experiments. The theory proposes that input data are temporally grouped and used to predict and estimate the motion flows in the image sequence. This temporal grouping can be considered a generalization of the data association techniques used by engineers to study motion sequences. Our temporal-grouping theory is expressed in terms of the Bayesian generalization of standard Kalman filtering. To implement the theory we derive a parallel network which shares some properties of cortical networks. Computer simulations of this network demonstrate that our theory qualitatively accounts for psychophysical experiments on motion occlusion and motion outliers.
Relating Operator Spaces via Adjunctions
Venue: arXiv cs.LO 2012
Year: 2012

This chapter uses categorical techniques to describe relations between various sets of operators on a Hilbert space, such as self-adjoint, positive, density, effect and projection operators. These relations, including various Hilbert-Schmidt isomorphisms of the form tr(A-), are expressed in terms of dual adjunctions, and maps between them. Of particular interest is the connection with quantum structures, via a dual adjunction between convex sets and effect modules. The approach systematically uses categories of modules, via their description as Eilenberg-Moore algebras of a monad.
Near-Optimal Random Walk Sampling in Distributed Networks
Venue: arXiv cs.DC 2012
Year: 2012

Performing random walks in networks is a fundamental primitive that has found numerous applications in communication networks such as token management, load balancing, network topology discovery and construction, search, and peer-to-peer membership management. While several such algorithms are ubiquitous, and use numerous random walk samples, the walks themselves have always been performed naively. In this paper, we focus on the problem of performing random walk sampling efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds and messages required to obtain several random walk samples in a continuous online fashion. We present the first round and message optimal distributed algorithms that present a significant improvement on all previous approaches. The theoretical analysis and comprehensive experimental evaluation of our algorithms show that they perform very well in different types of networks of differing topologies. In particular, our results show how several random walks can be performed continuously (when source nodes are provided only at runtime, i.e., online), such that each walk of length $\ell$ can be performed exactly in just $\tilde{O}(\sqrt{\ell D})$ rounds, (where $D$ is the diameter of the network), and $O(\ell)$ messages. This significantly improves upon both, the naive technique that requires $O(\ell)$ rounds and $O(\ell)$ messages, and the sophisticated algorithm of [DasSarma et al. PODC 2010] that has the same round complexity as this paper but requires $Ω(m\sqrt{\ell})$ messages (where $m$ is the number of edges in the network). Our theoretical results are corroborated through extensive experiments on various topological data sets. Our algorithms are fully decentralized, lightweight, and easily implementable, and can serve as building blocks in the design of topologically-aware networks.
Is it a "Good" Encoding of Mixed Choice? (Technical Report)
Venue: arXiv cs.LO 2012
Year: 2012

This technical report contains the proofs to the lemmata and theorems of [PN12] as well as some additional material. As main contributions [PN12] presents an encoding of mixed choice in the context of the pi-calculus and a criterion to measure whether the degree of distribution in process networks is preserved.
Temporal Psychovisual Modulation: a new paradigm of information display
Venue: arXiv cs.ET 2012
Year: 2012

We report on a new paradigm of information display that greatly extends the utility and versatility of current optoelectronic displays. The main innovation is to let a display of high refresh rate optically broadcast so-called atom frames, which are designed through non-negative matrix factorization to form bases for a class of images, and different viewers perceive selfintended images by using display-synchronized viewing devices and their own human visual systems to fuse appropriately weighted atom frames. This work is essentially a scheme of temporal psychovisual modulation in visible spectrum, using an optoelectronic modulator coupled with a biological demodulator.
On completeness of reducibility candidates as a semantics of strong normalization
Venue: arXiv cs.LO 2012
Year: 2012

This paper defines a sound and complete semantic criterion, based on reducibility candidates, for strong normalization of theories expressed in minimal deduction modulo à la Curry. The use of Curry-style proof-terms allows to build this criterion on the classic notion of pre-Heyting algebras and makes that criterion concern all theories expressed in minimal deduction modulo. Compared to using Church-style proof-terms, this method provides both a simpler definition of the criterion and a simpler proof of its completeness.
Abstract unordered and ordered trees CRDT
Venue: arXiv cs.DS 2012
Year: 2012

Trees are fundamental data structure for many areas of computer science and system engineering. In this report, we show how to ensure eventual consistency of optimistically replicated trees. In optimistic replication, the different replicas of a distributed system are allowed to diverge but should eventually reach the same value if no more mutations occur. A new method to ensure eventual consistency is to design Conflict-free Replicated Data Types (CRDT). In this report, we design a collection of tree CRDT using existing set CRDTs. The remaining concurrency problems particular to tree data structure are resolved using one or two layers of correction algorithm. For each of these layer, we propose different and independent policies. Any combination of set CRDT and policies can be constructed, giving to the distributed application programmer the entire control of the behavior of the shared data in face of concurrent mutations. We also propose to order these trees by adding a positioning layer which is also independent to obtain a collection of ordered tree CRDTs.
Spectrum Sensing in Cognitive Radio Networks: Performance Evaluation and Optimization
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies cooperative spectrum sensing in cognitive radio networks where secondary users collect local energy statistics and report their findings to a secondary base station, i.e., a fusion center. First, the average error probability is quantitively analyzed to capture the dynamic nature of both observation and fusion channels, assuming fixed amplifier gains for relaying local statistics to the fusion center. Second, the system level overhead of cooperative spectrum sensing is addressed by considering both the local processing cost and the transmission cost. Local processing cost incorporates the overhead of sample collection and energy calculation that must be conducted by each secondary user; the transmission cost accounts for the overhead of forwarding the energy statistic computed at each secondary user to the fusion center. Results show that when jointly designing the number of collected energy samples and transmission amplifier gains, only one secondary user needs to be actively engaged in spectrum sensing. Furthermore, when number of energy samples or amplifier gains are fixed, closed form expressions for optimal solutions are derived and a generalized water-filling algorithm is provided.