OpenRaiser/Intern-Atlas huggingface dataset:
A Concise Query Language with Search and Transform Operations for Corpora with Multiple Levels of Annotation
Venue: arXiv cs.CL 2011
Year: 2011

The usefulness of annotated corpora is greatly increased if there is an associated tool that can allow various kinds of operations to be performed in a simple way. Different kinds of annotation frameworks and many query languages for them have been proposed, including some to deal with multiple layers of annotation. We present here an easy to learn query language for a particular kind of annotation framework based on 'threaded trees', which are somewhere between the complete order of a tree and the anarchy of a graph. Through 'typed' threads, they can allow multiple levels of annotation in the same document. Our language has a simple, intuitive and concise syntax and high expressive power. It allows not only to search for complicated patterns with short queries but also allows data manipulation and specification of arbitrary return values. Many of the commonly used tasks that otherwise require writing programs, can be performed with one or more queries. We compare the language with some others and try to evaluate it.
Succinct Representations of Permutations and Functions
Venue: arXiv cs.DS 2011
Year: 2011

We investigate the problem of succinctly representing an arbitrary permutation, π, on {0,...,n-1} so that π^k(i) can be computed quickly for any i and any (positive or negative) integer power k. A representation taking (1+ε) n lg n + O(1) bits suffices to compute arbitrary powers in constant time, for any positive constant ε<= 1. A representation taking the optimal \ceil{\lg n!} + o(n) bits can be used to compute arbitrary powers in O(lg n / lg lg n) time. We then consider the more general problem of succinctly representing an arbitrary function, f: [n] \rightarrow [n] so that f^k(i) can be computed quickly for any i and any integer power k. We give a representation that takes (1+ε) n lg n + O(1) bits, for any positive constant ε<= 1, and computes arbitrary positive powers in constant time. It can also be used to compute f^k(i), for any negative integer k, in optimal O(1+|f^k(i)|) time. We place emphasis on the redundancy, or the space beyond the information-theoretic lower bound that the data structure uses in order to support operations efficiently. A number of lower bounds have recently been shown on the redundancy of data structures. These lower bounds confirm the space-time optimality of some of our solutions. Furthermore, the redundancy of one of our structures "surpasses" a recent lower bound by Golynski [Golynski, SODA 2009], thus demonstrating the limitations of this lower bound.
On the Structure of Weakly Acyclic Games
Venue: arXiv cs.GT 2011
Year: 2011

The class of weakly acyclic games, which includes potential games and dominance-solvable games, captures many practical application domains. In a weakly acyclic game, from any starting state, there is a sequence of better-response moves that leads to a pure Nash equilibrium; informally, these are games in which natural distributed dynamics, such as better-response dynamics, cannot enter inescapable oscillations. We establish a novel link between such games and the existence of pure Nash equilibria in subgames. Specifically, we show that the existence of a unique pure Nash equilibrium in every subgame implies the weak acyclicity of a game. In contrast, the possible existence of multiple pure Nash equilibria in every subgame is insufficient for weak acyclicity in general; here, we also systematically identify the special cases (in terms of the number of players and strategies) for which this is sufficient to guarantee weak acyclicity.
Reputation-based Incentive Protocols in Crowdsourcing Applications
Venue: arXiv cs.AI 2011
Year: 2011

Crowdsourcing websites (e.g. Yahoo! Answers, Amazon Mechanical Turk, and etc.) emerged in recent years that allow requesters from all around the world to post tasks and seek help from an equally global pool of workers. However, intrinsic incentive problems reside in crowdsourcing applications as workers and requester are selfish and aim to strategically maximize their own benefit. In this paper, we propose to provide incentives for workers to exert effort using a novel game-theoretic model based on repeated games. As there is always a gap in the social welfare between the non-cooperative equilibria emerging when workers pursue their self-interests and the desirable Pareto efficient outcome, we propose a novel class of incentive protocols based on social norms which integrates reputation mechanisms into the existing pricing schemes currently implemented on crowdsourcing websites, in order to improve the performance of the non-cooperative equilibria emerging in such applications. We first formulate the exchanges on a crowdsourcing website as a two-sided market where requesters and workers are matched and play gift-giving games repeatedly. Subsequently, we study the protocol designer's problem of finding an optimal and sustainable (equilibrium) protocol which achieves the highest social welfare for that website. We prove that the proposed incentives protocol can make the website operate close to Pareto efficiency. Moreover, we also examine an alternative scenario, where the protocol designer aims at maximizing the revenue of the website and evaluate the performance of the optimal protocol.
Digital Forensics Analysis of Spectral Estimation Methods
Venue: arXiv cs.CR 2011
Year: 2011

Steganography is the art and science of writing hidden messages in such a way that no one apart from the intended recipient knows of the existence of the message. In today's world, it is widely used in order to secure the information. In this paper, the traditional spectral estimation methods are introduced. The performance analysis of each method is examined by comparing all of the spectral estimation methods. Finally, from utilizing those performance analyses, a brief pros and cons of the spectral estimation methods are given. Also we give a steganography demo by hiding information into a sound signal and manage to pull out the information (i.e, the true frequency of the information signal) from the sound by means of the spectral estimation methods.
Spectral Estimation Methods Comparison and Performance Analysis on a Steganalysis Application
Venue: arXiv cs.CR 2011
Year: 2011

Steganography is the art and science of writing hidden messages in such a way that no one apart from the intended recipient knows of the existence of the message. In today's world, it is widely used in order to secure the information. In this paper, the traditional spectral estimation methods are introduced. The performance analysis of each method is examined by comparing all of the spectral estimation methods. Finally, from utilizing those performance analyses, a brief pros and cons of the spectral estimation methods are given. Also we give a steganography demo by hiding information into a sound signal and manage to pull out the information (i.e, the true frequency of the information signal) from the sound by means of the spectral estimation methods.
Optimal Indexes for Sparse Bit Vectors
Venue: arXiv cs.DS 2011
Year: 2011

We consider the problem of supporting Rank() and Select() operations on a bit vector of length m with n 1 bits. The problem is considered in the succinct index model, where the bit vector is stored in "read-only" memory and an additional data structure, called the index, is created during pre-processing to help answer the above queries. We give asymptotically optimal density-sensitive trade-offs, involving both m and n, that relate the size of the index to the number of accesses to the bit vector (and processing time) needed to answer the above queries. The results are particularly interesting for the case where n = o(m).
Maximal Structuring of Acyclic Process Models
Venue: arXiv cs.SE 2011
Year: 2011

This paper contributes to the solution of the problem of transforming a process model with an arbitrary topology into an equivalent structured process model. In particular, this paper addresses the subclass of process models that have no equivalent well-structured representation but which, nevertheless, can be partially structured into their maximally-structured representation. The structuring is performed under a behavioral equivalence notion that preserves observed concurrency of tasks in equivalent process models. The paper gives a full characterization of the subclass of acyclic process models that have no equivalent well-structured representation but do have an equivalent maximally-structured one, as well as proposes a complete structuring method.
Feature Extraction for Change-Point Detection using Stationary Subspace Analysis
Venue: arXiv cs.LG 2011
Year: 2011

Detecting changes in high-dimensional time series is difficult because it involves the comparison of probability densities that need to be estimated from finite samples. In this paper, we present the first feature extraction method tailored to change point detection, which is based on an extended version of Stationary Subspace Analysis. We reduce the dimensionality of the data to the most non-stationary directions, which are most informative for detecting state changes in the time series. In extensive simulations on synthetic data we show that the accuracy of three change point detection algorithms is significantly increased by a prior feature extraction step. These findings are confirmed in an application to industrial fault monitoring.
A Minimax Linear Quadratic Gaussian Method for Antiwindup Control Synthesis
Venue: arXiv cs.SY 2011
Year: 2011

In this paper, a dynamic antiwindup compensator design is proposed which augments the main controller and guarantees robust performance in the event of input saturation. This is a two stage process in which first a robust optimal controller is designed for an uncertain linear system which guarantees the internal stability of the closed loop system and provides robust performance in the absence of input saturation. Then a minimax linear quadratic Gaussian (LQG) compensator is designed to guarantee the performance in certain domain of attraction, in the presence of input saturation. This antiwindup augmentation only comes into action when plant is subject to input saturation. In order to illustrate the effectiveness of this approach, the proposed method is applied to a tracking control problem for an air-breathing hypersonic flight vehicle (AHFV).
Compressed Encoding for Rank Modulation
Venue: arXiv cs.IT 2011
Year: 2011

Rank modulation has been recently proposed as a scheme for storing information in flash memories. While rank modulation has advantages in improving write speed and endurance, the current encoding approach is based on the "push to the top" operation that is not efficient in the general case. We propose a new encoding procedure where a cell level is raised to be higher than the minimal necessary subset - instead of all - of the other cell levels. This new procedure leads to a significantly more compressed (lower charge levels) encoding. We derive an upper bound for a family of codes that utilize the proposed encoding procedure, and consider code constructions that achieve that bound for several special cases.
Vehicular Ad Hoc and Sensor Networks; Principles and Challenges
Venue: arXiv cs.NI 2011
Year: 2011

The rapid increase of vehicular traffic and congestion on the highways began hampering the safe and efficient movement of traffic. Consequently, year by year, we see the ascending rate of car accidents and casualties in most of the countries. Therefore, exploiting the new technologies, e.g. wireless sensor networks, is required as a solution of reduction of these saddening and reprehensible statistics. This has motivated us to propose a novel and comprehensive system to utilize Wireless Sensor Networks for vehicular networks. We coin the vehicular network employing wireless Sensor networks as Vehicular Ad Hoc and Sensor Network, or VASNET in short. The proposed VASNET is particularly for highway traffic .VASNET is a self-organizing Ad Hoc and sensor network comprised of a large number of sensor nodes. In VASNET there are two kinds of sensor nodes, some are embedded on the vehicles-vehicular nodes- and others are deployed in predetermined distances besides the highway road, known as Road Side Sensor nodes (RSS). The vehicular nodes are used to sense the velocity of the vehicle for instance. We can have some Base Stations (BS) such as Police Traffic Station, Firefighting Group and Rescue Team. The base stations may be stationary or mobile. VASNET provides capability of wireless communication between vehicular nodes and stationary nodes, to increase safety and comfort for vehicles on the highway roads. In this paper we explain main fundamentals and challenges of VASNET.
Some Problems in Automata Theory Which Depend on the Models of Set Theory
Venue: arXiv cs.FL 2011
Year: 2011

We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an omega-language $L(A)$ accepted by a Büchi 1-counter automaton $A$. We prove the following surprising result: there exists a 1-counter Büchi automaton $A$ such that the cardinality of the complement $L(A)^-$ of the omega-language $L(A)$ is not determined by ZFC: (1). There is a model $V_1$ of ZFC in which $L(A)^-$ is countable. (2). There is a model $V_2$ of ZFC in which $L(A)^-$ has cardinal $2^{\aleph_0}$. (3). There is a model $V_3$ of ZFC in which $L(A)^-$ has cardinal $\aleph_1$ with $\aleph_0<\aleph_1<2^{\aleph_0}$. We prove a very similar result for the complement of an infinitary rational relation accepted by a 2-tape Büchi automaton $B$. As a corollary, this proves that the Continuum Hypothesis may be not satisfied for complements of 1-counter omega-languages and for complements of infinitary rational relations accepted by 2-tape Büchi automata. We infer from the proof of the above results that basic decision problems about 1-counter omega-languages or infinitary rational relations are actually located at the third level of the analytical hierarchy. In particular, the problem to determine whether the complement of a 1-counter omega-language (respectively, infinitary rational relation) is countable is in $Σ_3^1 \setminus (Π_2^1 \cup Σ_2^1)$. This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).
Symmetric Group Testing and Superimposed Codes
Venue: arXiv cs.IT 2011
Year: 2011

We describe a generalization of the group testing problem termed symmetric group testing. Unlike in classical binary group testing, the roles played by the input symbols zero and one are "symmetric" while the outputs are drawn from a ternary alphabet. Using an information-theoretic approach, we derive sufficient and necessary conditions for the number of tests required for noise-free and noisy reconstructions. Furthermore, we extend the notion of disjunct (zero-false-drop) and separable (uniquely decipherable) codes to the case of symmetric group testing. For the new family of codes, we derive bounds on their size based on probabilistic methods, and provide construction methods based on coding theoretic ideas.
On the Unification of Process Semantics: Logical Semantics
Venue: arXiv cs.LO 2011
Year: 2011

We continue with the task of obtaining a unifying view of process semantics by considering in this case the logical characterization of the semantics. We start by considering the classic linear time-branching time spectrum developed by R.J. van Glabbeek. He provided a logical characterization of most of the semantics in his spectrum but, without following a unique pattern. In this paper, we present a uniform logical characterization of all the semantics in the enlarged spectrum. The common structure of the formulas that constitute all the corresponding logics gives us a much clearer picture of the spectrum, clarifying the relations between the different semantics, and allows us to develop generic proofs of some general properties of the semantics.
Modeling and frequency domain analysis of nonlinear compliant joints for a passive dynamic swimmer
Venue: arXiv cs.RO 2011
Year: 2011

In this paper we present the study of the mathematical model of a real life joint used in an underwater robotic fish. Fluid-structure interaction is utterly simplified and the motion of the joint is approximated by Düffing's equation. We compare the quality of analytical harmonic solutions previously reported, with the input-output relation obtained via truncated Volterra series expansion. Comparisons show a trade-off between accuracy and flexibility of the methods. The methods are discussed in detail in order to facilitate reproduction of our results. The approach presented herein can be used to verify results in nonlinear resonance applications and in the design of bio-inspired compliant robots that exploit passive properties of their dynamics. We focus on the potential use of this type of joint for energy extraction from environmental sources, in this case a Kármán vortex street shed by an obstacle in a flow. Open challenges and questions are mentioned throughout the document.
Comparing System Dynamics and Agent-Based Simulation for Tumour Growth and its Interactions with Effector Cells
Venue: arXiv cs.CE 2011
Year: 2011

There is little research concerning comparisons and combination of System Dynamics Simulation (SDS) and Agent Based Simulation (ABS). ABS is a paradigm used in many levels of abstraction, including those levels covered by SDS. We believe that the establishment of frameworks for the choice between these two simulation approaches would contribute to the simulation research. Hence, our work aims for the establishment of directions for the choice between SDS and ABS approaches for immune system-related problems. Previously, we compared the use of ABS and SDS for modelling agents' behaviour in an environment with nomovement or interactions between these agents. We concluded that for these types of agents it is preferable to use SDS, as it takes up less computational resources and produces the same results as those obtained by the ABS model. In order to move this research forward, our next research question is: if we introduce interactions between these agents will SDS still be the most appropriate paradigm to be used? To answer this question for immune system simulation problems, we will use, as case studies, models involving interactions between tumour cells and immune effector cells. Experiments show that there are cases where SDS and ABS can not be used interchangeably, and therefore, their comparison is not straightforward.
Information Centric Networking based Handover Support for QoS Maintenance in Cooperative Heterogeneous Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

Network of Information (NetInf) is a term coined for networks which unlike contemporary network are not node centric. As the name indicates, information supersedes nodes in the network. In this report, we propose an architecture of mobile node for NetInf. We call it NetInf Mobile Node. It is an extension of the basic node architecture proposed for NetInf. It is compatible to NetInf and TCP/IP based networks. The Virtual Node Layer modules in the architecture provide support for managing mobility, power consumption of the node as well data relaying/storing services. In- ner/Outer Locator Construction Routers (I/O LCTR) are two functions introduced in NetInf mobile nodes to operate between NetInf and non- NetInf sites. The basic purpose of NetInf mobile node is to maintain the QoS during mobility events. The handoff/handover are critical situations during mobility where chances of QoS degradation of an ongoing session are high. This report presents one such scenario in which QoS of an appli- cation is maintained during a handoff situations in heterogeneous wireless network environment through our proposed algorithm.
Multi-robot Deployment From LTL Specifications with Reduced Communication
Venue: arXiv cs.RO 2011
Year: 2011

In this paper, we develop a computational framework for fully automatic deployment of a team of unicycles from a global specification given as an LTL formula over some regions of interest. Our hierarchical approach consists of four steps: (i) the construction of finite abstractions for the motions of each robot, (ii) the parallel composition of the abstractions, (iii) the generation of a satisfying motion of the team; (iv) mapping this motion to individual robot control and communication strategies. The main result of the paper is an algorithm to reduce the amount of inter-robot communication during the fourth step of the procedure.
Self-Adjusting Stack Machines
Venue: arXiv cs.PL 2011
Year: 2011

Self-adjusting computation offers a language-based approach to writing programs that automatically respond to dynamically changing data. Recent work made significant progress in developing sound semantics and associated implementations of self-adjusting computation for high-level, functional languages. These techniques, however, do not address issues that arise for low-level languages, i.e., stack-based imperative languages that lack strong type systems and automatic memory management. In this paper, we describe techniques for self-adjusting computation which are suitable for low-level languages. Necessarily, we take a different approach than previous work: instead of starting with a high-level language with additional primitives to support self-adjusting computation, we start with a low-level intermediate language, whose semantics is given by a stack-based abstract machine. We prove that this semantics is sound: it always updates computations in a way that is consistent with full reevaluation. We give a compiler and runtime system for the intermediate language used by our abstract machine. We present an empirical evaluation that shows that our approach is efficient in practice, and performs favorably compared to prior proposals.
Simple Low-Rate Non-Binary LDPC Coding for Relay Channels
Venue: arXiv cs.IT 2011
Year: 2011

Binary LDPC coded relay systems have been well studied previously with the assumption of infinite codeword length. In this paper, we deal with non-binary LDPC codes which can outperform their binary counterpart especially for practical codeword length. We utilize non-binary LDPC codes and recently invented non-binary coding techniques known as multiplicative repetition to design the low-rate coding strategy for the decode-and-forward half-duplex relay channel. We claim that the proposed strategy is simple since the destination and the relay can decode with almost the same computational complexity by sharing the same structure of decoder. Numerical experiments are carried out to show that the performances obtained by non-binary LDPC coded relay systems surpass the capacity of direct transmission and also approach within less than 1.5 dB from the achievable rate of the relay channels.
A Machine Learning Perspective on Predictive Coding with PAQ
Venue: arXiv cs.LG 2011
Year: 2011

PAQ8 is an open source lossless data compression algorithm that currently achieves the best compression rates on many benchmarks. This report presents a detailed description of PAQ8 from a statistical machine learning perspective. It shows that it is possible to understand some of the modules of PAQ8 and use this understanding to improve the method. However, intuitive statistical explanations of the behavior of other modules remain elusive. We hope the description in this report will be a starting point for discussions that will increase our understanding, lead to improvements to PAQ8, and facilitate a transfer of knowledge from PAQ8 to other machine learning methods, such a recurrent neural networks and stochastic memoizers. Finally, the report presents a broad range of new applications of PAQ to machine learning tasks including language modeling and adaptive text prediction, adaptive game playing, classification, and compression using features from the field of deep learning.