OpenRaiser/Intern-Atlas huggingface dataset:
Algebraic Foundations for Information Theoretical, Probabilistic and Guessability measures of Information Flow
Venue: arXiv cs.IT 2011
Year: 2011

Several mathematical ideas have been investigated for Quantitative Information Flow. Information theory, probability, guessability are the main ideas in most proposals. They aim to quantify how much information is leaked, how likely is to guess the secret and how long does it take to guess the secret respectively. In this paper, we show how the Lattice of Information provides a valuable foundation for all these approaches; not only it provides an elegant algebraic framework for the ideas, but also to investigate their relationship. In particular we will use this lattice to prove some results establishing order relation correspondences between the different quantitative approaches. The implications of these results w.r.t. recent work in the community is also investigated. While this work concentrates on the foundational importance of the Lattice of Information its practical relevance has been recently proven, notably with the quantitative analysis of Linux kernel vulnerabilities. Overall we believe these works set the case for establishing the Lattice of Information as one of the main reference structure for Quantitative Information Flow.
Diversification improves interpolation
Venue: arXiv cs.SC 2011
Year: 2011

We consider the problem of interpolating an unknown multivariate polynomial with coefficients taken from a finite field or as numerical approximations of complex numbers. Building on the recent work of Garg and Schost, we improve on the best-known algorithm for interpolation over large finite fields by presenting a Las Vegas randomized algorithm that uses fewer black box evaluations. Using related techniques, we also address numerical interpolation of sparse polynomials with complex coefficients, and provide the first provably stable algorithm (in the sense of relative error) for this problem, at the cost of modestly more evaluations. A key new technique is a randomization which makes all coefficients of the unknown polynomial distinguishable, producing what we call a diverse polynomial. Another departure from most previous approaches is that our algorithms do not rely on root finding as a subroutine. We show how these improvements affect the practical performance with trial implementations.
Integrated monitoring of multi-domain backbone connections -- Operational experience in the LHC optical private network
Venue: arXiv cs.NI 2011
Year: 2011

Novel large scale research projects often require cooperation between various different project partners that are spread among the entire world. They do not only need huge computing resources, but also a reliable network to operate on. The Large Hadron Collider (LHC) at CERN is a representative example for such a project. Its experiments result in a vast amount of data, which is interesting for researchers around the world. For transporting the data from CERN to 11 data processing and storage sites, an optical private network (OPN) has been constructed. As the experiment data is highly valuable, LHC defines very high requirements to the underlying network infrastructure. In order to fulfil those requirements, the connections have to be managed and monitored permanently. In this paper, we present the integrated monitoring solution developed for the LHCOPN. We first outline the requirements and show how they are met on the single network layers. After that, we describe, how those single measurements can be combined into an integrated view. We cover design concepts as well as tool implementation highlights.
Speedup in the Traveling Repairman Problem with Constrained Time Windows
Venue: arXiv cs.DS 2011
Year: 2011

A bicriteria approximation algorithm is presented for the unrooted traveling repairman problem, realizing increased profit in return for increased speedup of repairman motion. The algorithm generalizes previous results from the case in which all time windows are the same length to the case in which their lengths can range between l and 2. This analysis can extend to any range of time window lengths, following our earlier techniques. This relationship between repairman profit and speedup is applicable over a range of values that is dependent on the cost of putting the input in an especially desirable form, involving what are called "trimmed windows." For time windows with lengths between 1 and 2, the range of values for speedup $s$ for which our analysis holds is $1 \leq s \leq 6$. In this range, we establish an approximation ratio that is constant for any specific value of $s$.
Dyna-H: a heuristic planning reinforcement learning algorithm applied to role-playing-game strategy decision systems
Venue: arXiv cs.AI 2011
Year: 2011

In a Role-Playing Game, finding optimal trajectories is one of the most important tasks. In fact, the strategy decision system becomes a key component of a game engine. Determining the way in which decisions are taken (online, batch or simulated) and the consumed resources in decision making (e.g. execution time, memory) will influence, in mayor degree, the game performance. When classical search algorithms such as A* can be used, they are the very first option. Nevertheless, such methods rely on precise and complete models of the search space, and there are many interesting scenarios where their application is not possible. Then, model free methods for sequential decision making under uncertainty are the best choice. In this paper, we propose a heuristic planning strategy to incorporate the ability of heuristic-search in path-finding into a Dyna agent. The proposed Dyna-H algorithm, as A* does, selects branches more likely to produce outcomes than other branches. Besides, it has the advantages of being a model-free online reinforcement learning algorithm. The proposal was evaluated against the one-step Q-Learning and Dyna-Q algorithms obtaining excellent experimental results: Dyna-H significantly overcomes both methods in all experiments. We suggest also, a functional analogy between the proposed sampling from worst trajectories heuristic and the role of dreams (e.g. nightmares) in human behavior.
Self-Index Based on LZ77
Venue: arXiv cs.DS 2011
Year: 2011

We introduce the first self-index based on the Lempel-Ziv 1977 compression format (LZ77). It is particularly competitive for highly repetitive text collections such as sequence databases of genomes of related species, software repositories, versioned document collections, and temporal text databases. Such collections are extremely compressible but classical self-indexes fail to capture that source of compressibility. Our self-index takes in practice a few times the space of the text compressed with LZ77 (as little as 2.6 times), extracts 1--2 million characters of the text per second, and finds patterns at a rate of 10--50 microseconds per occurrence. It is smaller (up to one half) than the best current self-index for repetitive collections, and faster in many cases.
Parameter Optimization of Multi-Agent Formations based on LQR Design
Venue: arXiv cs.SY 2011
Year: 2011

In this paper we study the optimal formation control of multiple agents whose interaction parameters are adjusted upon a cost function consisting of both the control energy and the geometrical performance. By optimizing the interaction parameters and by the linear quadratic regulation(LQR) controllers, the upper bound of the cost function is minimized. For systems with homogeneous agents interconnected over sparse graphs, distributed controllers are proposed that inherit the same underlying graph as the one among agents. For the more general case, a relaxed optimization problem is considered so as to eliminate the nonlinear constraints. Using the subgradient method, interaction parameters among agents are optimized under the constraint of a sparse graph, and the optimum of the cost function is a better result than the one when agents interacted only through the control channel. Numerical examples are provided to validate the effectiveness of the method and to illustrate the geometrical performance of the system.
Extensional Collapse Situations I: non-termination and unrecoverable errors
Venue: arXiv cs.LO 2011
Year: 2011

We consider a simple model of higher order, functional computation over the booleans. Then, we enrich the model in order to encompass non-termination and unrecoverable errors, taken separately or jointly. We show that the models so defined form a lattice when ordered by the extensional collapse situation relation, introduced in order to compare models with respect to the amount of "intensional information" that they provide on computation. The proofs are carried out by exhibiting suitable applied λ-calculi, and by exploiting the fundamental lemma of logical relations.
An automaton over data words that captures EMSO logic
Venue: arXiv cs.FL 2011
Year: 2011

We develop a general framework for the specification and implementation of systems whose executions are words, or partial orders, over an infinite alphabet. As a model of an implementation, we introduce class register automata, a one-way automata model over words with multiple data values. Our model combines register automata and class memory automata. It has natural interpretations. In particular, it captures communicating automata with an unbounded number of processes, whose semantics can be described as a set of (dynamic) message sequence charts. On the specification side, we provide a local existential monadic second-order logic that does not impose any restriction on the number of variables. We study the realizability problem and show that every formula from that logic can be effectively, and in elementary time, translated into an equivalent class register automaton.
Bandwidth sharing networks with priority scaling
Venue: arXiv cs.PF 2011
Year: 2011

In multi-class communication networks, traffic surges due to one class of users can significantly degrade the performance for other classes. During these transient periods, it is thus of crucial importance to implement priority mechanisms that conserve the quality of service experienced by the affected classes, while ensuring that the temporarily unstable class is not entirely neglected. In this paper, we examine the complex interaction occurring between several classes of traffic when classes obtain bandwidth proportionally to their incoming traffic. We characterize the evolution of the network from the moment the initial surge takes place until the system reaches its equilibrium. Using an appropriate scaling, we show that the trajectories of the temporarily unstable class can be described by a differential equation, while those of the stable classes retain their stochastic nature. A stochastic averaging phenomenon occurs and the dynamics of the temporarily unstable and the stable classes continue to influence one another. We further proceed to characterize the obtained differential equations and the stability region under this scaling for monotone networks. We illustrate these result on several toy examples and we finally build a penalization rule using these results for a network integrating streaming and elastic traffic.
Team-building with Answer Set Programming in the Gioia-Tauro Seaport
Venue: arXiv cs.LO 2011
Year: 2011

(To appear in Theory and Practice of Logic Programming (TPLP).) The seaport of Gioia Tauro is the largest transshipment terminal of the Mediterranean coast. A crucial management task for the companies operating in the seaport is team building: the problem of properly allocating the available personnel for serving the incoming ships. Teams have to be carefully arranged in order to meet several constraints, such as allocation of the employees with the appropriate skills, fair distribution of the working load, and turnover of the heavy/dangerous roles. This makes team building a hard and expensive task requiring several hours per day of manual preparation. In this paper we present a system based on Answer Set Programming (ASP) for the automatic generation of the teams of employees in the seaport of Gioia Tauro. The system is currently exploited in the Gioia Tauro seaport by ICO BLG, a company specialized in automobile logistics.
A Set and Collection Lemma
Venue: arXiv cs.DM 2011
Year: 2011

A set S is independent if no two vertices from S are adjacent. In this paper we prove that if F is a collection of maximum independent sets of a graph, then there is a matching from S-{intersection of all members of F} into {union of all members of F}-S, for every independent set S. Based on this finding we give alternative proofs for a number of well-known lemmata, as the "Maximum Stable Set Lemma" due to Claude Berge and the "Clique Collection Lemma" due to András Hajnal.
Sweeping an oval to a vanishing point
Venue: arXiv cs.CG 2011
Year: 2011

Given a convex region in the plane, and a sweep-line as a tool, what is best way to reduce the region to a single point by a sequence of sweeps? The problem of sweeping points by orthogonal sweeps was first studied in [2]. Here we consider the following \emph{slanted} variant of sweeping recently introduced in [1]: In a single sweep, the sweep-line is placed at a start position somewhere in the plane, then moved continuously according to a sweep vector $\vec v$ (not necessarily orthogonal to the sweep-line) to another parallel end position, and then lifted from the plane. The cost of a sequence of sweeps is the sum of the lengths of the sweep vectors. The (optimal) sweeping cost of a region is the infimum of the costs over all finite sweeping sequences for that region. An optimal sweeping sequence for a region is one with a minimum total cost, if it exists. Another parameter of interest is the number of sweeps. We show that there exist convex regions for which the optimal sweeping cost cannot be attained by two sweeps. This disproves a conjecture of Bousany, Karker, O'Rourke, and Sparaco stating that two sweeps (with vectors along the two adjacent sides of a minimum-perimeter enclosing parallelogram) always suffice [1]. Moreover, we conjecture that for some convex regions, no finite sweeping sequence is optimal. On the other hand, we show that both the 2-sweep algorithm based on minimum-perimeter enclosing rectangle and the 2-sweep algorithm based on minimum-perimeter enclosing parallelogram achieve a $4/π\approx 1.27$ approximation in this sweeping model.
It Is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular
Venue: arXiv cs.FL 2011
Year: 2011

The hairpin completion is an operation on formal languages which is inspired by the hairpin formation in biochemistry. Hairpin formations occur naturally within DNA-computing. It has been known that the hairpin completion of a regular language is linear context-free, but not regular, in general. However, for some time it is was open whether the regularity of the hairpin completion of a regular language is is decidable. In 2009 this decidability problem has been solved positively by providing a polynomial time algorithm. In this paper we improve the complexity bound by showing that the decision problem is actually NL-complete. This complexity bound holds for both, the one-sided and the two-sided hairpin completions.
Semantics of Higher-Order Recursion Schemes
Venue: arXiv cs.LO 2011
Year: 2011

Higher-order recursion schemes are recursive equations defining new operations from given ones called "terminals". Every such recursion scheme is proved to have a least interpreted semantics in every Scott's model of λ-calculus in which the terminals are interpreted as continuous operations. For the uninterpreted semantics based on infinite λ-terms we follow the idea of Fiore, Plotkin and Turi and work in the category of sets in context, which are presheaves on the category of finite sets. Fiore et al showed how to capture the type of variable binding in λ-calculus by an endofunctor Hλand they explained simultaneous substitution of λ-terms by proving that the presheaf of λ-terms is an initial Hλ-monoid. Here we work with the presheaf of rational infinite λ-terms and prove that this is an initial iterative Hλ-monoid. We conclude that every guarded higher-order recursion scheme has a unique uninterpreted solution in this monoid.
Aircraft Proximity Maps Based on Data-Driven Flow Modeling
Venue: arXiv cs.SY 2011
Year: 2011

With the forecast increase in air traffic demand over the next decades, it is imperative to develop tools to provide traffic flow managers with the information required to support decision making. In particular, decision-support tools for traffic flow management should aid in limiting controller workload and complexity, while supporting increases in air traffic throughput. While many decision-support tools exist for short-term traffic planning, few have addressed the strategic needs for medium- and long-term planning for time horizons greater than 30 minutes. This paper seeks to address this gap through the introduction of 3D aircraft proximity maps that evaluate the future probability of presence of at least one or two aircraft at any given point of the airspace. Three types of proximity maps are presented: presence maps that indicate the local density of traffic; conflict maps that determine locations and probabilities of potential conflicts; and outliers maps that evaluate the probability of conflict due to aircraft not belonging to dominant traffic patterns. These maps provide traffic flow managers with information relating to the complexity and difficulty of managing an airspace. The intended purpose of the maps is to anticipate how aircraft flows will interact, and how outliers impact the dominant traffic flow for a given time period. This formulation is able to predict which "critical" regions may be subject to conflicts between aircraft, thereby requiring careful monitoring. These probabilities are computed using a generative aircraft flow model. Time-varying flow characteristics, such as geometrical configuration, speed, and probability density function of aircraft spatial distribution within the flow, are determined from archived Enhanced Traffic Management System data, using a tailored clustering algorithm. Aircraft not belonging to flows are identified as outliers.
Order Statistics Based List Decoding Techniques for Linear Binary Block Codes
Venue: arXiv cs.IT 2011
Year: 2011

The order statistics based list decoding techniques for linear binary block codes of small to medium block length are investigated. The construction of the list of the test error patterns is considered. The original order statistics decoding is generalized by assuming segmentation of the most reliable independent positions of the received bits. The segmentation is shown to overcome several drawbacks of the original order statistics decoding. The complexity of the order statistics based decoding is further reduced by assuming a partial ordering of the received bits in order to avoid the complex Gauss elimination. The probability of the test error patterns in the decoding list is derived. The bit error rate performance and the decoding complexity trade-off of the proposed decoding algorithms is studied by computer simulations. Numerical examples show that, in some cases, the proposed decoding schemes are superior to the original order statistics decoding in terms of both the bit error rate performance as well as the decoding complexity.
On Sharing Viral Video over an Ad Hoc Wireless Network
Venue: arXiv cs.SI 2011
Year: 2011

We consider the problem of broadcasting a viral video (a large file) over an ad hoc wireless network (e.g., students in a campus). Many smartphones are GPS enabled, and equipped with peer-to-peer (ad hoc) transmission mode, allowing them to wirelessly exchange files over short distances rather than use the carrier's WAN. The demand for the file however is transmitted through the social network (e.g., a YouTube link posted on Facebook). To address this coupled-network problem (demand on the social network; bandwidth on the wireless network) where the two networks have different topologies, we propose a file dissemination algorithm. In our scheme, users query their social network to find geographically nearby friends that have the desired file, and utilize the underlying ad hoc network to route the data via multi-hop transmissions. We show that for many popular models for social networks, the file dissemination time scales sublinearly with n; the number of users, compared to the linear scaling required if each user who wants the file must download it from the carrier's WAN.
Analysing the Control Software of the Compact Muon Solenoid Experiment at the Large Hadron Collider
Venue: arXiv cs.LO 2011
Year: 2011

The control software of the CERN Compact Muon Solenoid experiment contains over 30,000 finite state machines. These state machines are organised hierarchically: commands are sent down the hierarchy and state changes are sent upwards. The sheer size of the system makes it virtually impossible to fully understand the details of its behaviour at the macro level. This is fuelled by unclarities that already exist at the micro level. We have solved the latter problem by formally describing the finite state machines in the mCRL2 process algebra. The translation has been implemented using the ASF+SDF meta-environment, and its correctness was assessed by means of simulations and visualisations of individual finite state machines and through formal verification of subsystems of the control software. Based on the formalised semantics of the finite state machines, we have developed dedicated tooling for checking properties that can be verified on finite state machines in isolation.
A practical guide to Message Structures: a modelling technique for information systems analysis and design
Venue: arXiv cs.SE 2011
Year: 2011

Despite the increasing maturity of model-driven software development (MDD), some research challenges remain open in the field of information systems (IS). For instance, there is a need to improve modelling techniques so that they cover several development stages in an integrated way, and they facilitate the transition from analysis to design. This paper presents Message Structures, a technique for the specification of communicative interactions between the IS and organisational actors. This technique can be used both in the analysis stage and in the design stage. During analysis, it allows abstracting from the technology that will support the IS, and to complement business process diagramming techniques with the specification of the communicational needs of the organisation. During design, Message Structures serves two purposes: (i) it allows to systematically derive a specification of the IS memory (e.g. a UML class diagram), (ii) and it allows to reason the user interface design using abstract patterns. This technique is part of Communication Analysis, a communication-oriented requirements engineering method, but it can be adopted in order to extend widely-used business process and functional requirements modelling techniques (e.g. BPMN, Use Cases). Moreover, the paper presents two tools that support Message Structures, one uses the Xtext technology, and the other uses the Eclipse Modelling Framework. Industrial experience has shown us that the technique can be adopted and applied in complex projects.
A 4/3-approximation for TSP on cubic 3-edge-connected graphs
Venue: arXiv cs.DS 2011
Year: 2011

We provide a polynomial time 4/3 approximation algorithm for TSP on metrics arising from the metric completion of cubic 3-edge connected graphs.