OpenRaiser/Intern-Atlas huggingface dataset:
Model Checking Probabilistic Real-Time Properties for Service-Oriented Systems with Service Level Agreements
Venue: arXiv cs.SE 2011
Year: 2011

The assurance of quality of service properties is an important aspect of service-oriented software engineering. Notations for so-called service level agreements (SLAs), such as the Web Service Level Agreement (WSLA) language, provide a formal syntax to specify such assurances in terms of (legally binding) contracts between a service provider and a customer. On the other hand, formal methods for verification of probabilistic real-time behavior have reached a level of expressiveness and efficiency which allows to apply them in real-world scenarios. In this paper, we suggest to employ the recently introduced model of Interval Probabilistic Timed Automata (IPTA) for formal verification of QoS properties of service-oriented systems. Specifically, we show that IPTA in contrast to Probabilistic Timed Automata (PTA) are able to capture the guarantees specified in SLAs directly. A particular challenge in the analysis of IPTA is the fact that their naive semantics usually yields an infinite set of states and infinitely-branching transitions. However, using symbolic representations, IPTA can be analyzed rather efficiently. We have developed the first implementation of an IPTA model checker by extending the PRISM tool and show that model checking IPTA is only slightly more expensive than model checking comparable PTA.
On Erdős-Gallai and Havel-Hakimi algorithms
Venue: arXiv cs.DM 2011
Year: 2011

Havel in 1955, Erdős and Gallai in 1960, Hakimi in 1962, Ruskey, Cohen, Eades and Scott in 1994, Barnes and Savage in 1997, Kohnert in 2004, Tripathi, Venugopalan and West in 2010 proposed a method to decide, whether a sequence of nonnegative integers can be the degree sequence of a simple graph. The running time of their algorithms is $Ω(n^2)$ in worst case. In this paper we propose a new algorithm called EGL (Erdős-Gallai Linear algorithm), whose worst running time is $Θ(n).$ As an application of this quick algorithm we computed the number of the different degree sequences of simple graphs for $24, ...,29$ vertices.
The Capacity of a Class of Multi-Way Relay Channels
Venue: arXiv cs.IT 2011
Year: 2011

The capacity of a class of multi-way relay channels, where L users communicate via a relay (at possibly different rates), is derived for the case where the channel outputs are modular sums of the channel inputs and the receiver noise. The cut-set upper bound to the capacity is shown to be achievable. More specifically, the capacity is achieved using (i) rate splitting, (ii) functional-decode-forward, and (iii) joint source-channel coding. We note that while separate source-channel coding can achieve the common-rate capacity, joint source-channel coding is used to achieve the capacity for the general case where the users are transmitting at different rates.
Linking to Data - Effect on Citation Rates in Astronomy
Venue: arXiv cs.DL 2011
Year: 2011

Is there a difference in citation rates between articles that were published with links to data and articles that were not? Besides being interesting from a purely academic point of view, this question is also highly relevant for the process of furthering science. Data sharing not only helps the process of verification of claims, but also the discovery of new findings in archival data. However, linking to data still is a far cry away from being a "practice", especially where it comes to authors providing these links during the writing and submission process. You need to have both a willingness and a publication mechanism in order to create such a practice. Showing that articles with links to data get higher citation rates might increase the willingness of scientists to take the extra steps of linking data sources to their publications. In this presentation we will show this is indeed the case: articles with links to data result in higher citation rates than articles without such links. The ADS is funded by NASA Grant NNX09AB39G.
VoIP Call Optimization in Diverse Network Scenarios Using Learning Based State-Space Search Technique
Venue: arXiv cs.NI 2011
Year: 2011

A VoIP based call has stringent QoS requirements with respect to delay, jitter, loss, MOS and R-Factor. Various QoS mechanisms implemented to satisfy these requirements must be adaptive under diverse network scenarios and applied in proper sequence, otherwise they may conflict with each other. The objective of this paper is to address the problem of adaptive QoS maintenance and sequential execution of available QoS implementation mechanisms with respect to VoIP under varying network conditions. In this paper, we generalize this problem as state-space problem and solve it. Firstly, we map the problem of QoS optimization into state-space domain and apply incremental heuristic search. We implement the proposed algorithm under various network and user scenarios in a VoIP test-bed for QoS enhancement. Then learning strategy is implemented for refinement of knowledge base to improve the performance of call quality over time. Finally, we discuss the advantages and uniqueness of our approach.
An Information-Theoretic Privacy Criterion for Query Forgery in Information Retrieval
Venue: arXiv cs.IT 2011
Year: 2011

In previous work, we presented a novel information-theoretic privacy criterion for query forgery in the domain of information retrieval. Our criterion measured privacy risk as a divergence between the user's and the population's query distribution, and contemplated the entropy of the user's distribution as a particular case. In this work, we make a twofold contribution. First, we thoroughly interpret and justify the privacy metric proposed in our previous work, elaborating on the intimate connection between the celebrated method of entropy maximization and the use of entropies and divergences as measures of privacy. Secondly, we attempt to bridge the gap between the privacy and the information-theoretic communities by substantially adapting some technicalities of our original work to reach a wider audience, not intimately familiar with information theory and the method of types.
Efficient Capacity Computation and Power Optimization for Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

The capacity or approximations to capacity of various single-source single-destination relay network models has been characterized in terms of the cut-set upper bound. In principle, a direct computation of this bound requires evaluating the cut capacity over exponentially many cuts. We show that the minimum cut capacity of a relay network under some special assumptions can be cast as a minimization of a submodular function, and as a result, can be computed efficiently. We use this result to show that the capacity, or an approximation to the capacity within a constant gap for the Gaussian, wireless erasure, and Avestimehr-Diggavi-Tse deterministic relay network models can be computed in polynomial time. We present some empirical results showing that computing constant-gap approximations to the capacity of Gaussian relay networks with around 300 nodes can be done in order of minutes. For Gaussian networks, cut-set capacities are also functions of the powers assigned to the nodes. We consider a family of power optimization problems and show that they can be solved in polynomial time. In particular, we show that the minimization of the sum of powers assigned to the nodes subject to a minimum rate constraint (measured in terms of cut-set bounds) can be computed in polynomial time. We propose an heuristic algorithm to solve this problem and measure its performance through simulations on random Gaussian networks. We observe that in the optimal allocations most of the power is assigned to a small subset of relays, which suggests that network simplification may be possible without excessive performance degradation.
Hardware Implementation of Successive Cancellation Decoders for Polar Codes
Venue: arXiv cs.AR 2011
Year: 2011

The recently-discovered polar codes are seen as a major breakthrough in coding theory; they provably achieve the theoretical capacity of discrete memoryless channels using the low complexity successive cancellation (SC) decoding algorithm. Motivated by recent developments in polar coding theory, we propose a family of efficient hardware implementations for SC polar decoders. We show that such decoders can be implemented with O(n) processing elements, O(n) memory elements, and can provide a constant throughput for a given target clock frequency. Furthermore, we show that SC decoding can be implemented in the logarithm domain, thereby eliminating costly multiplication and division operations and reducing the complexity of each processing element greatly. We also present a detailed architecture for an SC decoder and provide logic synthesis results confirming the linear growth in complexity of the decoder as the code length increases.
From nominal sets binding to functions and lambda-abstraction: connecting the logic of permutation models with the logic of functions
Venue: arXiv cs.LO 2011
Year: 2011

Permissive-Nominal Logic (PNL) extends first-order predicate logic with term-formers that can bind names in their arguments. It takes a semantics in (permissive-)nominal sets. In PNL, the forall-quantifier or lambda-binder are just term-formers satisfying axioms, and their denotation is functions on nominal atoms-abstraction. Then we have higher-order logic (HOL) and its models in ordinary (i.e. Zermelo-Fraenkel) sets; the denotation of forall or lambda is functions on full or partial function spaces. This raises the following question: how are these two models of binding connected? What translation is possible between PNL and HOL, and between nominal sets and functions? We exhibit a translation of PNL into HOL, and from models of PNL to certain models of HOL. It is natural, but also partial: we translate a restricted subsystem of full PNL to HOL. The extra part which does not translate is the symmetry properties of nominal sets with respect to permutations. To use a little nominal jargon: we can translate names and binding, but not their nominal equivariance properties. This seems reasonable since HOL---and ordinary sets---are not equivariant. Thus viewed through this translation, PNL and HOL and their models do different things, but they enjoy non-trivial and rich subsystems which are isomorphic.
Incremental Learning with Accuracy Prediction of Social and Individual Properties from Mobile-Phone Data
Venue: arXiv cs.SI 2011
Year: 2011

Mobile phones are quickly becoming the primary source for social, behavioral, and environmental sensing and data collection. Today's smartphones are equipped with increasingly more sensors and accessible data types that enable the collection of literally dozens of signals related to the phone, its user, and its environment. A great deal of research effort in academia and industry is put into mining this raw data for higher level sense-making, such as understanding user context, inferring social networks, learning individual features, predicting outcomes, and so on. In this work we investigate the properties of learning and inference of real world data collected via mobile phones over time. In particular, we look at the dynamic learning process over time, and how the ability to predict individual parameters and social links is incrementally enhanced with the accumulation of additional data. To do this, we use the Friends and Family dataset, which contains rich data signals gathered from the smartphones of 140 adult members of a young-family residential community for over a year, and is one of the most comprehensive mobile phone datasets gathered in academia to date. We develop several models that predict social and individual properties from sensed mobile phone data, including detection of life-partners, ethnicity, and whether a person is a student or not. Then, for this set of diverse learning tasks, we investigate how the prediction accuracy evolves over time, as new data is collected. Finally, based on gained insights, we propose a method for advance prediction of the maximal learning accuracy possible for the learning task at hand, based on an initial set of measurements. This has practical implications, like informing the design of mobile data collection campaigns, or evaluating analysis strategies.
Trends Prediction Using Social Diffusion Models
Venue: arXiv cs.SI 2011
Year: 2011

The importance of the ability of predict trends in social media has been growing rapidly in the past few years with the growing dominance of social media in our everyday's life. Whereas many works focus on the detection of anomalies in networks, there exist little theoretical work on the prediction of the likelihood of anomalous network pattern to globally spread and become "trends". In this work we present an analytic model the social diffusion dynamics of spreading network patterns. Our proposed method is based on information diffusion models, and is capable of predicting future trends based on the analysis of past social interactions between the community's members. We present an analytic lower bound for the probability that emerging trends would successful spread through the network. We demonstrate our model using two comprehensive social datasets - the "Friends and Family" experiment that was held in MIT for over a year, where the complete activity of 140 users was analyzed, and a financial dataset containing the complete activities of over 1.5 million members of the "eToro" social trading community.
Solving the TTC 2011 Compiler Optimization Task with metatools
Venue: arXiv cs.SE 2011
Year: 2011

The authors' "metatools" are a collection of tools for generic programming. This includes generating Java sources from mathematically well-founded specifications, as well as the creation of strictly typed document object models for XML encoded texts. In this context, almost every computer-internal structure is treated as a "model", and every computation is a kind of model transformation. This concept differs significantly from "classical model transformation" executed by specialized tools and languages. Therefore it seemed promising to the organizers of the TTC 2011, as well as to the authors, to apply metatools to one of the challenges, namely to the "compiler optimization task". This is a report on the resulting experiences.
Solving the TTC 2011 Compiler Optimization Case with GROOVE
Venue: arXiv cs.SE 2011
Year: 2011

This report presents a partial solution to the Compiler Optimization case study using GROOVE. We explain how the input graphs provided with the case study were adapted into a GROOVE representation and we describe an initial solution for Task 1. This solution allows us to automatically reproduce the steps of the constant folding example given in the case description. We did not solve Task 2.
Saying Hello World with GROOVE - A Solution to the TTC 2011 Instructive Case
Venue: arXiv cs.SE 2011
Year: 2011

This report presents a solution to the Hello World case study of TTC 2011 using GROOVE. We provide and explain the grammar that we used to solve the case study. Every requested question of the case study was solved by a single rule application.
Flipping the Winner of a Poset Game
Venue: arXiv cs.GT 2011
Year: 2011

Partially-ordered set games, also called poset games, are a class of two-player combinatorial games. The playing field consists of a set of elements, some of which are greater than other elements. Two players take turns removing an element and all elements greater than it, and whoever takes the last element wins. Examples of poset games include Nim and Chomp. We investigate the complexity of computing which player of a poset game has a winning strategy. We give an inductive procedure that modifies poset games to change the nim- value which informally captures the winning strategies in the game. For a generic poset game G, we describe an efficient method for constructing a game not G such that the first player has a winning strategy if and only if the second player has a winning strategy on G. This solves the long-standing problem of whether this construction can be done efficiently. This construction also allows us to reduce the class of Boolean formulas to poset games, establishing a lower bound on the complexity of poset games.
Concurrent Models for Function Execution
Venue: arXiv cs.SE 2011
Year: 2011

We derive an abstract computational model from a sequential computational model that is generally used for function execution. This abstract computational model allows for the concurrent execution of functions. We discuss concurrent models for function execution as implementations from the abstract computational model. We give an example of a particular concurrent function construct that can be implemented on a concurrent machine model using multi-threading. The result is a framework of computational models at different levels of abstraction that can be used in further development of concurrent computational models that deal with the problems inherent with concurrency.
A Novel Approach for Periodic Assessment of Business Process Interoperability
Venue: arXiv cs.OH 2011
Year: 2011

Business collaboration networks provide collaborative organizations a favorable context for automated business process interoperability. This paper aims to present a novel approach for assessing interoperability of process driven services by considering the three main aspects of interoperation: potentiality, compatibility and operational performance. It presents also a software tool that supports the proposed assessment method. In addition to its capacity to track and control the evolution of interoperation degree in time, the proposed tool measures the required effort to reach a planned degree of interoperability. Public accounting of financial authority is given as an illustrative case study of interoperability monitoring in public collaboration network.
Rule based Part of speech Tagger for Homoeopathy Clinical realm
Venue: arXiv cs.CL 2011
Year: 2011

A tagger is a mandatory segment of most text scrutiny systems, as it consigned a s yntax class (e.g., noun, verb, adjective, and adverb) to every word in a sentence. In this paper, we present a simple part of speech tagger for homoeopathy clinical language. This paper reports about the anticipated part of speech tagger for homoeopathy clinical language. It exploit standard pattern for evaluating sentences, untagged clinical corpus of 20085 words is used, from which we had selected 125 sentences (2322 tokens). The problem of tagging in natural language processing is to find a way to tag every word in a text as a meticulous part of speech. The basic idea is to apply a set of rules on clinical sentences and on each word, Accuracy is the leading factor in evaluating any POS tagger so the accuracy of proposed tagger is also conversed.
Digraph Complexity Measures and Applications in Formal Language Theory
Venue: arXiv cs.DM 2011
Year: 2011

We investigate structural complexity measures on digraphs, in particular the cycle rank. This concept is intimately related to a classical topic in formal language theory, namely the star height of regular languages. We explore this connection, and obtain several new algorithmic insights regarding both cycle rank and star height. Among other results, we show that computing the cycle rank is NP-complete, even for sparse digraphs of maximum outdegree 2. Notwithstanding, we provide both a polynomial-time approximation algorithm and an exponential-time exact algorithm for this problem. The former algorithm yields an O((log n)^(3/2))- approximation in polynomial time, whereas the latter yields the optimum solution, and runs in time and space O*(1.9129^n) on digraphs of maximum outdegree at most two. Regarding the star height problem, we identify a subclass of the regular languages for which we can precisely determine the computational complexity of the star height problem. Namely, the star height problem for bideterministic languages is NP-complete, and this holds already for binary alphabets. Then we translate the algorithmic results concerning cycle rank to the bideterministic star height problem, thus giving a polynomial-time approximation as well as a reasonably fast exact exponential algorithm for bideterministic star height.
Randomized Speedup of the Bellman-Ford Algorithm
Venue: arXiv cs.DS 2011
Year: 2011

We describe a variant of the Bellman-Ford algorithm for single-source shortest paths in graphs with negative edges but no negative cycles that randomly permutes the vertices and uses this randomized order to process the vertices within each pass of the algorithm. The modification reduces the worst-case expected number of relaxation steps of the algorithm, compared to the previously-best variant by Yen (1970), by a factor of 2/3 with high probability. We also use our high probability bound to add negative cycle detection to the randomized algorithm.
Understanding the Role of Cooperation in Emergency Plan Construction
Venue: arXiv cs.HC 2011
Year: 2011

In this paper we describe a proposal for information organization for computer supported cooperative work, while working with spatial information. It is focused on emergency response plan construction, and the requirements extracted from that task. At the centre of our proposal is the analysis of the structure of the cooperative workspace. We argue that the internal information representation should follow a spatial approach, tying the structure used to manage users with the structure used to manage information, suggesting the use of different spaces to represent the information. The gain we expect from this approach is the improved capacity to extract information on how people are cooperating and their relationship with the information they are working with. The ideas are introduced while focusing on real life emergency planning activities, where we discuss the current shortcomings of the cooperation strategies in use and propose a solution.
An Improvement of RC4 Cipher Using Vigenere Cipher
Venue: arXiv cs.CR 2011
Year: 2011

This paper develops a new algorithm to improve the security of RC4. Given that RC4 cipher is widely used in the wireless communication and has some weaknesses in the security of RC4 cipher, our idea is based on the combination of the RC4 and the poly alphabetic cipher Vigenère to give a new and more secure algorithm which we called VRC4. In this technique the plain text is encrypted using the classic RC4 cipher then re-encrypt the resulted cipher text using Vigenère cipher to be a more secure cipher text. For simplicity, we have implemented our new algorithm in Java Script taking into consideration two factors: improvement of the security and the time complexity. To show the performance of the new algorithm, we have used the well known network cracking software KisMac.
Social Service Brokerage based on UDDI and Social Requirements
Venue: arXiv cs.SE 2011
Year: 2011

The choice of a suitable service provider is an important issue often overlooked in existing architectures. Current systems focus mostly on the service itself, paying little (if at all) attention to the service provider. In the Service Oriented Architecture (SOA), Universal Description, Discovery and Integration (UDDI) registries have been proposed as a way to publish and find information about available services. These registries have been criticized for not being completely trustworthy. In this paper, an enhancement of existing mechanisms for finding services is proposed. The concept of Social Service Broker addressing both service and social requirements is proposed. While UDDI registries still provide information about available services, methods from Social Network Analysis are proposed as a way to evaluate and rank the services proposed by a UDDI registry in social terms.