OpenRaiser/Intern-Atlas huggingface dataset:
Breaking Symmetries
Venue: arXiv cs.LO 2010
Year: 2010

A well-known result by Palamidessi tells us that \pimix (the π-calculus with mixed choice) is more expressive than \pisep (its subset with only separate choice). The proof of this result argues with their different expressive power concerning leader election in symmetric networks. Later on, Gorla offered an arguably simpler proof that, instead of leader election in symmetric networks, employed the reducibility of incestual processes (mixed choices that include both enabled senders and receivers for the same channel) when running two copies in parallel. In both proofs, the role of breaking (initial) symmetries is more or less apparent. In this paper, we shed more light on this role by re-proving the above result - based on a proper formalization of what it means to break symmetries without referring to another layer of the distinguishing problem domain of leader election. Both Palamidessi and Gorla rephrased their results by stating that there is no uniform and reasonable encoding from \pimix into \pisep. We indicate how the respective proofs can be adapted and exhibit the consequences of varying notions of uniformity and reasonableness. In each case, the ability to break initial symmetries turns out to be essential.
A Calculus of Consistent Component-based Software Updates
Venue: arXiv cs.LO 2010
Year: 2010

It is important to enable reasoning about the meaning and possible effects of updates to ensure that the updated system operates correctly. A formal, mathematical model of dynamic update should be developed, in order to understand by both users and implementors of update technology what design choices can be considered. In this paper, we define a formal calculus $updateπ$, a variant extension of higher-order $π$ calculus, to model dynamic updates of component-based software, which is language and technology independent. The calculus focuses on following main concepts: proper granularity of update, timing of dynamic update, state transformation between versions, update failure check and recovery. We describe a series of rule on safe component updates to model some general processes of dynamic update and discuss its reduction semantics coincides with a labelled transition system semantics that illustrate the expressive power of these calculi.
Multi-Hop Bandwidth Management Protocol for Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

An admission control scheme should play the role of a coordinator for flows in a data communication network, to provide the guarantees as the medium is shared. The nodes of a wired network can monitor the medium to know the available bandwidth at any point of time. But, in wireless ad hoc networks, a node must consume the bandwidth of neighboring nodes, during a communication. Hence, the consumption of bandwidth by a flow and the availability of resources to any wireless node strictly depend upon the neighboring nodes within its transmission range. We present a scalable and efficient admission control scheme, Multi-hop Bandwidth Management Protocol (MBMP), to support the QoS requirements in multi-hop ad hoc networks. We simulate several options to design MBMP and compare the performances of these options through mathematical analysis and simulation results, and compare its effectiveness with the existing admission control schemes through extensive simulations.
Functional Categories of Support to Operations in Military Information Systems
Venue: arXiv cs.OH 2010
Year: 2010

In order to group the functional requirements for support to operations by modern information systems systematically, the NATO Code of best Practise (COBP) for C2 Assessment defines three domain areas: Battlespace Visualization, Decision Making, and Battle Management Functions. In addition, within an domain overlapping information grid of the information system, necessary functions for assessing and disseminating the information are capsulated. For all three domains, including the overlapping information grid, the respective requirements for functional support have to be met be future command, control, communications, and intelligence (C3I) systems. The paper describes the functional categories of the three domains having been defined for article 5 operations, extends them to meet the requirements for operations other than war (OOTW), and gives some examples how modules of simulation systems can deliver respective support functions. In addition, references defining migration procedures for legacy systems to enable a smooth change from the old to the new C3I paradigm are given.
Pumping lemmas for linear and nonlinear context-free languages
Venue: arXiv cs.FL 2010
Year: 2010

Pumping lemmas are created to prove that given languages are not belong to certain language classes. There are several known pumping lemmas for the whole class and some special classes of the context-free languages. In this paper we prove new, interesting pumping lemmas for special linear and context-free language classes. Some of them can be used to pump regular languages in two place simultaneously. Other lemma can be used to pump context-free languages in arbitrary many places.
Score lists in multipartite hypertournaments
Venue: arXiv cs.DM 2010
Year: 2010

Given non-negative integers $n_{i}$ and $α_{i}$ with $0 \leq α_{i} \leq n_i$ $(i=1,2,...,k)$, an $[α_{1},α_{2},...,α_{k}]$-$k$-partite hypertournament on $\sum_{1}^{k}n_{i}$ vertices is a $(k+1)$-tuple $(U_{1},U_{2},...,U_{k},E)$, where $U_{i}$ are $k$ vertex sets with $|U_{i}|=n_{i}$, and $E$ is a set of $\sum_{1}^{k}α_{i}$-tuples of vertices, called arcs, with exactly $α_{i}$ vertices from $U_{i}$, such that any $\sum_{1}^{k}α_{i}$ subset $\cup_{1}^{k}U_{i}^{\prime}$ of $\cup_{1}^{k}U_{i}$, $E$ contains exactly one of the $(\sum_{1}^{k} α_{i})!$ $\sum_{1}^{k}α_{i}$-tuples whose entries belong to $\cup_{1}^{k}U_{i}^{\prime}$. We obtain necessary and sufficient conditions for $k$ lists of non-negative integers in non-decreasing order to be the losing score lists and to be the score lists of some $k$-partite hypertournament.
Modelling dynamic programming problems by generalized d-graphs
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we introduce the concept of generalized d-graph (admitting cycles) as special dependency-graphs for modelling dynamic programming (DP) problems. We describe the d-graph versions of three famous single-source shortest algorithms (The algorithm based on the topological order of the vertices, Dijkstra algorithm and Bellman-Ford algorithm), which can be viewed as general DP strategies in the case of three different class of optimization problems. The new modelling method also makes possible to classify DP problems and the corresponding DP strategies in term of graph theory.
An Effective Method of Image Retrieval using Image Mining Techniques
Venue: arXiv cs.CV 2010
Year: 2010

The present research scholars are having keen interest in doing their research activities in the area of Data mining all over the world. Especially, [13]Mining Image data is the one of the essential features in this present scenario since image data plays vital role in every aspect of the system such as business for marketing, hospital for surgery, engineering for construction, Web for publication and so on. The other area in the Image mining system is the Content-Based Image Retrieval (CBIR) which performs retrieval based on the similarity defined in terms of extracted features with more objectiveness. The drawback in CBIR is the features of the query image alone are considered. Hence, a new technique called Image retrieval based on optimum clusters is proposed for improving user interaction with image retrieval systems by fully exploiting the similarity information. The index is created by describing the images according to their color characteristics, with compact feature vectors, that represent typical color distributions [12].
Middle and Ripple, fast simple O(lg n) algorithms for Lucas Numbers
Venue: arXiv cs.DM 2010
Year: 2010

A fast simple O(\log n) iteration algorithm for individual Lucas numbers is given. This is faster than using Fibonacci based methods because of the structure of Lucas numbers. Using a sqrt 5 conversion factor on Lucus numbers gives a faster Fibonacci algorithm. In addition, a fast simple recursive algorithm for individual Lucas numbers is given that is O(log n).
Quality of Source Location Protection in Globally Attacked Sensor Networks
Venue: arXiv cs.CR 2010
Year: 2010

We propose an efficient scheme for generating fake network traffic to disguise the real event notification in the presence of a global eavesdropper, which is especially relevant for the quality of service in delay-intolerant applications monitoring rare and spatially sparse events, and deployed as large wireless sensor networks with single data collector. The efficiency of the scheme that provides statistical source anonymity is achieved by partitioning network nodes randomly into several node groups. Members of the same group collectively emulate both temporal and spatial distribution of the event. Under such dummy-traffic framework of the source anonymity protection, we aim to better model the global eavesdropper, especially her way of using statistical tests to detect the real event, and to present the quality of the location protection as relative to the adversary's strength. In addition, our approach aims to reduce the per-event work spent to generate the fake traffic while, most importantly, providing a guaranteed latency in reporting the event. The latency is controlled by decoupling the routing from the fake traffic schedule. We believe that the proposed source anonymity protection strategy, and the quality evaluation framework, are well justified by the abundance of the applications that monitor a rare event with known temporal statistics, and uniform spatial distribution.
Design of QoS-aware Provisioning Systems
Venue: arXiv cs.NI 2010
Year: 2010

We present an architecture of a hosting system consisting of a set of hosted Web Services subject to QoS constraints, and a certain number of servers used to run users demand. The traffic is session-based, while provider and users agree on SLAs specifying the expected level of service performance such that the service provider is liable to compensate his/her customers if the level of performance is not satisfactory. The system is driven by a utility function which tries to optimize the average earned revenue per unit time. The middleware collects demand and performance statistics, and estimates traffic parameters in order to make dynamic decisions concerning server allocation and admission control. We empirically evaluate the effects of admission policies, resource allocation and service differentiation schemes on the achieved revenues, and we find that our system is robust enough to successfully deal with session-based traffic under different conditions.
Infinite computable version of Lovasz Local Lemma
Venue: arXiv cs.DS 2010
Year: 2010

Lovász Local Lemma (LLL) is a probabilistic tool that allows us to prove the existence of combinatorial objects in the cases when standard probabilistic argument does not work (there are many partly independent conditions). LLL can be also used to prove the consistency of an infinite set of conditions, using standard compactness argument (if an infinite set of conditions is inconsistent, then some finite part of it is inconsistent, too, which contradicts LLL). In this way we show that objects satisfying all the conditions do exist (though the probability of this event equals~$0$). However, if we are interested in finding a computable solution that satisfies all the constraints, compactness arguments do not work anymore. Moser and Tardos recently gave a nice constructive proof of LLL. Lance Fortnow asked whether one can apply Moser--Tardos technique to prove the existence of a computable solution. We show that this is indeed possible (under almost the same conditions as used in the non-constructive version).
Towards a Low-Complexity Dynamic Decode-and-Forward Relay Protocol
Venue: arXiv cs.IT 2010
Year: 2010

The dynamic decode-and-forward (DDF) relaying protocol is a relatively new cooperative scheme which has been shown to achieve promising theoretical results in terms of diversity-multiplexing gain tradeoff and error rates. The case of a single relay has been extensively studied in the literature and several techniques to approach the optimum performance have been proposed. Until recently, however, a practical implementation for the case of several relays had been considered to be much more challenging. A rotation-based DDF technique, suitable for any number of relays, has been recently proposed which promises to overcome important implementation hurdles. This article provides an overview of the DDF protocol, describes different implementation techniques and compares their performance.
Novel Mechanism to Defend DDoS Attacks Caused by Spam
Venue: arXiv cs.CR 2010
Year: 2010

Corporate mail services are designed to perform better than public mail services. Fast mail delivery, large size file transfer as an attachments, high level spam and virus protection, commercial advertisement free environment are some of the advantages worth to mention. But these mail services are frequent target of hackers and spammers. Distributed Denial of service attacks are becoming more common and sophisticated. The researchers have proposed various solutions to the DDOS attacks. Can we stop these kinds of attacks with available technology? These days the DDoS attack through spam has increased and disturbed the mail services of various organizations. Spam penetrates through all the filters to establish DDoS attacks, which causes serious problems to users and the data. In this paper we propose a novel approach to defend DDoS attack caused by spam mails. This approach is a combination of fine tuning of source filters, content filters, strictly implementing mail policies,educating user, network monitoring and logical solutions to the ongoing attack. We have conducted several experiments in corporate mail services; the results show that this approach is highly effective to prevent DDoS attack caused by spam. The novel defense mechanism reduced 60% of the incoming spam traffic and repelled many DDoS attacks caused by spam.
An Effective Clustering Approach to Web Query Log Anonymization
Venue: arXiv cs.DB 2010
Year: 2010

Web query log data contain information useful to research; however, release of such data can re-identify the search engine users issuing the queries. These privacy concerns go far beyond removing explicitly identifying information such as name and address, since non-identifying personal data can be combined with publicly available information to pinpoint to an individual. In this work we model web query logs as unstructured transaction data and present a novel transaction anonymization technique based on clustering and generalization techniques to achieve the k-anonymity privacy. We conduct extensive experiments on the AOL query log data. Our results show that this method results in a higher data utility compared to the state of-the-art transaction anonymization methods.
Automated Query Learning with Wikipedia and Genetic Programming
Venue: arXiv cs.AI 2010
Year: 2010

Most of the existing information retrieval systems are based on bag of words model and are not equipped with common world knowledge. Work has been done towards improving the efficiency of such systems by using intelligent algorithms to generate search queries, however, not much research has been done in the direction of incorporating human-and-society level knowledge in the queries. This paper is one of the first attempts where such information is incorporated into the search queries using Wikipedia semantics. The paper presents an essential shift from conventional token based queries to concept based queries, leading to an enhanced efficiency of information retrieval systems. To efficiently handle the automated query learning problem, we propose Wikipedia-based Evolutionary Semantics (Wiki-ES) framework where concept based queries are learnt using a co-evolving evolutionary procedure. Learning concept based queries using an intelligent evolutionary procedure yields significant improvement in performance which is shown through an extensive study using Reuters newswire documents. Comparison of the proposed framework is performed with other information retrieval systems. Concept based approach has also been implemented on other information retrieval systems to justify the effectiveness of a transition from token based queries to concept based queries.
Binary Inference for Primary User Separation in Cognitive Radio Networks
Venue: arXiv cs.NI 2010
Year: 2010

Spectrum sensing receives much attention recently in the cognitive radio (CR) network research, i.e., secondary users (SUs) constantly monitor channel condition to detect the presence of the primary users (PUs). In this paper, we go beyond spectrum sensing and introduce the PU separation problem, which concerns with the issues of distinguishing and characterizing PUs in the context of collaborative spectrum sensing and monitor selection. The observations of monitors are modeled as boolean OR mixtures of underlying binary sources for PUs. We first justify the use of the binary OR mixture model as opposed to the traditional linear mixture model through simulation studies. Then we devise a novel binary inference algorithm for PU separation. Not only PU-SU relationship are revealed, but PUs' transmission statistics and activities at each time slot can also be inferred. Simulation results show that without any prior knowledge regarding PUs' activities, the algorithm achieves high inference accuracy even in the presence of noisy measurements.
A Distributed Cluster Scheme For Bandwidth Management In Multi-hop MANETs
Venue: arXiv cs.NI 2010
Year: 2010

Electronic collaboration among devices in a geographically localized environment is made possible with the implementation of IEEE 802.11 based wireless ad hoc networks. Dynamic nature of mobile ad hoc networks(MANETs) may lead to unpredictable intervention of attacks or fault occurrence, which consequently may partition the network, degrade its performance, violate the QoS requirements and most importantly, affect bandwidth allocation to mobile nodes in the network. In this paper, we propose a new distributed cluster scheme for MANETs, especially in harsh environments, based on the concept of survivability to support QoS requirements and to protect bandwidth efficiently. With the incorporation of clustering algorithms in survivability technology, we employ a simple network configuration and expect to reduce occurrences of faults in MANETs. At the same time, we address the scalability problem, which represents a great challenge to network configuration. We do expect a simplification of accessing bandwidth allocation with required QoS support for different applications.
Capacitated Vehicle Routing with Non-Uniform Speeds
Venue: arXiv cs.DS 2010
Year: 2010

The capacitated vehicle routing problem (CVRP) involves distributing (identical) items from a depot to a set of demand locations, using a single capacitated vehicle. We study a generalization of this problem to the setting of multiple vehicles having non-uniform speeds (that we call Heterogenous CVRP), and present a constant-factor approximation algorithm. The technical heart of our result lies in achieving a constant approximation to the following TSP variant (called Heterogenous TSP). Given a metric denoting distances between vertices, a depot r containing k vehicles with possibly different speeds, the goal is to find a tour for each vehicle (starting and ending at r), so that every vertex is covered in some tour and the maximum completion time is minimized. This problem is precisely Heterogenous CVRP when vehicles are uncapacitated. The presence of non-uniform speeds introduces difficulties for employing standard tour-splitting techniques. In order to get a better understanding of this technique in our context, we appeal to ideas from the 2-approximation for scheduling in parallel machine of Lenstra et al.. This motivates the introduction of a new approximate MST construction called Level-Prim, which is related to Light Approximate Shortest-path Trees. The last component of our algorithm involves partitioning the Level-Prim tree and matching the resulting parts to vehicles. This decomposition is more subtle than usual since now we need to enforce correlation between the size of the parts and their distances to the depot.
Coding for High-Density Recording on a 1-D Granular Magnetic Medium
Venue: arXiv cs.IT 2010
Year: 2010

In terabit-density magnetic recording, several bits of data can be replaced by the values of their neighbors in the storage medium. As a result, errors in the medium are dependent on each other and also on the data written. We consider a simple one-dimensional combinatorial model of this medium. In our model, we assume a setting where binary data is sequentially written on the medium and a bit can erroneously change to the immediately preceding value. We derive several properties of codes that correct this type of errors, focusing on bounds on their cardinality. We also define a probabilistic finite-state channel model of the storage medium, and derive lower and upper estimates of its capacity. A lower bound is derived by evaluating the symmetric capacity of the channel, i.e., the maximum transmission rate under the assumption of the uniform input distribution of the channel. An upper bound is found by showing that the original channel is a stochastic degradation of another, related channel model whose capacity we can compute explicitly.
Querying Biomedical Ontologies in Natural Language using Answer Set
Venue: arXiv cs.AI 2010
Year: 2010

In this work, we develop an intelligent user interface that allows users to enter biomedical queries in a natural language, and that presents the answers (possibly with explanations if requested) in a natural language. We develop a rule layer over biomedical ontologies and databases, and use automated reasoners to answer queries considering relevant parts of the rule layer.
MUDOS-NG: Multi-document Summaries Using N-gram Graphs (Tech Report)
Venue: arXiv cs.CL 2010
Year: 2010

This report describes the MUDOS-NG summarization system, which applies a set of language-independent and generic methods for generating extractive summaries. The proposed methods are mostly combinations of simple operators on a generic character n-gram graph representation of texts. This work defines the set of used operators upon n-gram graphs and proposes using these operators within the multi-document summarization process in such subtasks as document analysis, salient sentence selection, query expansion and redundancy control. Furthermore, a novel chunking methodology is used, together with a novel way to assign concepts to sentences for query expansion. The experimental results of the summarization system, performed upon widely used corpora from the Document Understanding and the Text Analysis Conferences, are promising and provide evidence for the potential of the generic methods introduced. This work aims to designate core methods exploiting the n-gram graph representation, providing the basis for more advanced summarization systems.