OpenRaiser/Intern-Atlas huggingface dataset:
Folk Theorems on the Correspondence between State-Based and Event-Based Systems
Venue: arXiv cs.LO 2010
Year: 2010

Kripke Structures and Labelled Transition Systems are the two most prominent semantic models used in concurrency theory. Both models are commonly believed to be equi-expressive. One can find many ad-hoc embeddings of one of these models into the other. We build upon the seminal work of De Nicola and Vaandrager that firmly established the correspondence between stuttering equivalence in Kripke Structures and divergence-sensitive branching bisimulation in Labelled Transition Systems. We show that their embeddings can also be used for a range of other equivalences of interest, such as strong bisimilarity, simulation equivalence, and trace equivalence. Furthermore, we extend the results by De Nicola and Vaandrager by showing that there are additional translations that allow one to use minimisation techniques in one semantic domain to obtain minimal representatives in the other semantic domain for these equivalences.
Golden and Alternating, fast simple O(lg n) algorithms for Fibonacci
Venue: arXiv cs.DM 2010
Year: 2010

Two very fast and simple O(lg n) algorithms for individual Fibonacci numbers are given and compared to competing algorithms. A simple O(lg n) recursion is derived that can also be applied to Lucas. A formula is given to estimate the largest n, where F_n does not overflow the implementation's data type. The danger of timing runs on input that is too large for the computer representation leads to false research results.
Digital Identity in The Absence of Authorities: A New Socio-Technical Approach
Venue: arXiv cs.CY 2010
Year: 2010

On the Internet large service providers tend to control the digital identities of users. These defacto identity authorities wield significant power over users, compelling them to comply with non-negotiable terms, before access to services is granted. In doing so, users expose themselves to privacy risks, manipulation and exploitation via direct marketing. Against this backdrop, the emerging areas of Digital Ecosystems and user-centric identity emphasise decentralised environments with independent self-determining entities that control their own data and identity. We show that recent advances in user-centric identity, federated identity and trust have prepared the ground for decentralised identity provisioning. We show how social trust, rather than blind deference to authorities, can provide a basis for identity, where risks can be weighed and compared rather than merely accepted. Fundamentally, we are considering the move from authority-centric centralised identity provisioning to user-centric distributed identity provisioning. Finally, we highlight the potential impacts of distributed identity provisioning in the Information Society and give a brief roadmap for its general implementation and adoption.
On Zone-Based Analysis of Duration Probabilistic Automata
Venue: arXiv cs.FL 2010
Year: 2010

We propose an extension of the zone-based algorithmics for analyzing timed automata to handle systems where timing uncertainty is considered as probabilistic rather than set-theoretic. We study duration probabilistic automata (DPA), expressing multiple parallel processes admitting memoryfull continuously-distributed durations. For this model we develop an extension of the zone-based forward reachability algorithm whose successor operator is a density transformer, thus providing a solution to verification and performance evaluation problems concerning acyclic DPA (or the bounded-horizon behavior of cyclic DPA).
Polynomial-time Computation of Exact Correlated Equilibrium in Compact Games
Venue: arXiv cs.GT 2010
Year: 2010

In a landmark paper, Papadimitriou and Roughgarden described a polynomial-time algorithm ("Ellipsoid Against Hope") for computing sample correlated equilibria of concisely-represented games. Recently, Stein, Parrilo and Ozdaglar showed that this algorithm can fail to find an exact correlated equilibrium, but can be easily modified to efficiently compute approximate correlated equilibria. Currently, it remains unresolved whether the algorithm can be modified to compute an exact correlated equilibrium. We show that it can, presenting a variant of the Ellipsoid Against Hope algorithm that guarantees the polynomial-time identification of exact correlated equilibrium. Our new algorithm differs from the original primarily in its use of a separation oracle that produces cuts corresponding to pure-strategy profiles. As a result, we no longer face the numerical precision issues encountered by the original approach, and both the resulting algorithm and its analysis are considerably simplified. Our new separation oracle can be understood as a derandomization of Papadimitriou and Roughgarden's original separation oracle via the method of conditional probabilities. Also, the equilibria returned by our algorithm are distributions with polynomial-sized supports, which are simpler (in the sense of being representable in fewer bits) than the mixtures of product distributions produced previously; no tractable algorithm has previously been proposed for identifying such equilibria.
A Novel Approach Towards Cost Effective Region-Based Group Key Agreement Protocol for Peer - to - Peer Information Sharing in Mobile Ad Hoc Networks
Venue: arXiv cs.CR 2010
Year: 2010

Peer-to-peer systems have gained a lot of attention as information sharing systems for the widespread exchange of resources and voluminous information that is easily accessible among thousands of users. However, current peer-to-peer information sharing systems work mostly on wired networks. With the growing number of communication-equipped mobile devices that can self-organize into infrastructure-less communication platform, namely mobile ad hoc networks (MANETs), peer-to-peer information sharing over MANETs becomes a promising research area. In this paper, we propose a Region-Based structure that enables efficient and secure peer-to-peer information sharing over MANETs. The implementation shows that the proposed scheme is Secure, scalable, efficient, and adaptive to node mobility and provides Reliable information sharing.
Finite Model Finding for Parameterized Verification
Venue: arXiv cs.LO 2010
Year: 2010

In this paper we investigate to which extent a very simple and natural "reachability as deducibility" approach, originated in the research in formal methods in security, is applicable to the automated verification of large classes of infinite state and parameterized systems. The approach is based on modeling the reachability between (parameterized) states as deducibility between suitable encodings of states by formulas of first-order predicate logic. The verification of a safety property is reduced to a pure logical problem of finding a countermodel for a first-order formula. The later task is delegated then to the generic automated finite model building procedures. In this paper we first establish the relative completeness of the finite countermodel finding method (FCM) for a class of parameterized linear arrays of finite automata. The method is shown to be at least as powerful as known methods based on monotonic abstraction and symbolic backward reachability. Further, we extend the relative completeness of the approach and show that it can solve all safety verification problems which can be solved by the traditional regular model checking.
Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning
Venue: arXiv cs.DS 2010
Year: 2010

The number of triangles is a computationally expensive graph statistic which is frequently used in complex network analysis (e.g., transitivity ratio), in various random graph models (e.g., exponential random graph model) and in important real world applications such as spam detection, uncovering of the hidden thematic structure of the Web and link recommendation. Counting triangles in graphs with millions and billions of edges requires algorithms which run fast, use small amount of space, provide accurate estimates of the number of triangles and preferably are parallelizable. In this paper we present an efficient triangle counting algorithm which can be adapted to the semistreaming model. The key idea of our algorithm is to combine the sampling algorithm of Tsourakakis et al. and the partitioning of the set of vertices into a high degree and a low degree subset respectively as in the Alon, Yuster and Zwick work treating each set appropriately. We obtain a running time $O \left(m + \frac{m^{3/2} Δ\log{n}}{t ε^2} \right)$ and an $ε$ approximation (multiplicative error), where $n$ is the number of vertices, $m$ the number of edges and $Δ$ the maximum number of triangles an edge is contained. Furthermore, we show how this algorithm can be adapted to the semistreaming model with space usage $O\left(m^{1/2}\log{n} + \frac{m^{3/2} Δ\log{n}}{t ε^2} \right)$ and a constant number of passes (three) over the graph stream. We apply our methods in various networks with several millions of edges and we obtain excellent results. Finally, we propose a random projection based method for triangle counting and provide a sufficient condition to obtain an estimate with low variance.
Regularized Risk Minimization by Nesterov's Accelerated Gradient Methods: Algorithmic Extensions and Empirical Studies
Venue: arXiv cs.LG 2010
Year: 2010

Nesterov's accelerated gradient methods (AGM) have been successfully applied in many machine learning areas. However, their empirical performance on training max-margin models has been inferior to existing specialized solvers. In this paper, we first extend AGM to strongly convex and composite objective functions with Bregman style prox-functions. Our unifying framework covers both the $\infty$-memory and 1-memory styles of AGM, tunes the Lipschiz constant adaptively, and bounds the duality gap. Then we demonstrate various ways to apply this framework of methods to a wide range of machine learning problems. Emphasis will be given on their rate of convergence and how to efficiently compute the gradient and optimize the models. The experimental results show that with our extensions AGM outperforms state-of-the-art solvers on max-margin models.
A New Email Retrieval Ranking Approach
Venue: arXiv cs.IR 2010
Year: 2010

Email Retrieval task has recently taken much attention to help the user retrieve the email(s) related to the submitted query. Up to our knowledge, existing email retrieval ranking approaches sort the retrieved emails based on some heuristic rules, which are either search clues or some predefined user criteria rooted in email fields. Unfortunately, the user usually does not know the effective rule that acquires best ranking related to his query. This paper presents a new email retrieval ranking approach to tackle this problem. It ranks the retrieved emails based on a scoring function that depends on crucial email fields, namely subject, content, and sender. The paper also proposes an architecture to allow every user in a network/group of users to be able, if permissible, to know the most important network senders who are interested in his submitted query words. The experimental evaluation on Enron corpus prove that our approach outperforms known email retrieval ranking approaches.
Level Shifter Design for Low Power Applications
Venue: arXiv cs.OH 2010
Year: 2010

With scaling of Vt sub-threshold leakage power is increasing and expected to become significant part of total power consumption In present work three new configurations of level shifters for low power application in 0.35μm technology have been presented. The proposed circuits utilize the merits of stacking technique with smaller leakage current and reduction in leakage power. Conventional level shifter has been improved by addition of three NMOS transistors, which shows total power consumption of 402.2264pW as compared to 0.49833nW with existing circuit. Single supply level shifter has been modified with addition of two NMOS transistors that gives total power consumption of 108.641pW as compared to 31.06nW. Another circuit, contention mitigated level shifter (CMLS) with three additional transistors shows total power consumption of 396.75pW as compared to 0.4937354nW. Three proposed circuit's shows better performance in terms of power consumption with a little conciliation in delay. Output level of 3.3V has been obtained with input pulse of 1.6V for all proposed circuits.
Ciphertext Policy Attribute based Encryption with anonymous access policy
Venue: arXiv cs.CR 2010
Year: 2010

In Ciphertext Policy Attribute based Encryption scheme, the encryptor can fix the policy, who can decrypt the encrypted message. The policy can be formed with the help of attributes. In CP-ABE, access policy is sent along with the ciphertext. We propose a method in which the access policy need not be sent along with the ciphertext, by which we are able to preserve the privacy of the encryptor. The proposed construction is provably secure under Decision Bilinear Diffe-Hellman assumption.
Performance Analysis of Contention Window Cheating Misbehaviors in Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

Mobile Ad Hoc Network (MANET) is a collection of nodes that can be rapidly deployed as a multi-hop network without the aid of any centralized administration. Misbehavior is challenged by bandwidth and energy efficient medium access control and fair share of throughput. Node misbehavior plays an important role in MANET. In this survey, few of the contention window misbehavior is reviewed and compared. The contention window cheating either minimizes the active communication of the network or reduces bandwidth utilization of a particular node. The classification presented is in no case unique but summarizes the chief characteristics of many published proposals for contention window cheating. After getting insight into the different contention window misbehavior, few of the enhancements that can be done to improve the existing contention window are suggested. The purpose of this paper is to facilitate the research efforts in combining the existing solutions to offer more efficient methods to reduce contention window cheating mechanisms.
Heuristic Approach of Automated Test Data Generation for Program having Array of Different Dimensions and Loops with Variable Number of Iteration
Venue: arXiv cs.SE 2010
Year: 2010

Normally, program execution spends most of the time on loops. Automated test data generation devotes special attention to loops for better coverage. Automated test data generation for programs having loops with variable number of iteration and variable length array is a challenging problem. It is so because the number of paths may increase exponentially with the increase of array size for some programming constructs, like merge sort. We propose a method that finds heuristic for different types of programming constructs with loops and arrays. Linear search, Bubble sort, merge sort, and matrix multiplication programs are included in an attempt to highlight the difference in execution between single loop, variable length array and nested loops with one and two dimensional arrays. We have used two parameters/heuristics to predict the minimum number of iterations required for generating automated test data. They are longest path level (kL) and saturation level (kS). The proceedings of our work includes the instrumentation of source code at the elementary level, followed by the application of the random inputs until all feasible paths or all paths having longest paths are collected. However, duplicate paths are avoided by using a filter. Our test data is the random numbers that cover each feasible path.
Gaussian Process Techniques for Wireless Communications
Venue: arXiv cs.IT 2010
Year: 2010

Bayesian filtering is a general framework for recursively estimating the state of a dynamical system. Classical solutions such that Kalman filter and Particle filter are introduced in this report. Gaussian processes have been introduced as a non-parametric technique for system estimation from supervision learning. For the thesis project, we intend to propose a new, general methodology for inference and learning in non-linear state-space models probabilistically incorporating with the Gaussian process model estimation.
Soil Classification Using GATree
Venue: arXiv cs.NE 2010
Year: 2010

This paper details the application of a genetic programming framework for classification of decision tree of Soil data to classify soil texture. The database contains measurements of soil profile data. We have applied GATree for generating classification decision tree. GATree is a decision tree builder that is based on Genetic Algorithms (GAs). The idea behind it is rather simple but powerful. Instead of using statistic metrics that are biased towards specific trees we use a more flexible, global metric of tree quality that try to optimize accuracy and size. GATree offers some unique features not to be found in any other tree inducers while at the same time it can produce better results for many difficult problems. Experimental results are presented which illustrate the performance of generating best decision tree for classifying soil texture for soil data set.
Providing Group Anonymity Using Wavelet Transform
Venue: arXiv cs.CR 2010
Year: 2010

Providing public access to unprotected digital data can pose a threat of unwanted disclosing the restricted information. The problem of protecting such information can be divided into two main subclasses, namely, individual and group data anonymity. By group anonymity we define protecting important data patterns, distributions, and collective features which cannot be determined through analyzing individual records only. An effective and comparatively simple way of solving group anonymity problem is doubtlessly applying wavelet transform. It's easy-to-implement, powerful enough, and might produce acceptable results if used properly. In the paper, we present a novel method of using wavelet transform for providing group anonymity; it is gained through redistributing wavelet approximation values, along with simultaneous fixing data mean value and leaving wavelet details unchanged (or proportionally altering them). Moreover, we provide a comprehensive example to illustrate the method.
Logics and Games for True Concurrency
Venue: arXiv cs.LO 2010
Year: 2010

We study the underlying mathematical properties of various partial order models of concurrency based on transition systems, Petri nets, and event structures, and show that the concurrent behaviour of these systems can be captured in a uniform way by two simple and general dualities of local behaviour. Such dualities are used to define new mu-calculi and logic games for the analysis of concurrent systems with partial order semantics. Some results of this work are: the definition of a number of mu-calculi which, in some classes of systems, induce the same identifications as some of the best known bisimulation equivalences for concurrency; and the definition of (infinite) higher-order logic games for bisimulation and model-checking, where the players of the games are given (local) monadic second-order power on the sets of elements they are allowed to play. More specifically, we show that our games are sound and complete, and therefore, determined; moreover, they are decidable in the finite case and underpin novel decision procedures for bisimulation and model-checking. Since these mu-calculi and logic games generalise well-known fixpoint logics and game-theoretic decision procedures for concurrent systems with interleaving semantics, the results herein give some of the groundwork for the design of a logic-based, game-theoretic framework for studying, in a uniform way, several concurrent systems regardless of whether they have an interleaving or a partial order semantics.
Quantum computation with devices whose contents are never read
Venue: arXiv cs.CC 2010
Year: 2010

In classical computation, a "write-only memory" (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic or probabilistic) classical computer brings no advantage. We prove that quantum computers that are augmented with WOM can solve problems that neither a classical computer with WOM nor a quantum computer without WOM can solve, when all other resource bounds are equal. We focus on realtime quantum finite automata, and examine the increase in their power effected by the addition of WOMs with different access modes and capacities. Some problems that are unsolvable by two-way probabilistic Turing machines using sublogarithmic amounts of read/write memory are shown to be solvable by these enhanced automata.
Deduction as Reduction
Venue: arXiv cs.LO 2010
Year: 2010

Deduction systems and graph rewriting systems are compared within a common categorical framework. This leads to an improved deduction method in diagrammatic logics.
Optimal Binary Search Trees with Near Minimal Height
Venue: arXiv cs.DS 2010
Year: 2010

Suppose we have n keys, n access probabilities for the keys, and n+1 access probabilities for the gaps between the keys. Let h_min(n) be the minimal height of a binary search tree for n keys. We consider the problem to construct an optimal binary search tree with near minimal height, i.e.\ with height h <= h_min(n) + Delta for some fixed Delta. It is shown, that for any fixed Delta optimal binary search trees with near minimal height can be constructed in time O(n^2). This is as fast as in the unrestricted case. So far, the best known algorithms for the construction of height-restricted optimal binary search trees have running time O(L n^2), whereby L is the maximal permitted height. Compared to these algorithms our algorithm is at least faster by a factor of log n, because L is lower bounded by log n.
Construction of Network Error Correction Codes in Packet Networks
Venue: arXiv cs.IT 2010
Year: 2010

Recently, network error correction coding (NEC) has been studied extensively. Several bounds in classical coding theory have been extended to network error correction coding, especially the Singleton bound. In this paper, following the research line using the extended global encoding kernels proposed in \cite{zhang-correction}, the refined Singleton bound of NEC can be proved more explicitly. Moreover, we give a constructive proof of the attainability of this bound and indicate that the required field size for the existence of network maximum distance separable (MDS) codes can become smaller further. By this proof, an algorithm is proposed to construct general linear network error correction codes including the linear network error correction MDS codes. Finally, we study the error correction capability of random linear network error correction coding. Motivated partly by the performance analysis of random linear network coding \cite{Ho-etc-random}, we evaluate the different failure probabilities defined in this paper in order to analyze the performance of random linear network error correction coding. Several upper bounds on these probabilities are obtained and they show that these probabilities will approach to zero as the size of the base field goes to infinity. Using these upper bounds, we slightly improve on the probability mass function of the minimum distance of random linear network error correction codes in \cite{zhang-random}, as well as the upper bound on the field size required for the existence of linear network error correction codes with degradation at most $d$.
Quantization using Compressive Sensing
Venue: arXiv cs.IT 2010
Year: 2010

The problem of compressing a real-valued sparse source using compressive sensing techniques is studied. The rate distortion optimality of a coding scheme in which compressively sensed signals are quantized and then reconstructed is established when the reconstruction is also required to be sparse. The result holds in general when the distortion constraint is on the expected $p$-norm of error between the source and the reconstruction. A new restricted isometry like property is introduced for this purpose and the existence of matrices that satisfy this property is shown.