OpenRaiser/Intern-Atlas huggingface dataset:
Narrowing the Modeling Gap: A Cluster-Ranking Approach to Coreference Resolution
Venue: arXiv cs.CL 2014
Year: 2014

Traditional learning-based coreference resolvers operate by training the mention-pair model for determining whether two mentions are coreferent or not. Though conceptually simple and easy to understand, the mention-pair model is linguistically rather unappealing and lags far behind the heuristic-based coreference models proposed in the pre-statistical NLP era in terms of sophistication. Two independent lines of recent research have attempted to improve the mention-pair model, one by acquiring the mention-ranking model to rank preceding mentions for a given anaphor, and the other by training the entity-mention model to determine whether a preceding cluster is coreferent with a given mention. We propose a cluster-ranking approach to coreference resolution, which combines the strengths of the mention-ranking model and the entity-mention model, and is therefore theoretically more appealing than both of these models. In addition, we seek to improve cluster rankers via two extensions: (1) lexicalization and (2) incorporating knowledge of anaphoricity by jointly modeling anaphoricity determination and coreference resolution. Experimental results on the ACE data sets demonstrate the superior performance of cluster rankers to competing approaches as well as the effectiveness of our two extensions.
An Incomplete Cryptography based Digital Rights Management with DCFF
Venue: arXiv cs.CR 2014
Year: 2014

In general, DRM (Digital Rights Management) system is responsible for the safe distribution of digital content, however, DRM system is achieved with individual function modules of cryptography, watermarking and so on. In this typical system flow, it has a problem that all original digital contents are temporarily disclosed with perfect condition via decryption process. In this paper, we propose the combination of the differential codes and fragile fingerprinting (DCFF) method based on incomplete cryptography that holds promise for a better compromise between practicality and security for emerging digital rights management applications. Experimental results with simulation confirmed that DCFF keeps compatibility with standard JPEG codec, and revealed that the proposed method is suitable for DRM in the network distribution system.
Dynamic Hierarchical Bayesian Network for Arabic Handwritten Word Recognition
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents a new probabilistic graphical model used to model and recognize words representing the names of Tunisian cities. In fact, this work is based on a dynamic hierarchical Bayesian network. The aim is to find the best model of Arabic handwriting to reduce the complexity of the recognition process by permitting the partial recognition. Actually, we propose a segmentation of the word based on smoothing the vertical histogram projection using different width values to reduce the error of segmentation. Then, we extract the characteristics of each cell using the Zernike and HU moments, which are invariant to rotation, translation and scaling. Our approach is tested using the IFN / ENIT database, and the experiment results are very promising.
Intuitionistic PUC-Logic for Constructive Counterfactuals
Venue: arXiv cs.LO 2014
Year: 2014

We present the intuitionistic version of PUC-Logic. After that, we present a constructive approach to Lewis' counterfactual abstraction to show that it does not require the classical absurd rule.
Prometheus: LT Codes Meet Cooperative Transmission in Cellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

Following fast growth of cellular networks, more users have drawn attention to the contradiction between dynamic user data traffic and static data plans. To address this important but largely unexplored issue, in this paper, we design a new data plan sharing system named Prometheus, which is based on the scenario that some smartphone users have surplus data traffic and are willing to help others download data. To realize this system, we first propose a mechanism that incorporates LT codes into UDP. It is robust to transmission errors and encourages more concurrent transmissions and forwardings. It also can be implemented easily with low implementation complexity. Then we design an incentive mechanism using a Stackelberg game to choose assistant users ($AUs$), all participants will gain credits in return, which can be used to ask for future help when they need to download something. Finally real environment experiments are conducted and the results show that users in our Prometheus not only can manage their surplus data plan more efficiently, but also achieve a higher speed download rate.
Computing necessary integrability conditions for planar parametrized homogeneous potentials
Venue: arXiv cs.SC 2014
Year: 2014

Let $V\in\mathbb{Q}(i)(\a_1,\dots,\a_n)(\q_1,\q_2)$ be a rationally parametrized planar homogeneous potential of homogeneity degree $k\neq -2, 0, 2$. We design an algorithm that computes polynomial \emph{necessary} conditions on the parameters $(\a_1,\dots,\a_n)$ such that the dynamical system associated to the potential $V$ is integrable. These conditions originate from those of the Morales-Ramis-Simó integrability criterion near all Darboux points. The implementation of the algorithm allows to treat applications that were out of reach before, for instance concerning the non-integrability of polynomial potentials up to degree $9$. Another striking application is the first complete proof of the non-integrability of the \emph{collinear three body problem}.
Off-Policy Shaping Ensembles in Reinforcement Learning
Venue: arXiv cs.AI 2014
Year: 2014

Recent advances of gradient temporal-difference methods allow to learn off-policy multiple value functions in parallel with- out sacrificing convergence guarantees or computational efficiency. This opens up new possibilities for sound ensemble techniques in reinforcement learning. In this work we propose learning an ensemble of policies related through potential-based shaping rewards. The ensemble induces a combination policy by using a voting mechanism on its components. Learning happens in real time, and we empirically show the combination policy to outperform the individual policies of the ensemble.
Improved Performance of RF Energy Powered Wireless Sensor Node with Cooperative Beam Selection
Venue: arXiv cs.IT 2014
Year: 2014

RF energy harvesting is a promising potential solution to provide convenient and perpetual energy supplies to low-power wireless sensor networks. In this paper, we investigate the energy harvesting performance of a wireless sensor node powered by harvesting RF energy from existing multiuser MIMO system. Specifically, we propose a random unitary beamforming (RUB) based cooperative beam selection scheme to enhance the energy harvesting performance at the sensor. Under a constant total transmission power constraint, the multiuser MIMO system tries to select a maximal number of active beams for data transmission, while satisfying the energy harvesting requirement at the sensor. We derive the exact closed-form expression for the distribution function of harvested energy in a coherence time over Rayleigh fading channels. We further investigate the performance tradeoff of the average harvested energy at the sensor versus the sum-rate of the multiuser MIMO system.
Web Log Data Analysis by Enhanced Fuzzy C Means Clustering
Venue: arXiv cs.IR 2014
Year: 2014

World Wide Web is a huge repository of information and there is a tremendous increase in the volume of information daily. The number of users are also increasing day by day. To reduce users browsing time lot of research is taken place. Web Usage Mining is a type of web mining in which mining techniques are applied in log data to extract the behaviour of users. Clustering plays an important role in a broad range of applications like Web analysis, CRM, marketing, medical diagnostics, computational biology, and many others. Clustering is the grouping of similar instances or objects. The key factor for clustering is some sort of measure that can determine whether two objects are similar or dissimilar . In this paper a novel clustering method to partition user sessions into accurate clusters is discussed. The accuracy and various performance measures of the proposed algorithm shows that the proposed method is a better method for web log mining.
On Local and Global Centrality in Large Scale Networks
Venue: arXiv cs.SI 2014
Year: 2014

Estimating influential nodes in large scale networks including but not limited to social networks, biological networks, communication networks, emerging smart grids etc. is a topic of fundamental interest. To understand influences of nodes in a network, a classical metric is centrality within which there are multiple specific instances including degree centrality, closeness centrality, betweenness centrality and more. As of today, existing algorithms to identify nodes with high centrality measures operate upon the entire (or rather global) network, resulting in high computational complexity. In this paper, we design efficient algorithms for determining the betweenness centrality in large scale networks by taking advantage of the modular topology exhibited by most of these large scale networks. Very briefly, modular topologies are those wherein the entire network appears partitioned into distinct modules (or clusters or communities), wherein nodes within the module (that likely share highly similar profiles) have dense connections between them, while connections across modules are relatively sparse. Using a novel adaptation of Dijkstra's shortest path algorithm, and executing it over local modules and over sparse edges between modules, we design algorithms that can correctly compute the betweenness centrality much faster than existing algorithms. To the best of our knowledge, ours is the first work that leverage modular topologies of large scale networks to address the centrality problem, though here we mostly limit our discussions to social networks. We also provide more insights on centrality in general, and also how our algorithms can be used to determine other centrality measures.
Saturation algorithms for model-checking pushdown systems
Venue: arXiv cs.FL 2014
Year: 2014

We present a survey of the saturation method for model-checking pushdown systems.
Equivalence Problems for Tree Transducers: A Brief Survey
Venue: arXiv cs.FL 2014
Year: 2014

The decidability of equivalence for three important classes of tree transducers is discussed. Each class can be obtained as a natural restriction of deterministic macro tree transducers (MTTs): (1) no context parameters, i.e., top-down tree transducers, (2) linear size increase, i.e., MSO definable tree transducers, and (3) monadic input and output ranked alphabets. For the full class of MTTs, decidability of equivalence remains a long-standing open problem.
Similarity density of the Thue-Morse word with overlap-free infinite binary words
Venue: arXiv cs.FL 2014
Year: 2014

We consider a measure of similarity for infinite words that generalizes the notion of asymptotic or natural density of subsets of natural numbers from number theory. We show that every overlap-free infinite binary word, other than the Thue-Morse word t and its complement t bar, has this measure of similarity with t between 1/4 and 3/4. This is a partial generalization of a classical 1927 result of Mahler.
More Structural Characterizations of Some Subregular Language Families by Biautomata
Venue: arXiv cs.FL 2014
Year: 2014

We study structural restrictions on biautomata such as, e.g., acyclicity, permutation-freeness, strongly permutation-freeness, and orderability, to mention a few. We compare the obtained language families with those induced by deterministic finite automata with the same property. In some cases, it is shown that there is no difference in characterization between deterministic finite automata and biautomata as for the permutation-freeness, but there are also other cases, where it makes a big difference whether one considers deterministic finite automata or biautomata. This is, for instance, the case when comparing strongly permutation-freeness, which results in the family of definite language for deterministic finite automata, while biautomata induce the family of finite and co-finite languages. The obtained results nicely fall into the known landscape on classical language families.
Boolean Circuit Complexity of Regular Languages
Venue: arXiv cs.FL 2014
Year: 2014

In this paper we define a new descriptional complexity measure for Deterministic Finite Automata, BC-complexity, as an alternative to the state complexity. We prove that for two DFAs with the same number of states BC-complexity can differ exponentially. In some cases minimization of DFA can lead to an exponential increase in BC-complexity, on the other hand BC-complexity of DFAs with a large state space which are obtained by some standard constructions (determinization of NFA, language operations), is reasonably small. But our main result is the analogue of the "Shannon effect" for finite automata: almost all DFAs with a fixed number of states have BC-complexity that is close to the maximum.
Resource Allocation in Wireless Networks with RF Energy Harvesting and Transfer
Venue: arXiv cs.NI 2014
Year: 2014

Radio frequency (RF) energy harvesting and transfer techniques have recently become alternative methods to power the next generation of wireless networks. As this emerging technology enables proactive replenishment of wireless devices, it is advantageous in supporting applications with quality-of-service (QoS) requirement. This article focuses on the resource allocation issues in wireless networks with RF energy harvesting capability, referred to as RF energy harvesting networks (RF-EHNs). First, we present an overview of the RF-EHNs, followed by a review of a variety of issues regarding resource allocation. Then, we present a case study of designing in the receiver operation policy, which is of paramount importance in the RF-EHNs. We focus on QoS support and service differentiation, which have not been addressed by previous literatures. Furthermore, we outline some open research directions.
On Green Energy Powered Cognitive Radio Networks
Venue: arXiv cs.NI 2014
Year: 2014

Green energy powered cognitive radio (CR) network is capable of liberating the wireless access networks from spectral and energy constraints. The limitation of the spectrum is alleviated by exploiting cognitive networking in which wireless nodes sense and utilize the spare spectrum for data communications, while dependence on the traditional unsustainable energy is assuaged by adopting energy harvesting (EH) through which green energy can be harnessed to power wireless networks. Green energy powered CR increases the network availability and thus extends emerging network applications. Designing green CR networks is challenging. It requires not only the optimization of dynamic spectrum access but also the optimal utilization of green energy. This paper surveys the energy efficient cognitive radio techniques and the optimization of green energy powered wireless networks. Existing works on energy aware spectrum sensing, management, and sharing are investigated in detail. The state of the art of the energy efficient CR based wireless access network is discussed in various aspects such as relay and cooperative radio and small cells. Envisioning green energy as an important energy resource in the future, network performance highly depends on the dynamics of the available spectrum and green energy. As compared with the traditional energy source, the arrival rate of green energy, which highly depends on the environment of the energy harvesters, is rather random and intermittent. To optimize and adapt the usage of green energy according to the opportunistic spectrum availability, we discuss research challenges in designing cognitive radio networks which are powered by energy harvesters.
Extended AIGER Format for Synthesis
Venue: arXiv cs.OH 2014
Year: 2014

We extend the AIGER format, as used in HWMCC, to a format that is suitable to define synthesis problems with safety specifications. We recap the original format and define one format for posing synthesis problems and one for solutions of synthesis problems in this setting.
MOSDEN: A Scalable Mobile Collaborative Platform for Opportunistic Sensing Applications
Venue: arXiv cs.NI 2014
Year: 2014

Mobile smartphones along with embedded sensors have become an efficient enabler for various mobile applications including opportunistic sensing. The hi-tech advances in smartphones are opening up a world of possibilities. This paper proposes a mobile collaborative platform called MOSDEN that enables and supports opportunistic sensing at run time. MOSDEN captures and shares sensor data across multiple apps, smartphones and users. MOSDEN supports the emerging trend of separating sensors from application-specific processing, storing and sharing. MOSDEN promotes reuse and re-purposing of sensor data hence reducing the efforts in developing novel opportunistic sensing applications. MOSDEN has been implemented on Android-based smartphones and tablets. Experimental evaluations validate the scalability and energy efficiency of MOSDEN and its suitability towards real world applications. The results of evaluation and lessons learned are presented and discussed in this paper.
Verifying Monadic Second-Order Properties of Graph Programs
Venue: arXiv cs.LO 2014
Year: 2014

The core challenge in a Hoare- or Dijkstra-style proof system for graph programs is in defining a weakest liberal precondition construction with respect to a rule and a postcondition. Previous work addressing this has focused on assertion languages for first-order properties, which are unable to express important global properties of graphs such as acyclicity, connectedness, or existence of paths. In this paper, we extend the nested graph conditions of Habel, Pennemann, and Rensink to make them equivalently expressive to monadic second-order logic on graphs. We present a weakest liberal precondition construction for these assertions, and demonstrate its use in verifying non-local correctness specifications of graph programs in the sense of Habel et al.
Polynomial trajectory algorithm for a biped robot
Venue: arXiv cs.RO 2014
Year: 2014

Building trajectories for biped robot walking is a complex task considering all degrees of freedom (DOFs) commonly bound within the mechanical structure. A typical problem for such robots is the instability produced by violent transitions between walking phases in particular when a swinging leg impacts the surface. Although extensive research on novel efficient walking algorithms has been conducted, falls commonly appear as the walking speed increases or as the terrain condition changes. This paper presents a polynomial trajectory generation algorithm (PTA) to implement the walking on biped robots following the cubic Hermitian polynomial interpolation between initial and final conditions. The proposed algorithm allows smooth transitions between walking phases, significantly reducing the possibility of falling. The algorithm has been successfully tested by generating walking trajectories under different terrain conditions on a biped robot of 10 DOFs. PTA has shown to be simple and suitable to generate real time walking trajectories, despite reduced computing resources of a commercial embedded microcontroller. Experimental evidence and comparisons to other state-of-the-art methods demonstrates a better performance of the proposed method in generating walking trajectories under different ground conditions.
Living on the Edge: The Role of Proactive Caching in 5G Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

This article explores one of the key enablers of beyond $4$G wireless networks leveraging small cell network deployments, namely proactive caching. Endowed with predictive capabilities and harnessing recent developments in storage, context-awareness and social networks, peak traffic demands can be substantially reduced by proactively serving predictable user demands, via caching at base stations and users' devices. In order to show the effectiveness of proactive caching, we examine two case studies which exploit the spatial and social structure of the network, where proactive caching plays a crucial role. Firstly, in order to alleviate backhaul congestion, we propose a mechanism whereby files are proactively cached during off-peak demands based on file popularity and correlations among users and files patterns. Secondly, leveraging social networks and device-to-device (D2D) communications, we propose a procedure that exploits the social structure of the network by predicting the set of influential users to (proactively) cache strategic contents and disseminate them to their social ties via D2D communications. Exploiting this proactive caching paradigm, numerical results show that important gains can be obtained for each case study, with backhaul savings and a higher ratio of satisfied users of up to $22\%$ and $26\%$, respectively. Higher gains can be further obtained by increasing the storage capability at the network edge.
Cyclic codes over the ring $ \Z_p[u, v]/\langle u^2, v^2, uv-vu\rangle$
Venue: arXiv cs.IT 2014
Year: 2014

Let $p$ be a prime number. In this paper, we study cyclic codes over the ring $ \Z_p[u, v]/\langle u^2, v^2, uv-vu\rangle$. We find a unique set of generators for these codes. We also study the rank and the Hamming distance of these codes. We obtain all except one ternary optimal code of length 12 as the Gray image of the cyclic codes over the ring $ \Z_p[u, v]/\langle u^2, v^2, uv-vu\rangle$. We also characterize the $p$-ary image of these cyclic codes under the Gray map.
Understanding model counting for $β$-acyclic CNF-formulas
Venue: arXiv cs.CC 2014
Year: 2014

We extend the knowledge about so-called structural restrictions of $\mathrm{\#SAT}$ by giving a polynomial time algorithm for $β$-acyclic $\mathrm{\#SAT}$. In contrast to previous algorithms in the area, our algorithm does not proceed by dynamic programming but works along an elimination order, solving a weighted version of constraint satisfaction. Moreover, we give evidence that this deviation from more standard algorithm is not a coincidence, but that there is likely no dynamic programming algorithm of the usual style for $β$-acyclic $\mathrm{\#SAT}$.
Online Linear Optimization via Smoothing
Venue: arXiv cs.LG 2014
Year: 2014

We present a new optimization-theoretic approach to analyzing Follow-the-Leader style algorithms, particularly in the setting where perturbations are used as a tool for regularization. We show that adding a strongly convex penalty function to the decision rule and adding stochastic perturbations to data correspond to deterministic and stochastic smoothing operations, respectively. We establish an equivalence between "Follow the Regularized Leader" and "Follow the Perturbed Leader" up to the smoothness properties. This intuition leads to a new generic analysis framework that recovers and improves the previous known regret bounds of the class of algorithms commonly known as Follow the Perturbed Leader.
Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
Venue: arXiv cs.SC 2014
Year: 2014

Cylindrical algebraic decomposition (CAD) is a key tool for solving problems in real algebraic geometry and beyond. In recent years a new approach has been developed, where regular chains technology is used to first build a decomposition in complex space. We consider the latest variant of this which builds the complex decomposition incrementally by polynomial and produces CADs on whose cells a sequence of formulae are truth-invariant. Like all CAD algorithms the user must provide a variable ordering which can have a profound impact on the tractability of a problem. We evaluate existing heuristics to help with the choice for this algorithm, suggest improvements and then derive a new heuristic more closely aligned with the mechanics of the new algorithm.