OpenRaiser/Intern-Atlas huggingface dataset:
Non-Confluent NLC Graph Grammar Inference by Compressing Disjoint Subgraphs
Venue: arXiv cs.LG 2009
Year: 2009

Grammar inference deals with determining (preferable simple) models/grammars consistent with a set of observations. There is a large body of research on grammar inference within the theory of formal languages. However, there is surprisingly little known on grammar inference for graph grammars. In this paper we take a further step in this direction and work within the framework of node label controlled (NLC) graph grammars. Specifically, we characterize, given a set of disjoint and isomorphic subgraphs of a graph $G$, whether or not there is a NLC graph grammar rule which can generate these subgraphs to obtain $G$. This generalizes previous results by assuming that the set of isomorphic subgraphs is disjoint instead of non-touching. This leads naturally to consider the more involved ``non-confluent'' graph grammar rules.
The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games
Venue: arXiv cs.GT 2009
Year: 2009

We analyse the computational complexity of finding Nash equilibria in simple stochastic multiplayer games. We show that restricting the search space to equilibria whose payoffs fall into a certain interval may lead to undecidability. In particular, we prove that the following problem is undecidable: Given a game G, does there exist a pure-strategy Nash equilibrium of G where player 0 wins with probability 1. Moreover, this problem remains undecidable if it is restricted to strategies with (unbounded) finite memory. However, if mixed strategies are allowed, decidability remains an open problem. One way to obtain a provably decidable variant of the problem is restricting the strategies to be positional or stationary. For the complexity of these two problems, we obtain a common lower bound of NP and upper bounds of NP and PSPACE respectively.
Graph Sparsification in the Semi-streaming Model
Venue: arXiv cs.DS 2009
Year: 2009

Analyzing massive data sets has been one of the key motivations for studying streaming algorithms. In recent years, there has been significant progress in analysing distributions in a streaming setting, but the progress on graph problems has been limited. A main reason for this has been the existence of linear space lower bounds for even simple problems such as determining the connectedness of a graph. However, in many new scenarios that arise from social and other interaction networks, the number of vertices is significantly less than the number of edges. This has led to the formulation of the semi-streaming model where we assume that the space is (near) linear in the number of vertices (but not necessarily the edges), and the edges appear in an arbitrary (and possibly adversarial) order. In this paper we focus on graph sparsification, which is one of the major building blocks in a variety of graph algorithms. There has been a long history of (non-streaming) sampling algorithms that provide sparse graph approximations and it a natural question to ask if the sparsification can be achieved using a small space, and in addition using a single pass over the data? The question is interesting from the standpoint of both theory and practice and we answer the question in the affirmative, by providing a one pass $\tilde{O}(n/ε^{2})$ space algorithm that produces a sparsification that approximates each cut to a $(1+ε)$ factor. We also show that $Ω(n \log \frac1ε)$ space is necessary for a one pass streaming algorithm to approximate the min-cut, improving upon the $Ω(n)$ lower bound that arises from lower bounds for testing connectivity.
Malware Detection using Attribute-Automata to parse Abstract Behavioral Descriptions
Venue: arXiv cs.CR 2009
Year: 2009

Most behavioral detectors of malware remain specific to a given language and platform, mostly PE executables for Windows. The objective of this paper is to define a generic approach for behavioral detection based on two layers respectively responsible for abstraction and detection. The first abstraction layer remains specific to a platform and a language. This first layer interprets the collected instructions, API calls and arguments and classifies these operations as well as the involved objects according to their purpose in the malware lifecycle. The second detection layer remains generic and is totally interoperable between the different abstraction components. This layer relies on parallel automata parsing attribute-grammars where semantic rules are used for object typing (object classification) and object binding (data-flow). To feed detection and to experiment with our approach we have developed two different abstraction components: one processing system call traces from native code and one processing the VBScript interpreted language. The different experimentations have provided promising detection rates, in particular for script files (89%), with almost none false positives. In the case of process traces, the detection rate remains significant (51%) but could be increased by more sophisticated collection tools.
Decoding Network Codes by Message Passing
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we show how to construct a factor graph from a network code. This provides a systematic framework for decoding using message passing algorithms. The proposed message passing decoder exploits knowledge of the underlying communications network topology to simplify decoding. For uniquely decodeable linear network codes on networks with error-free links, only the message supports (rather than the message values themselves) are required to be passed. This proposed simplified support message algorithm is an instance of the sum-product algorithm. Our message-passing framework provides a basis for the design of network codes and control of network topology with a view toward quantifiable complexity reduction in the sink terminals.
On the Applicability of Combinatorial Designs to Key Predistribution for Wireless Sensor Networks
Venue: arXiv cs.CR 2009
Year: 2009

The constraints of lightweight distributed computing environments such as wireless sensor networks lend themselves to the use of symmetric cryptography to provide security services. The lack of central infrastructure after deployment of such networks requires the necessary symmetric keys to be predistributed to participating nodes. The rich mathematical structure of combinatorial designs has resulted in the proposal of several key predistribution schemes for wireless sensor networks based on designs. We review and examine the appropriateness of combinatorial designs as a tool for building key predistribution schemes suitable for such environments.
Formalization of malware through process calculi
Venue: arXiv cs.CR 2009
Year: 2009

Since the seminal work from F. Cohen in the eighties, abstract virology has seen the apparition of successive viral models, all based on Turing-equivalent formalisms. But considering recent malware such as rootkits or k-ary codes, these viral models only partially cover these evolved threats. The problem is that Turing-equivalent models do not support interactive computations. New models have thus appeared, offering support for these evolved malware, but loosing the unified approach in the way. This article provides a basis for a unified malware model founded on process algebras and in particular the Join-Calculus. In terms of expressiveness, the new model supports the fundamental definitions based on self-replication and adds support for interactions, concurrency and non-termination allows the definition of more complex behaviors. Evolved malware such as rootkits can now be thoroughly modeled. In terms of detection and prevention, the fundamental results of undecidability and isolation still hold. However the process-based model has permitted to establish new results: identification of fragments from the Join-Calculus where malware detection becomes decidable, formal definition of the non-infection property, approximate solutions to restrict malware propagation.
Analysis of bandwidth measurement methodologies over WLAN systems
Venue: arXiv cs.NI 2009
Year: 2009

WLAN devices have become a fundamental component of nowadays network deployments. However, even though traditional networking applications run mostly unchanged over wireless links, the actual interaction between these applications and the dynamics of wireless transmissions is not yet fully understood. An important example of such applications are bandwidth estimation tools. This area has become a mature research topic with well-developed results. Unfortunately recent studies have shown that the application of these results to WLAN links is not straightforward. The main reasons for this is that the assumptions taken to develop bandwidth measurements tools do not hold any longer in the presence of wireless links (e.g. non-FIFO scheduling). This paper builds from these observations and its main goal is to analyze the interaction between probe packets and WLAN transmissions in bandwidth estimation processes. The paper proposes an analytical model that better accounts for the particularities of WLAN links. The model is validated through extensive experimentation and simulation and reveals that (1) the distribution of the delay to transmit probing packets is not the same for the whole probing sequence, this biases the measurements process and (2) existing tools and techniques point at the achievable throughput rather than the available bandwidth or the capacity, as previously assumed.
Degrees of Guaranteed Envy-Freeness in Finite Bounded Cake-Cutting Protocols
Venue: arXiv cs.GT 2009
Year: 2009

Cake-cutting protocols aim at dividing a ``cake'' (i.e., a divisible resource) and assigning the resulting portions to several players in a way that each of the players feels to have received a ``fair'' amount of the cake. An important notion of fairness is envy-freeness: No player wishes to switch the portion of the cake received with another player's portion. Despite intense efforts in the past, it is still an open question whether there is a \emph{finite bounded} envy-free cake-cutting protocol for an arbitrary number of players, and even for four players. We introduce the notion of degree of guaranteed envy-freeness (DGEF) as a measure of how good a cake-cutting protocol can approximate the ideal of envy-freeness while keeping the protocol finite bounded (trading being disregarded). We propose a new finite bounded proportional protocol for any number n \geq 3 of players, and show that this protocol has a DGEF of 1 + \lceil (n^2)/2 \rceil. This is the currently best DGEF among known finite bounded cake-cutting protocols for an arbitrary number of players. We will make the case that improving the DGEF even further is a tough challenge, and determine, for comparison, the DGEF of selected known finite bounded cake-cutting protocols.
Efficient implementation of linear programming decoding
Venue: arXiv cs.IT 2009
Year: 2009

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem, and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. We first prove, by modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, that LP decoding can be performed by solving a number of LP problems that contain at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate iterative solution of such systems. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.
Application of the Weil representation: diagonalization of the discrete Fourier transform
Venue: arXiv cs.IT 2009
Year: 2009

We survey a new application of the Weil representation to construct a canonical basis of eigenvectors for the discrete Fourier transform (DFT). The transition matrix from the standard basis to the canonical basis defines a novel transform which we call the discrete oscillator transform (DOT for short). In addition, we describe a fast algorithm for computing the DOT in certain cases.
Embedding Data within Knowledge Spaces
Venue: arXiv cs.AI 2009
Year: 2009

The promise of e-Science will only be realized when data is discoverable, accessible, and comprehensible within distributed teams, across disciplines, and over the long-term--without reliance on out-of-band (non-digital) means. We have developed the open-source Tupelo semantic content management framework and are employing it to manage a wide range of e-Science entities (including data, documents, workflows, people, and projects) and a broad range of metadata (including provenance, social networks, geospatial relationships, temporal relations, and domain descriptions). Tupelo couples the use of global identifiers and resource description framework (RDF) statements with an aggregatable content repository model to provide a unified space for securely managing distributed heterogeneous content and relationships.
Alleviating Media Bias Through Intelligent Agent Blogging
Venue: arXiv cs.AI 2009
Year: 2009

Consumers of mass media must have a comprehensive, balanced and plural selection of news to get an unbiased perspective; but achieving this goal can be very challenging, laborious and time consuming. News stories development over time, its (in)consistency, and different level of coverage across the media outlets are challenges that a conscientious reader has to overcome in order to alleviate bias. In this paper we present an intelligent agent framework currently facilitating analysis of the main sources of on-line news in El Salvador. We show how prior tools of text analysis and Web 2.0 technologies can be combined with minimal manual intervention to help individuals on their rational decision process, while holding media outlets accountable for their work.
Comparative concept similarity over Minspaces: Axiomatisation and Tableaux Calculus
Venue: arXiv cs.AI 2009
Year: 2009

We study the logic of comparative concept similarity $\CSL$ introduced by Sheremet, Tishkovsky, Wolter and Zakharyaschev to capture a form of qualitative similarity comparison. In this logic we can formulate assertions of the form " objects A are more similar to B than to C". The semantics of this logic is defined by structures equipped by distance functions evaluating the similarity degree of objects. We consider here the particular case of the semantics induced by \emph{minspaces}, the latter being distance spaces where the minimum of a set of distances always exists. It turns out that the semantics over arbitrary minspaces can be equivalently specified in terms of preferential structures, typical of conditional logics. We first give a direct axiomatisation of this logic over Minspaces. We next define a decision procedure in the form of a tableaux calculus. Both the calculus and the axiomatisation take advantage of the reformulation of the semantics in terms of preferential structures.
On Designing Lyapunov-Krasovskii Based AQM for Routers Supporting TCP Flows
Venue: arXiv cs.NI 2009
Year: 2009

For the last few years, we assist to a growing interest of designing AQM (Active Queue Management) using control theory. In this paper, we focus on the synthesis of an AQM based on the Lyapunov theory for time delay systems. With the help of a recently developed Lyapunov-Krasovskii functional and using a state space representation of a linearized fluid model of TCP, two robust AQMs stabilizing the TCP model are constructed. Notice that our results are constructive and the synthesis problem is reduced to a convex optimization scheme expressed in terms of linear matrix inequalities (LMIs). Finally, an example extracted from the literature and simulations via {\it NS simulator} support our study.
Towards a Statistical Methodology to Evaluate Program Speedups and their Optimisation Techniques
Venue: arXiv cs.PF 2009
Year: 2009

The community of program optimisation and analysis, code performance evaluation, parallelisation and optimising compilation has published since many decades hundreds of research and engineering articles in major conferences and journals. These articles study efficient algorithms, strategies and techniques to accelerate programs execution times, or optimise other performance metrics (MIPS, code size, energy/power, MFLOPS, etc.). Many speedups are published, but nobody is able to reproduce them exactly. The non-reproducibility of our research results is a dark point of the art, and we cannot be qualified as {\it computer scientists} if we do not provide rigorous experimental methodology. This article provides a first effort towards a correct statistical protocol for analysing and measuring speedups. As we will see, some common mistakes are done by the community inside published articles, explaining part of the non-reproducibility of the results. Our current article is not sufficient by its own to deliver a complete experimental methodology, further efforts must be done by the community to decide about a common protocol for our future experiences. Anyway, our community should take care about the aspect of reproducibility of the results in the future.
On the Average Complexity of Moore's State Minimization Algorithm
Venue: arXiv cs.DS 2009
Year: 2009

We prove that, for any arbitrary finite alphabet and for the uniform distribution over deterministic and accessible automata with n states, the average complexity of Moore's state minimization algorithm is in O(n log n). Moreover this bound is tight in the case of unary utomata.
Node Weighted Scheduling
Venue: arXiv cs.NI 2009
Year: 2009

This paper proposes a new class of online policies for scheduling in input-buffered crossbar switches. Our policies are throughput optimal for a large class of arrival processes which satisfy strong-law of large numbers. Given an initial configuration and no further arrivals, our policies drain all packets in the system in the minimal amount of time (providing an online alternative to the batch approach based on Birkhoff-VonNeumann decompositions). We show that it is possible for policies in our class to be throughput optimal even if they are not constrained to be maximal in every time slot. Most algorithms for switch scheduling take an edge based approach; in contrast, we focus on scheduling (a large enough set of) the most congested ports. This alternate approach allows for lower-complexity algorithms, and also requires a non-standard technique to prove throughput-optimality. One algorithm in our class, Maximum Vertex-weighted Matching (MVM) has worst-case complexity similar to Max-size Matching, and in simulations shows slightly better delay performance than Max-(edge)weighted-Matching (MWM).
Opportunistic Communications in Fading Multiaccess Relay Channels
Venue: arXiv cs.IT 2009
Year: 2009

The problem of optimal resource allocation is studied for ergodic fading orthogonal multiaccess relay channels (MARCs) in which the users (sources) communicate with a destination with the aid of a half-duplex relay that transmits on a channel orthogonal to that used by the transmitting sources. Under the assumption that the instantaneous fading state information is available at all nodes, the maximum sum-rate and the optimal user and relay power allocations (policies) are developed for a decode-and-forward (DF) relay. With the observation that a DF relay results in two multiaccess channels, one at the relay and the other at the destination, a single known lemma on the sum-rate of two intersecting polymatroids is used to determine the DF sum-rate and the optimal user and relay policies. The lemma also enables a broad topological classification of fading MARCs into one of three types. The first type is the set of partially clustered MARCs where a user is clustered either with the relay or with the destination such that the users waterfill on their bottle-neck links to the distant receiver. The second type is the set of clustered MARCs where all users are either proximal to the relay or to the destination such that opportunistic multiuser scheduling to one of the receivers is optimal. The third type consists of arbitrarily clustered MARCs which are a combination of the first two types, and for this type it is shown that the optimal policies are opportunistic non-waterfilling solutions. The analysis is extended to develop the rate region of a K-user orthogonal half-duplex MARC. Finally, cutset outer bounds are used to show that DF achieves the capacity region for a class of clustered orthogonal half-duplex MARCs.
Compilation of extended recursion in call-by-value functional languages
Venue: arXiv cs.PL 2009
Year: 2009

This paper formalizes and proves correct a compilation scheme for mutually-recursive definitions in call-by-value functional languages. This scheme supports a wider range of recursive definitions than previous methods. We formalize our technique as a translation scheme to a lambda-calculus featuring in-place update of memory blocks, and prove the translation to be correct.
The Price of Anarchy in Cooperative Network Creation Games
Venue: arXiv cs.GT 2009
Year: 2009

In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost α. Together the agents create a network (a subgraph of the host graph) while selfishly minimizing the link creation costs plus the sum of the distances to all other players (usage cost). In this paper, we pursue two important facets of the network creation game. First, we study extensively a natural version of the game, called the cooperative model, where nodes can collaborate and share the cost of creating any edge in the host graph. We prove the first nontrivial bounds in this model, establishing that the price of anarchy is polylogarithmic in n for all values of α in complete host graphs. This bound is the first result of this type for any version of the network creation game; most previous general upper bounds are polynomial in n. Interestingly, we also show that equilibrium graphs have polylogarithmic diameter for the most natural range of α(at most n polylg n). Second, we study the impact of the natural assumption that the host graph is a general graph, not necessarily complete. This model is a simple example of nonuniform creation costs among the edges (effectively allowing weights of αand \infty). We prove the first assemblage of upper and lower bounds for this context, stablishing nontrivial tight bounds for many ranges of α, for both the unilateral and cooperative versions of network creation. In particular, we establish polynomial lower bounds for both versions and many ranges of α, even for this simple nonuniform cost model, which sharply contrasts the conjectured constant bounds for these games in complete (uniform) graphs.