OpenRaiser/Intern-Atlas huggingface dataset:
Quantifying the implicit process flow abstraction in SBGN-PD diagrams with Bio-PEPA
Venue: arXiv cs.PL 2009
Year: 2009

For a long time biologists have used visual representations of biochemical networks to gain a quick overview of important structural properties. Recently SBGN, the Systems Biology Graphical Notation, has been developed to standardise the way in which such graphical maps are drawn in order to facilitate the exchange of information. Its qualitative Process Diagrams (SBGN-PD) are based on an implicit Process Flow Abstraction (PFA) that can also be used to construct quantitative representations, which can be used for automated analyses of the system. Here we explicitly describe the PFA that underpins SBGN-PD and define attributes for SBGN-PD glyphs that make it possible to capture the quantitative details of a biochemical reaction network. We implemented SBGNtext2BioPEPA, a tool that demonstrates how such quantitative details can be used to automatically generate working Bio-PEPA code from a textual representation of SBGN-PD that we developed. Bio-PEPA is a process algebra that was designed for implementing quantitative models of concurrent biochemical reaction systems. We use this approach to compute the expected delay between input and output using deterministic and stochastic simulations of the MAPK signal transduction cascade. The scheme developed here is general and can be easily adapted to other output formalisms.
Tracking object's type changes with fuzzy based fusion rule
Venue: arXiv cs.AI 2009
Year: 2009

In this paper the behavior of three combinational rules for temporal/sequential attribute data fusion for target type estimation are analyzed. The comparative analysis is based on: Dempster's fusion rule proposed in Dempster-Shafer Theory; Proportional Conflict Redistribution rule no. 5 (PCR5), proposed in Dezert-Smarandache Theory and one alternative class fusion rule, connecting the combination rules for information fusion with particular fuzzy operators, focusing on the t-norm based Conjunctive rule as an analog of the ordinary conjunctive rule and t-conorm based Disjunctive rule as an analog of the ordinary disjunctive rule. The way how different t-conorms and t-norms functions within TCN fusion rule influence over target type estimation performance is studied and estimated.
Tool-Assisted Multi-Facet Analysis of Formal Specifications (Using Alelier-B and ProB)
Venue: arXiv cs.SE 2009
Year: 2009

Tool-assisted analysis of software systems and convenient guides to practise the formal methods are still motivating challenges. This article addresses these challenges. We ex periment on analysing a formal specification from multiple aspects. The B method and the Atelier-B tool are used for formal specifications, for safety property analysis and for refinements. The ProB tool is used to supplement the study with model checking; it helps to discover errors and there fore to improve the former specifications.
A Generalized Recursive Algorithm for Binary Multiplication based on Vedic Mathematics
Venue: arXiv cs.DS 2009
Year: 2009

A generalized algorithm for multiplication is proposed through recursive application of the Nikhilam Sutra from Vedic Mathematics, operating in radix - 2 number system environment suitable for digital platforms. Statistical analysis has been carried out based on the number of recursions profile as a function of the smaller multiplicand. The proposed algorithm is efficient for smaller multiplicands as well, unlike most of the asymptotically fast algorithms. Further, a basic block schematic of Hardware Implementation of our algorithm is suggested to exploit parallelism and speed up the implementation of the algorithm in a multiprocessor environment.
Enhancing network transmission capacity by efficiently allocating node capability
Venue: arXiv cs.NI 2009
Year: 2009

A network's transmission capacity is the maximal rate of traffic inflow that the network can handle without causing congestion. Here we study how to enhance this quantity by redistributing the capability of individual nodes while preserving the total sum of node capability. We propose a practical and effective node-capability allocation scheme which allocates a node's capability based on the local knowledge of the node's connectivity. We show the scheme enhances the transmission capacity by two orders of magnitude for networks with heterogenous structures.
Optimal Multiplexing Gain of K-user Line-of-Sight Interference Channels with Polarization
Venue: arXiv cs.IT 2009
Year: 2009

We consider the multiplexing gain (MUXG) of the fully connected K-user line-of-sight (LOS) interference channels (ICs). A polarimetric antenna composed of 3 orthogonal electric dipoles and 3 orthogonal magnetic dipoles is considered where all 6 dipoles are co-located. In case of K-user IC with single polarization, the maximum achievable MUXG is K regardless of the number of transmit and receive antennas because of the key-hole effect. With polarization, a trivial upper bound on the MUXG is 2K. We propose a zero forcing (ZF) scheme for the K-user LOS IC, where each user uses one or more polarimetric antennas. By using the proposed ZF scheme, we find minimal antenna configurations that achieve this bound for K <= 5. For K > 5, we show that the optimal MUXG of 2K is achieved with M = (K+1)/6 polarimetric antennas at each user.
Multiple Cross-Layer Design Based Complete Architecture for Mobile Adhoc Networks
Venue: arXiv cs.NI 2009
Year: 2009

Different cross layer design for mobile adhoc network focuses on different optimization purpose, different Quality of Service (QoS) metric and the functions like delay, priority handling, security, etc. Existing cross layer designs provide individual solution for congestion control, fault tolerance, power conservation, energy minimization and flow control and the major drawback is of high cost and overhead. In this paper, we propose to design multiple cross layer design based architecture to provide a combined solution for link failure management, power conservation, congestion control and admission control. By simulation results, we show that the average end to end delay, average energy consumption and the packet loss are considerably reduced with the increase in high throughput and good delivery ratio.
Decreasing Diagrams and Relative Termination
Venue: arXiv cs.LO 2009
Year: 2009

In this paper we use the decreasing diagrams technique to show that a left-linear term rewrite system R is confluent if all its critical pairs are joinable and the critical pair steps are relatively terminating with respect to R. We further show how to encode the rule-labeling heuristic for decreasing diagrams as a satisfiability problem. Experimental data for both methods are presented.
Can we debug the Universe?
Venue: arXiv cs.OH 2009
Year: 2009

Roughly, the Church-Turing thesis is a hypothesis that describes exactly what can be computed by any real or feasible conceptual computing device. Generally speaking, the computational metaphor is the idea that everything, including the universe itself, has a computational nature. However, if the Church-Turing thesis is not valid, then does it make sense to expect the construction of a computer program capable of simulating the whole Universe? In the lights of hypercomputation, the scientific discipline that is about computing beyond the Church-Turing barrier, the most natural answer to this question is: No. This note is a justification of this answer and its deeper meaning based on arguments from physics, the philosophy of the mind, and, of course, (hyper)computability theory.
Average-Time Games on Timed Automata
Venue: arXiv cs.GT 2009
Year: 2009

An average-time game is played on the infinite graph of configurations of a finite timed automaton. The two players, Min and Max, construct an infinite run of the automaton by taking turns to perform a timed transition. Player Min wants to minimise the average time per transition and player Max wants to maximise it. A solution of average-time games is presented using a reduction to average-price game on a finite graph. A direct consequence is an elementary proof of determinacy for average-time games. This complements our results for reachability-time games and partially solves a problem posed by Bouyer et al., to design an algorithm for solving average-price games on priced timed automata. The paper also establishes the exact computational complexity of solving average-time games: the problem is EXPTIME-complete for timed automata with at least two clocks.
An Immune Inspired Approach to Anomaly Detection
Venue: arXiv cs.AI 2009
Year: 2009

The immune system provides a rich metaphor for computer security: anomaly detection that works in nature should work for machines. However, early artificial immune system approaches for computer security had only limited success. Arguably, this was due to these artificial systems being based on too simplistic a view of the immune system. We present here a second generation artificial immune system for process anomaly detection. It improves on earlier systems by having different artificial cell types that process information. Following detailed information about how to build such second generation systems, we find that communication between cells types is key to performance. Through realistic testing and validation we show that second generation artificial immune systems are capable of anomaly detection beyond generic system policies. The paper concludes with a discussion and outline of the next steps in this exciting area of computer security.
b-Bit Minwise Hashing
Venue: arXiv cs.DS 2009
Year: 2009

This paper establishes the theoretical framework of b-bit minwise hashing. The original minwise hashing method has become a standard technique for estimating set similarity (e.g., resemblance) with applications in information retrieval, data management, social networks and computational advertising. By only storing the lowest $b$ bits of each (minwise) hashed value (e.g., b=1 or 2), one can gain substantial advantages in terms of computational efficiency and storage space. We prove the basic theoretical results and provide an unbiased estimator of the resemblance for any b. We demonstrate that, even in the least favorable scenario, using b=1 may reduce the storage space at least by a factor of 21.3 (or 10.7) compared to using b=64 (or b=32), if one is interested in resemblance > 0.5.
Sum-capacity of Interference Channels with a Local View: Impact of Distributed Decisions
Venue: arXiv cs.IT 2009
Year: 2009

Due to the large size of wireless networks, it is often impractical for nodes to track changes in the complete network state. As a result, nodes have to make distributed decisions about their transmission and reception parameters based on their local view of the network. In this paper, we characterize the impact of distributed decisions on the global network performance in terms of achievable sum-rates. We first formalize the concept of local view by proposing a protocol abstraction using the concept of local message passing. In the proposed protocol, nodes forward information about the network state to other neighboring nodes, thereby allowing network state information to trickle to all the nodes. The protocol proceeds in rounds, where all transmitters send a message followed by a message by all receivers. The number of rounds then provides a natural metric to quantify the extent of local information at each node. We next study three network connectivities, Z-channel, a three-user double Z-channel and a reduced-parametrization $K$-user stacked Z-channel. In each case, we characterize achievable sum-rate with partial message passing leading to three main results. First, in many cases, nodes can make distributed decisions with only local information about the network and can still achieve the same sum-capacity as can be attained with global information irrespective of the actual channel gains. Second, for the case of three-user double Z-channel, we show that universal optimality is not achievable if the per node information is below a threshold. Third, using reduced parametrization $K$-user channel, we show that very few protocol rounds are needed for the case of very weak or very strong interference.
Constraint-based Local Move Definitions for Lattice Protein Models Including Side Chains
Venue: arXiv cs.CE 2009
Year: 2009

The simulation of a protein's folding process is often done via stochastic local search, which requires a procedure to apply structural changes onto a given conformation. Here, we introduce a constraint-based approach to enumerate lattice protein structures according to k-local moves in arbitrary lattices. Our declarative description is much more flexible for extensions than standard operational formulations. It enables a generic calculation of k-local neighbors in backbone-only and side chain models. We exemplify the procedure using a simple hierarchical folding scheme.
Preamble-Based Channel Estimation for CP-OFDM and OFDM/OQAM Systems: A Comparative Study
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, preamble-based least squares (LS) channel estimation in OFDM systems of the QAM and offset QAM (OQAM) types is considered, in both the frequency and the time domains. The construction of optimal (in the mean squared error (MSE) sense) preambles is investigated, for both the cases of full (all tones carrying pilot symbols) and sparse (a subset of pilot tones, surrounded by nulls or data) preambles. The two OFDM systems are compared for the same transmit power, which, for cyclic prefix (CP) based OFDM/QAM, also includes the power spent for CP transmission. OFDM/OQAM, with a sparse preamble consisting of equipowered and equispaced pilots embedded in zeros, turns out to perform at least as well as CP-OFDM. Simulations results are presented that verify the analysis.
Studying Maximum Information Leakage Using Karush-Kuhn-Tucker Conditions
Venue: arXiv cs.CR 2009
Year: 2009

When studying the information leakage in programs or protocols, a natural question arises: "what is the worst case scenario?". This problem of identifying the maximal leakage can be seen as a channel capacity problem in the information theoretical sense. In this paper, by combining two powerful theories: Information Theory and Karush-Kuhn-Tucker conditions, we demonstrate a very general solution to the channel capacity problem. Examples are given to show how our solution can be applied to practical contexts of programs and anonymity protocols, and how this solution generalizes previous approaches to this problem.
Infinitary Combinatory Reduction Systems: Confluence
Venue: arXiv cs.LO 2009
Year: 2009

We study confluence in the setting of higher-order infinitary rewriting, in particular for infinitary Combinatory Reduction Systems (iCRSs). We prove that fully-extended, orthogonal iCRSs are confluent modulo identification of hypercollapsing subterms. As a corollary, we obtain that fully-extended, orthogonal iCRSs have the normal form property and the unique normal form property (with respect to reduction). We also show that, unlike the case in first-order infinitary rewriting, almost non-collapsing iCRSs are not necessarily confluent.
Secure Communication in the Low-SNR Regime
Venue: arXiv cs.IT 2009
Year: 2009

Secrecy capacity of a multiple-antenna wiretap channel is studied in the low signal-to-noise ratio (SNR) regime. Expressions for the first and second derivatives of the secrecy capacity with respect to SNR at SNR = 0 are derived. Transmission strategies required to achieve these derivatives are identified. In particular, it is shown that it is optimal in the low-SNR regime to transmit in the maximal-eigenvalue eigenspace of Phi = H_m* H_m - N_m/N_e H_e* H_e where H_m and H_e denote the channel matrices associated with the legitimate receiver and eavesdropper, respectively, and N_m and N_e are the noise variances at the receiver and eavesdropper, respectively. Energy efficiency is analyzed by finding the minimum bit energy required for secure and reliable communications, and the wideband slope. Increased bit energy requirements under secrecy constraints are quantified. Finally, the impact of fading is investigated, and the benefits of fading in terms of energy efficiency are shown.
An empirical study of spatial and transpatial social networks using Bluetooth and Facebook
Venue: arXiv cs.CY 2009
Year: 2009

This study provides insights into the quantitative similarities, differences and relationships between users' spatial, face-to-face, urban social networks and their transpatial, online counterparts. We explore and map the social ties within a cohort of 2602 users, and how those ties are mediated via physical co-presence and online tools. Our analysis focused on isolating two distinct segments of the social network: one mediated by physical co-presence, and the other mediated by Facebook. Our results suggest that as a whole the networks exhibit homogeneous characteristics, but individuals' involvement in those networks varies considerably. Furthermore this study provides a methodological approach for jointly analysing spatial & transpatial networks utilising pervasive and ubiquitous technology.
Fair Exchange in Strand Spaces
Venue: arXiv cs.CR 2009
Year: 2009

Many cryptographic protocols are intended to coordinate state changes among principals. Exchange protocols coordinate delivery of new values to the participants, e.g. additions to the set of values they possess. An exchange protocol is fair if it ensures that delivery of new values is balanced: If one participant obtains a new possession via the protocol, then all other participants will, too. Fair exchange requires progress assumptions, unlike some other protocol properties. The strand space model is a framework for design and verification of cryptographic protocols. A strand is a local behavior of a single principal in a single session of a protocol. A bundle is a partially ordered global execution built from protocol strands and adversary activities. The strand space model needs two additions for fair exchange protocols. First, we regard the state as a multiset of facts, and we allow strands to cause changes in this state via multiset rewriting. Second, progress assumptions stipulate that some channels are resilient-and guaranteed to deliver messages-and some principals are assumed not to stop at certain critical steps. This method leads to proofs of correctness that cleanly separate protocol properties, such as authentication and confidentiality, from invariants governing state evolution. G. Wang's recent fair exchange protocol illustrates the approach.
Nonapproximablity of the Normalized Information Distance
Venue: arXiv cs.CC 2009
Year: 2009

Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of the file involved, using a real-world compression program. This practical application is called `normalized compression distance' and it is trivially computable. It is a parameter-free similarity measure based on compression, and is used in pattern recognition, data mining, phylogeny, clustering, and classification. The complexity properties of its theoretical precursor, the NID, have been open. We show that the NID is neither upper semicomputable nor lower semicomputable up to any reasonable precision.
Optimised access to user analysis data using the gLite DPM
Venue: arXiv cs.DC 2009
Year: 2009

The ScotGrid distributed Tier-2 now provides more that 4MSI2K and 500TB for LHC computing, which is spread across three sites at Durham, Edinburgh and Glasgow. Tier-2 sites have a dual role to play in the computing models of the LHC VOs. Firstly, their CPU resources are used for the generation of Monte Carlo event data. Secondly, the end user analysis data is distributed across the grid to the site's storage system and held on disk ready for processing by physicists' analysis jobs. In this paper we show how we have designed the ScotGrid storage and data management resources in order to optimise access by physicists to LHC data. Within ScotGrid, all sites use the gLite DPM storage manager middleware. Using the EGEE grid to submit real ATLAS analysis code to process VO data stored on the ScotGrid sites, we present an analysis of the performance of the architecture at one site, and procedures that may be undertaken to improve such. The results will be presented from the point of view of the end user (in terms of number of events processed/second) and from the point of view of the site, which wishes to minimise load and the impact that analysis activity has on other users of the system.
Convolution operations arising from Vandermonde matrices
Venue: arXiv cs.IT 2009
Year: 2009

Different types of convolution operations involving large Vandermonde matrices are considered. The convolutions parallel those of large Gaussian matrices and additive and multiplicative free convolution. First additive and multiplicative convolution of Vandermonde matrices and deterministic diagonal matrices are considered. After this, several cases of additive and multiplicative convolution of two independent Vandermonde matrices are considered. It is also shown that the convergence of any combination of Vandermonde matrices is almost sure. We will divide the considered convolutions into two types: those which depend on the phase distribution of the Vandermonde matrices, and those which depend only on the spectra of the matrices. A general criterion is presented to find which type applies for any given convolution. A simulation is presented, verifying the results. Implementations of all considered convolutions are provided and discussed, together with the challenges in making these implementations efficient. The implementation is based on the technique of Fourier-Motzkin elimination, and is quite general as it can be applied to virtually any combination of Vandermonde matrices. Generalizations to related random matrices, such as Toeplitz and Hankel matrices, are also discussed.
Fast Algebraic Attacks and Decomposition of Symmetric Boolean Functions
Venue: arXiv cs.CR 2009
Year: 2009

Algebraic and fast algebraic attacks are power tools to analyze stream ciphers. A class of symmetric Boolean functions with maximum algebraic immunity were found vulnerable to fast algebraic attacks at EUROCRYPT'06. Recently, the notion of AAR (algebraic attack resistant) functions was introduced as a unified measure of protection against both classical algebraic and fast algebraic attacks. In this correspondence, we first give a decomposition of symmetric Boolean functions, then we show that almost all symmetric Boolean functions, including these functions with good algebraic immunity, behave badly against fast algebraic attacks, and we also prove that no symmetric Boolean functions are AAR functions. Besides, we improve the relations between algebraic degree and algebraic immunity of symmetric Boolean functions.
Computing modular correspondences for abelian varieties
Venue: arXiv cs.SC 2009
Year: 2009

The aim of this paper is to give a higher dimensional equivalent of the classical modular polynomials $Φ_\ell(X,Y)$. If $j$ is the $j$-invariant associated to an elliptic curve $E_k$ over a field $k$ then the roots of $Φ_\ell(j,X)$ correspond to the $j$-invariants of the curves which are $\ell$-isogeneous to $E_k$. Denote by $X_0(N)$ the modular curve which parametrizes the set of elliptic curves together with a $N$-torsion subgroup. It is possible to interpret $Φ_\ell(X,Y)$ as an equation cutting out the image of a certain modular correspondence $X_0(\ell) \to X_0(1) \times X_0(1)$ in the product $X_0(1) \times X_0(1)$. Let $g$ be a positive integer and $\overn \in \N^g$. We are interested in the moduli space that we denote by $\Mn$ of abelian varieties of dimension $g$ over a field $k$ together with an ample symmetric line bundle $\pol$ and a symmetric theta structure of type $\overn$. If $\ell$ is a prime and let $\overl=(\ell, ..., \ell)$, there exists a modular correspondence $\Mln \to \Mn \times \Mn$. We give a system of algebraic equations defining the image of this modular correspondence.