OpenRaiser/Intern-Atlas huggingface dataset:
On a Possible Similarity between Gene and Semantic Networks
Venue: arXiv cs.CL 2015
Year: 2015

In several domains such as linguistics, molecular biology or social sciences, holistic effects are hardly well-defined by modeling with single units, but more and more studies tend to understand macro structures with the help of meaningful and useful associations in fields such as social networks, systems biology or semantic web. A stochastic multi-agent system offers both accurate theoretical framework and operational computing implementations to model large-scale associations, their dynamics and patterns extraction. We show that clustering around a target object in a set of associations of object prove some similarity in specific data and two case studies about gene-gene and term-term relationships leading to an idea of a common organizing principle of cognition with random and deterministic effects.
Multi-Agent Modeling of Dynamical Systems: A Self-organized, Emergent, Homeostatic and Autopoietic Approach
Venue: arXiv cs.MA 2015
Year: 2015

This thesis presents the theoretical, conceptual and methodological aspects that support the modeling of dynamical systems (DS) by using several agents. The modeling approach permits the assessment of properties representing order, change, equilibrium, adaptability, and autonomy, in DS. The modeling processes were supported by a conceptual corpus regarding systems dynamics, multi-agent systems, graph theory, and, particularly, the information theory. Besides to the specification of the dynamical systems as a computational network of agents, metrics that allow characterizing and assessing the inherent complexity of such systems were defined. As a result, properties associated with emergence, self-organization, complexity, homeostasis and autopoiesis were defined, formalized and measured. The validation of the underlying DS model was carried out on discrete systems (boolean networks and cellular automata) and ecological systems. The central contribution of this thesis was the development of a methodological approach for DS modeling. This approach includes a larger set of properties than in traditional studies, what allows us to deepen in questioning essential issues associated with the DS field. All this was achieved from a simple base of calculation and interpretation, which does not require advanced mathematical knowledge, and facilitates their application in different fields of science.
Power Gating Structure for Reversible Programmable Logic Array
Venue: arXiv cs.AR 2015
Year: 2015

Throughout the world, the numbers of researchers or hardware designer struggle for the reducing of power dissipation in low power VLSI systems. This paper presented an idea of using the power gating structure for reducing the sub threshold leakage in the reversible system. This concept presented in the paper is entirely new and presented in the literature of reversible logics. By using the reversible logics for the digital systems, the energy can be saved up to the gate level implementation. But at the physical level designing of the reversible logics by the modern CMOS technology the heat or energy is dissipated due the sub-threshold leakage at the time of inactivity or standby mode. The Reversible Programming logic array (RPLA) is one of the important parts of the low power industrial applications and in this paper the physical design of the RPLA is presented by using the sleep transistor and the results is shown with the help of TINA- PRO software. The results for the proposed design is also compare with the CMOS design and shown that of 40.8% of energy saving. The Transient response is also produces in the paper for the switching activity and showing that the proposed design is much better that the modern CMOS design of the RPLA.
Unfolding Smooth Prismatoids
Venue: arXiv cs.CG 2015
Year: 2015

We define a notion for unfolding smooth, ruled surfaces, and prove that every smooth prismatoid (the convex hull of two smooth curves lying in parallel planes), has a nonoverlapping "volcano unfolding." These unfoldings keep the base intact, unfold the sides outward, splayed around the base, and attach the top to the tip of some side rib. Our result answers a question for smooth prismatoids whose analog for polyhedral prismatoids remains unsolved.
Recursive n-gram hashing is pairwise independent, at best
Venue: arXiv cs.DB 2016
Year: 2016

Many applications use sequences of n consecutive symbols (n-grams). Hashing these n-grams can be a performance bottleneck. For more speed, recursive hash families compute hash values by updating previous values. We prove that recursive hash families cannot be more than pairwise independent. While hashing by irreducible polynomials is pairwise independent, our implementations either run in time O(n) or use an exponential amount of memory. As a more scalable alternative, we make hashing by cyclic polynomials pairwise independent by ignoring n-1 bits. Experimentally, we show that hashing by cyclic polynomials is is twice as fast as hashing by irreducible polynomials. We also show that randomized Karp-Rabin hash families are not pairwise independent.
Efficient Optimally Lazy Algorithms for Minimal-Interval Semantics
Venue: arXiv cs.DS 2016
Year: 2016

Minimal-interval semantics associates with each query over a document a set of intervals, called witnesses, that are incomparable with respect to inclusion (i.e., they form an antichain): witnesses define the minimal regions of the document satisfying the query. Minimal-interval semantics makes it easy to define and compute several sophisticated proximity operators, provides snippets for user presentation, and can be used to rank documents. In this paper we provide algorithms for computing conjunction and disjunction that are linear in the number of intervals and logarithmic in the number of operands; for additional operators, such as ordered conjunction and Brouwerian difference, we provide linear algorithms. In all cases, space is linear in the number of operands. More importantly, we define a formal notion of optimal laziness, and either prove it, or prove its impossibility, for each algorithm. We cast our results in a general framework of antichains of intervals on total orders, making our algorithms directly applicable to other domains.
Sorting improves word-aligned bitmap indexes
Venue: arXiv cs.DB 2016
Year: 2016

Bitmap indexes must be compressed to reduce input/output costs and minimize CPU usage. To accelerate logical operations (AND, OR, XOR) over bitmaps, we use techniques based on run-length encoding (RLE), such as Word-Aligned Hybrid (WAH) compression. These techniques are sensitive to the order of the rows: a simple lexicographical sort can divide the index size by 9 and make indexes several times faster. We investigate row-reordering heuristics. Simply permuting the columns of the table can increase the sorting efficiency by 40%. Secondary contributions include efficient algorithms to construct and aggregate bitmaps. The effect of word length is also reviewed by constructing 16-bit, 32-bit and 64-bit indexes. Using 64-bit CPUs, we find that 64-bit indexes are slightly faster than 32-bit indexes despite being nearly twice as large.
Web 2.0 OLAP: From Data Cubes to Tag Clouds
Venue: arXiv cs.DB 2016
Year: 2016

Increasingly, business projects are ephemeral. New Business Intelligence tools must support ad-lib data sources and quick perusal. Meanwhile, tag clouds are a popular community-driven visualization technique. Hence, we investigate tag-cloud views with support for OLAP operations such as roll-ups, slices, dices, clustering, and drill-downs. As a case study, we implemented an application where users can upload data and immediately navigate through its ad hoc dimensions. To support social networking, views can be easily shared and embedded in other Web sites. Algorithmically, our tag-cloud views are approximate range top-k queries over spontaneous data cubes. We present experimental evidence that iceberg cuboids provide adequate online approximations. We benchmark several browser-oblivious tag-cloud layout optimizations.
Transport of finiteness structures and applications
Venue: arXiv cs.LO 2016
Year: 2016

We describe a general construction of finiteness spaces which subsumes the interpretations of all positive connectors of linear logic. We then show how to apply this construction to prove the existence of least fixpoints for particular functors in the category of finiteness spaces: these include the functors involved in a relational interpretation of lazy recursive algebraic datatypes along the lines of the coherence semantics of system T.
Colored-Gaussian Multiple Descriptions: Spectral and Time-Domain Forms
Venue: arXiv cs.IT 2016
Year: 2016

It is well known that Shannon's rate-distortion function (RDF) in the colored quadratic Gaussian (QG) case can be parametrized via a single Lagrangian variable (the "water level" in the reverse water filling solution). In this work, we show that the symmetric colored QG multiple-description (MD) RDF in the case of two descriptions can be parametrized in the spectral domain via two Lagrangian variables, which control the trade-off between the side distortion, the central distortion, and the coding rate. This spectral-domain analysis is complemented by a time-domain scheme-design approach: we show that the symmetric colored QG MD RDF can be achieved by combining ideas of delta-sigma modulation and differential pulse-code modulation. Specifically, two source prediction loops, one for each description, are embedded within a common noise shaping loop, whose parameters are explicitly found from the spectral-domain characterization.
Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle
Venue: arXiv cs.DM 2016
Year: 2016

Let G be a plane graph with exactly one triangle T and all other cycles of length at least 5, and let C be a facial cycle of G of length at most six. We prove that a 3-coloring of C does not extend to a 3-coloring of G if and only if C has length exactly six and there is a color x such that either G has an edge joining two vertices of C colored x, or T is disjoint from C and every vertex of T is adjacent to a vertex of C colored x. This is a lemma to be used in a future paper of this series.
Fully dynamic maximal matching in O(log n) update time
Venue: arXiv cs.DS 2016
Year: 2016

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes O(log n) expected amortized time for each edge update where n is the number of vertices in the graph. While there is a trivial O(n) algorithm for edge update, the previous best known result for this problem for a graph with n vertices and m edges is O({(n+ m)}^{0.7072})which is sub-linear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfield designed a randomized data structure that achieves O(log^2 n) amortized time for each update for maintaining a c-approximate maximum matching for some large constant c. In contrast, we can maintain a factor two approximate maximum matching in O(log n) expected time per update as a direct corollary of the maximal matching scheme. This in turn also implies a two approximate vertex cover maintenance scheme that takes O(log n) expected time per update.
Computing Strong Game-Theoretic Strategies in Jotto
Venue: arXiv cs.GT 2016
Year: 2016

We develop a new approach that computes approximate equilibrium strategies in Jotto, a popular word game. Jotto is an extremely large two-player game of imperfect information; its game tree has many orders of magnitude more states than games previously studied, including no-limit Texas hold 'em. To address the fact that the game is so large, we propose a novel strategy representation called oracular form, in which we do not explicitly represent a strategy, but rather appeal to an oracle that quickly outputs a sample move from the strategy's distribution. Our overall approach is based on an extension of the fictitious play algorithm to this oracular setting. We demonstrate the superiority of our computed strategies over the strategies computed by a benchmark algorithm, both in terms of head-to-head and worst-case performance.
Better abstractions for timed automata
Venue: arXiv cs.LO 2016
Year: 2016

We consider the reachability problem for timed automata. A standard solution to this problem involves computing a search tree whose nodes are abstractions of zones. These abstractions preserve underlying simulation relations on the state space of the automaton. For both effectiveness and efficiency reasons, they are parametrized by the maximal lower and upper bounds (LU-bounds) occurring in the guards of the automaton. We consider the aLU abstraction defined by Behrmann et al. Since this abstraction can potentially yield non-convex sets, it has not been used in implementations. We prove that aLU abstraction is the biggest abstraction with respect to LU-bounds that is sound and complete for reachability. We also provide an efficient technique to use the aLU abstraction to solve the reachability problem.
Anonymous Meeting in Networks
Venue: arXiv cs.DS 2016
Year: 2016

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. Which configurations are gatherable and how to gather all of them deterministically by the same algorithm? We give a complete solution of this gathering problem in arbitrary networks. We characterize all gatherable configurations and give two universal deterministic gathering algorithms, i.e., algorithms that gather all gatherable configurations. The first algorithm works under the assumption that an upper bound n on the size of the network is known. In this case our algorithm guarantees gathering with detection, i.e., the existence of a round for any gatherable configuration, such that all agents are at the same node and all declare that gathering is accomplished. If no upper bound on the size of the network is known, we show that a universal algorithm for gathering with detection does not exist. Hence, for this harder scenario, we construct a second universal gathering algorithm, which guarantees that, for any gatherable configuration, all agents eventually get to one node and stop, although they cannot tell if gathering is over. The time of the first algorithm is polynomial in the upper bound n on the size of the network, and the time of the second algorithm is polynomial in the (unknown) size itself. Our results have an important consequence for the leader election problem for anonymous agents in arbitrary graphs. For anonymous agents in graphs, leader election turns out to be equivalent to gathering with detection. Hence, as a by-product, we obtain a complete solution of the leader election problem for anonymous agents in arbitrary graphs.
Mean-Payoff Pushdown Games
Venue: arXiv cs.LO 2016
Year: 2016

Two-player games on graphs is central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and $ω$-regular objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean-payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus does not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows (1) One-player pushdown games with mean-payoff objectives under global strategies is decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies is undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies is NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies is NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two-player pushdown games. Finally we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.
Predictive Complexity and Generalized Entropy Rate of Stationary Ergodic Processes
Venue: arXiv cs.IT 2016
Year: 2016

In the online prediction framework, we use generalized entropy of to study the loss rate of predictors when outcomes are drawn according to stationary ergodic distributions over the binary alphabet. We show that the notion of generalized entropy of a regular game \cite{KVV04} is well-defined for stationary ergodic distributions. In proving this, we obtain new game-theoretic proofs of some classical information theoretic inequalities. Using Birkhoff's ergodic theorem and convergence properties of conditional distributions, we prove that a classical Shannon-McMillan-Breiman theorem holds for a restricted class of regular games, when no computational constraints are imposed on the prediction strategies. If a game is mixable, then there is an optimal aggregating strategy which loses at most an additive constant when compared to any other lower semicomputable strategy. The loss incurred by this algorithm on an infinite sequence of outcomes is called its predictive complexity. We use our version of Shannon-McMillan-Breiman theorem to prove that when a restriced regular game has a predictive complexity, the predictive complexity converges to the generalized entropy of the game almost everywhere with respect to the stationary ergodic distribution.
Locally Stable Marriage with Strict Preferences
Venue: arXiv cs.DS 2016
Year: 2016

We study stable matching problems with locality of information and control. In our model, each agent is a node in a fixed network and strives to be matched to another agent. An agent has a complete preference list over all other agents it can be matched with. Agents can match arbitrarily, and they learn about possible partners dynamically based on their current neighborhood. We consider convergence of dynamics to locally stable matchings -- states that are stable with respect to their imposed information structure in the network. In the two-sided case of stable marriage in which existence is guaranteed, we show that the existence of a path to stability becomes NP-hard to decide. This holds even when the network exists only among one partition of agents. In contrast, if one partition has no network and agents remember a previous match every round, a path to stability is guaranteed and random dynamics converge with probability 1. We characterize this positive result in various ways. For instance, it holds for random memory and for cache memory with the most recent partner, but not for cache memory with the best partner. Also, it is crucial which partition of the agents has memory. Finally, we present results for centralized computation of locally stable matchings, i.e., computing maximum locally stable matchings in the two-sided case and deciding existence in the roommates case.
Learning the Interference Graph of a Wireless Network
Venue: arXiv cs.IT 2016
Year: 2016

A key challenge in wireless networking is the management of interference between transmissions. Identifying which transmitters interfere with each other is a crucial first step. In this paper we cast the task of estimating the a wireless interference environment as a graph learning problem. Nodes represent transmitters and edges represent the presence of interference between pairs of transmitters. We passively observe network traffic transmission patterns and collect information on transmission successes and failures. We establish bounds on the number of observations (each a snapshot of a network traffic pattern) required to identify the interference graph reliably with high probability. Our main results are scaling laws that tell us how the number of observations must grow in terms of the total number of nodes $n$ in the network and the maximum number of interfering transmitters $d$ per node (maximum node degree). The effects of hidden terminal interference (i.e., interference not detectable via carrier sensing) on the observation requirements are also quantified. We show that to identify the graph it is necessary and sufficient that the observation period grows like $d^2 \log n$, and we propose a practical algorithm that reliably identifies the graph from this length of observation. The observation requirements scale quite mildly with network size, and networks with sparse interference (small $d$) can be identified more rapidly. Computational experiments based on a realistic simulations of the traffic and protocol lend additional support to these conclusions.
Granular association rules on two universes with four measures
Venue: arXiv cs.DB 2016
Year: 2016

Relational association rules reveal patterns hide in multiple tables. Existing rules are usually evaluated through two measures, namely support and confidence. However, these two measures may not be enough to describe the strength of a rule. In this paper, we introduce granular association rules with four measures to reveal connections between granules in two universes, and propose three algorithms for rule mining. An example of such a rule might be "40% men like at least 30% kinds of alcohol; 45% customers are men and 6% products are alcohol." Here 45%, 6%, 40%, and 30% are the source coverage, the target coverage, the source confidence, and the target confidence, respectively. With these measures, our rules are semantically richer than existing ones. Three subtypes of rules are obtained through considering special requirements on the source/target confidence. Then we define a rule mining problem, and design a sandwich algorithm with different rule checking approaches for different subtypes. Experiments on a real world dataset show that the approaches dedicated to three subtypes are 2-3 orders of magnitudes faster than the one for the general case. A forward algorithm and a backward algorithm for one particular subtype can speed up the mining process further. This work opens a new research trend concerning relational association rule mining, granular computing and rough sets.