OpenRaiser/Intern-Atlas huggingface dataset:
10 Inventions on modular keyboards: A TRIZ based analysis
Venue: arXiv cs.HC 2013
Year: 2013

As a standard keyboard is quite spacious many inventions try to use the space of keyboard to use for various activities. A modular keyboard is designed in such a way that the components of the keyboard can be attached and detached as per the need. This article illustrates 10 inventions on modular keyboard from US patent database. The objective of these inventions is to make a keyboard modular, so that the same keyboard can be made smaller by detaching some of its components and larger by attaching additional attachments. Some modular keyboards provide slots for external attachments like mouse, telephone, speakers, joystick and storage devices etc.
Sparse Solution of Underdetermined Linear Equations via Adaptively Iterative Thresholding
Venue: arXiv cs.IT 2013
Year: 2013

Finding the sparset solution of an underdetermined system of linear equations $y=Ax$ has attracted considerable attention in recent years. Among a large number of algorithms, iterative thresholding algorithms are recognized as one of the most efficient and important classes of algorithms. This is mainly due to their low computational complexities, especially for large scale applications. The aim of this paper is to provide guarantees on the global convergence of a wide class of iterative thresholding algorithms. Since the thresholds of the considered algorithms are set adaptively at each iteration, we call them adaptively iterative thresholding (AIT) algorithms. As the main result, we show that as long as $A$ satisfies a certain coherence property, AIT algorithms can find the correct support set within finite iterations, and then converge to the original sparse solution exponentially fast once the correct support set has been identified. Meanwhile, we also demonstrate that AIT algorithms are robust to the algorithmic parameters. In addition, it should be pointed out that most of the existing iterative thresholding algorithms such as hard, soft, half and smoothly clipped absolute deviation (SCAD) algorithms are included in the class of AIT algorithms studied in this paper.
MOSDEN: An Internet of Things Middleware for Resource Constrained Mobile Devices
Venue: arXiv cs.NI 2013
Year: 2013

The Internet of Things (IoT) is part of Future Internet and will comprise many billions of Internet Connected Objects (ICO) or `things' where things can sense, communicate, compute and potentially actuate as well as have intelligence, multi-modal interfaces, physical/ virtual identities and attributes. Collecting data from these objects is an important task as it allows software systems to understand the environment better. Many different hardware devices may involve in the process of collecting and uploading sensor data to the cloud where complex processing can occur. Further, we cannot expect all these objects to be connected to the computers due to technical and economical reasons. Therefore, we should be able to utilize resource constrained devices to collect data from these ICOs. On the other hand, it is critical to process the collected sensor data before sending them to the cloud to make sure the sustainability of the infrastructure due to energy constraints. This requires to move the sensor data processing tasks towards the resource constrained computational devices (e.g. mobile phones). In this paper, we propose Mobile Sensor Data Processing Engine (MOSDEN), an plug-in-based IoT middleware for mobile devices, that allows to collect and process sensor data without programming efforts. Our architecture also supports sensing as a service model. We present the results of the evaluations that demonstrate its suitability towards real world deployments. Our proposed middleware is built on Android platform.
On the Griesmer Bound for Systematic Codes
Venue: arXiv cs.IT 2013
Year: 2013

We generalize the Griesmer bound in the case of systematic codes over a field of size q greater than the distance d of the code. We also generalize the Griesmer bound in the case of any systematic code of distance 2,3,4 and in the case of binary systematic codes of distance up to 6.
A Computational Model of Two Cognitive Transitions Underlying Cultural Evolution
Venue: arXiv cs.AI 2013
Year: 2013

We tested the computational feasibility of the proposal that open-ended cultural evolution was made possible by two cognitive transitions: (1) onset of the capacity to chain thoughts together, followed by (2) onset of contextual focus (CF): the capacity to shift between a divergent mode of thought conducive to 'breaking out of a rut' and a convergent mode of thought conducive to minor modifications. These transitions were simulated in EVOC, an agent-based model of cultural evolution, in which the fitness of agents' actions increases as agents invent ideas for new actions, and imitate the fittest of their neighbors' actions. Both mean fitness and diversity of actions across the society increased with chaining, and even more so with CF, as hypothesized. CF was only effective when the fitness function changed, which supports its hypothesized role in generating and refining ideas.
An Extensive Report on Cellular Automata Based Artificial Immune System for Strengthening Automated Protein Prediction
Venue: arXiv cs.AI 2013
Year: 2013

Artificial Immune System (AIS-MACA) a novel computational intelligence technique is can be used for strengthening the automated protein prediction system with more adaptability and incorporating more parallelism to the system. Most of the existing approaches are sequential which will classify the input into four major classes and these are designed for similar sequences. AIS-MACA is designed to identify ten classes from the sequences that share twilight zone similarity and identity with the training sequences with mixed and hybrid variations. This method also predicts three states (helix, strand, and coil) for the secondary structure. Our comprehensive design considers 10 feature selection methods and 4 classifiers to develop MACA (Multiple Attractor Cellular Automata) based classifiers that are build for each of the ten classes. We have tested the proposed classifier with twilight-zone and 1-high-similarity benchmark datasets with over three dozens of modern competing predictors shows that AIS-MACA provides the best overall accuracy that ranges between 80% and 89.8% depending on the dataset.
On Recovering from Run-time Misbehaviour in ADR
Venue: arXiv cs.SE 2013
Year: 2013

We propose a monitoring mechanism for recording the evolution of systems after certain computations, maintaining the history in a tree-like structure. Technically, we develop the monitoring mechanism in a variant of ADR (after Architectural Design Rewriting), a rule-based formal framework for modelling the evolution of architectures of systems. The hierarchical nature of ADR allows us to take full advantage of the tree-like structure of the monitoring mechanism. We exploit this mechanism to formally define new rewriting mechanisms for ADR reconfiguration rules. Also, by monitoring the evolution we propose a way of identifying which part of a system has been affected when unexpected run-time behaviours emerge. Moreover, we propose a methodology to suggest reconfigurations that could potentially lead the system in a non-erroneous state.
Avoiding 2-binomial squares and cubes
Venue: arXiv cs.FL 2013
Year: 2013

Two finite words $u,v$ are 2-binomially equivalent if, for all words $x$ of length at most 2, the number of occurrences of $x$ as a (scattered) subword of $u$ is equal to the number of occurrences of $x$ in $v$. This notion is a refinement of the usual abelian equivalence. A 2-binomial square is a word $uv$ where $u$ and $v$ are 2-binomially equivalent. In this paper, considering pure morphic words, we prove that 2-binomial squares (resp. cubes) are avoidable over a 3-letter (resp. 2-letter) alphabet. The sizes of the alphabets are optimal.
Fine-grained Categorization -- Short Summary of our Entry for the ImageNet Challenge 2012
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we tackle the problem of visual categorization of dog breeds, which is a surprisingly challenging task due to simultaneously present low interclass distances and high intra-class variances. Our approach combines several techniques well known in our community but often not utilized for fine-grained recognition: (1) automatic segmentation, (2) efficient part detection, and (3) combination of multiple features. In particular, we demonstrate that a simple head detector embedded in an off-the-shelf recognition pipeline can improve recognition accuracy quite significantly, highlighting the importance of part features for fine-grained recognition tasks. Using our approach, we achieved a 24.59% mean average precision performance on the Stanford dog dataset.
IntelligentWeb Agent for Search Engines
Venue: arXiv cs.IR 2013
Year: 2013

In this paper we review studies of the growth of the Internet and technologies that are useful for information search and retrieval on the Web. Search engines are retrieve the efficient information. We collected data on the Internet from several different sources, e.g., current as well as projected number of users, hosts, and Web sites. The trends cited by the sources are consistent and point to exponential growth in the past and in the coming decade. Hence it is not surprising that about 85% of Internet users surveyed claim using search engines and search services to find specific information and users are not satisfied with the performance of the current generation of search engines; the slow retrieval speed, communication delays, and poor quality of retrieved results. Web agents, programs acting autonomously on some task, are already present in the form of spiders, crawler, and robots. Agents offer substantial benefits and hazards, and because of this, their development must involve attention to technical details. This paper illustrates the different types of agents,crawlers, robots,etc for mining the contents of web in a methodical, automated manner, also discusses the use of crawler to gather specific types of information from Web pages, such as harvesting e-mail addresses
Implementing Computations in Automaton (Semi)groups
Venue: arXiv cs.FL 2013
Year: 2013

We consider the growth, order, and finiteness problems for automaton (semi)groups. We propose new implementations and compare them with the existing ones. As a result of extensive experimentations, we propose some conjectures on the order of finite automaton (semi)groups.
The Optimal Division of the Energy Market into Zones: Comparison of Two Methodologies under Variable Wind Conditions
Venue: arXiv cs.CE 2013
Year: 2013

We compare two competing methodologies of market zones identification under the criterion of social welfare maximization: (i) consensus clustering of Locational Marginal Prices over different wind scenarios and (ii) congestion contribution identification with congested lines identified across variable wind generation outputs. We test the division of market into zones based on each of the two methodologies using a welfare criterion, i.e., comparing the cost of supplying energy on uniform market (including readjustments made on a balancing market to overcome the congestion) with cost on k-zone market. A division which maximizes the welfare is considered as the optimum.
A Joint Uplink/Downlink Opportunistic Scheduling Scheme for Infrastructure WLANs
Venue: arXiv cs.NI 2013
Year: 2013

We propose a combined uplink/downlink opportunistic scheduling algorithm for infrastructure WLANs. In the presence of both uplink and downlink flows, an infrastructure WLAN suffers from the uplink/downlink unfairness problem which severely decreases the throughput of the access point (AP). We resolve the unfairness by maintaining a separate queue and a backoff timer for each associated mobile station (STA) at the AP. We also increase the system throughput by making the backoff time a function of the channel gains. This reduces the collision probability also. We theoretically analyze the performance of the system under symmetric statistics for all users and validate the analysis by extensive simulations. Simulation results show increase in system throughput by over 40% compared to the 802.11 MAC.
Generalized Extended Hamming Codes over Galois Ring of Characteristic $2^{n}$
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we introduce generalized extended Hamming codes over Galois rings $GR(2^n,m)$ of characteristic $2^n$ with extension degree $m$. Furthermore we prove that the minimum Hamming weight of generalized extended Hamming codes over $GR(2^n,m)$ is 4 and the minimum Lee weight of generalized extended Hamming codes over $GR(8,m)$ is 6 for all $m \geq 3$.
Graph-Based Approaches to Clustering Network-Constrained Trajectory Data
Venue: arXiv cs.LG 2013
Year: 2013

Clustering trajectory data attracted considerable attention in the last few years. Most of prior work assumed that moving objects can move freely in an euclidean space and did not consider the eventual presence of an underlying road network and its influence on evaluating the similarity between trajectories. In this paper, we present an approach to clustering such network-constrained trajectory data. More precisely we aim at discovering groups of road segments that are often travelled by the same trajectories. To achieve this end, we model the interactions between segments w.r.t. their similarity as a weighted graph to which we apply a community detection algorithm to discover meaningful clusters. We showcase our proposition through experimental results obtained on synthetic datasets.
Balanced Allocations: A Simple Proof for the Heavily Loaded Case
Venue: arXiv cs.DM 2013
Year: 2013

We provide a relatively simple proof that the expected gap between the maximum load and the average load in the two choice process is bounded by $(1+o(1))\log \log n$, irrespective of the number of balls thrown. The theorem was first proven by Berenbrink et al. Their proof uses heavy machinery from Markov-Chain theory and some of the calculations are done using computers. In this manuscript we provide a significantly simpler proof that is not aided by computers and is self contained. The simplification comes at a cost of weaker bounds on the low order terms and a weaker tail bound for the probability of deviating from the expectation.
Hypermap-Homology Quantum Codes (Ph.D. thesis)
Venue: arXiv cs.IT 2013
Year: 2013

We introduce a new type of sparse CSS quantum error correcting code based on the homology of hypermaps. Sparse quantum error correcting codes are of interest in the building of quantum computers due to their ease of implementation and the possibility of developing fast decoders for them. Codes based on the homology of embeddings of graphs, such as Kitaev's toric code, have been discussed widely in the literature and our class of codes generalize these. We use embedded hypergraphs, which are a generalization of graphs that can have edges connected to more than two vertices. We develop theorems and examples of our hypermap-homology codes, especially in the case that we choose a special type of basis in our homology chain complex. In particular the most straightforward generalization of the $m \times m$ toric code to hypermap-homology codes gives us a $[(3/2)m^2,2,m]$ code as compared to the toric code which is a $[2m^2,2,m]$ code. Thus we can protect the same amount of quantum information, with the same error-correcting capability, using less physical qubits.
Digital Circuits Implementation On Rpga Simulator
Venue: arXiv cs.ET 2013
Year: 2013

For Reversible computing, Target technology is yet to become available. Adequate tools are not yet developed for reversible technology. Simulation is still under development. Classical logic synthesis methods and simulation tools can not be used in reversible computing. Because these work on irreversible logic blocks but in reversible computing reversible logic blocks are used for design and implementation. So, we need a simulation platform to analysis and development in this area. So, we worked on this area and developed a GUI based simulator. In the Dissertation work, we undertook simulation of RPGA, reversible alternative to FPGA. We developed a RPGA simulator in our project. RPGA simulator combines the technology of PLD/FPGA/SYSTOLIC array. Our RPGA simulator, implements a given symmetric reversible Circuit on a RPGA structure. We also worked on RPGA structure gates (picton and kerntopf gates) to develop a better RPGA structure. Stepwise execution on RPGA structure is also performed in RPGA simulator. We also designed new algorithms for Truth Table generation and symmetry analysis. The dissertation work aims to develop entire simulator is GUI based and easy to learn that makes it user friendly. User can easily view all simulation results in GUI of our RPGA simulator.
Parameterized Algorithms for Finding Square Roots
Venue: arXiv cs.DS 2013
Year: 2013

We show that the following two problems are fixed-parameter tractable with parameter k: testing whether a connected n-vertex graph with m edges has a square root with at most n-1+k edges and testing whether such a graph has a square root with at least m-k edges. Our first result implies that squares of graphs obtained from trees by adding at most k edges can be recognized in polynomial time for every fixed k>=0; previously this result was known only for k=0. Our second result is equivalent to stating that deciding whether a graph can be modified into a square root of itself by at most k edge deletions is fixed-parameter tractable with parameter k.
Towards Application of the RBNK Model
Venue: arXiv cs.CE 2013
Year: 2013

The computational modeling of genetic regulatory networks is now common place, either by fitting a system to experimental data or by exploring the behaviour of abstract systems with the aim of identifying underlying principles. This paper presents an approach to the latter, considering the response to environmental changes of a well-known model placed upon tunable fitness landscapes. The effects on genome size and gene connectivity are explored.
A class of generalized additive Runge-Kutta methods
Venue: arXiv cs.NA 2013
Year: 2013

This work generalizes the additively partitioned Runge-Kutta methods by allowing for different stage values as arguments of different components of the right hand side. An order conditions theory is developed for the new family of generalized additive methods, and stability and monotonicity investigations are carried out. The paper discusses the construction and properties of implicit-explicit and implicit-implicit,methods in the new framework. The new family, named GARK, introduces additional flexibility when compared to traditional partitioned Runge-Kutta methods, and therefore offers additional opportunities for the development of flexible solvers for systems with multiple scales, or driven by multiple physical processes.
Uncoupled Learning Rules for Seeking Equilibria in Repeated Plays: An Overview
Venue: arXiv cs.GT 2013
Year: 2013

In this note, we consider repeated play of a finite game using learning rules whose period-by-period behavior probabilities or empirical distributions converge to some notion of equilibria of the stage game. Our primary focus is on uncoupled and completely uncoupled learning rules. While the former relies on players being aware of only their own payoff functions and able to monitor the action taken by the others, the latter assumes that players only know their own past realized payoffs. We highlight the border between possible and impossible results using these rules. We also overview several uncoupled and completely uncoupled learning rules, most of which leverage notions of regret as the solution concept to seek payoff-improving action profiles.
Multivalued Logic Circuit Design for Binary Logic Interface
Venue: arXiv cs.OH 2013
Year: 2013

Binary logic and devices have been in used since inception with advancement and technology and millennium gate design era. The development in binary logic has become tedious and cumbersome. Multivalued logic enables significant more information to be packed within a single digit. The design and development of logic circuit becomes very compact and easier. Attempts are being made to fabricate multivalued logic based devices. Since present devices can be implemented only in binary system,it is necessary to evolve a system that can built the circuit in multivalued logic system and convert in binary logic system. In multivalued logic system logic gates differ in different logic system, a quaternary has become mature in terms of logic algebra and gates. Hence logic design based on above system can be done using standard procedure. In this dissertation a logic circuit design entry based on multivalued logic system has been taken up that can provide the ease of circuit design in multivalued system and output as binary valued circuit. The named "MVL-DEV" offers editing, storage and conversion into binary facility.
Trading inference effort versus size in CNF Knowledge Compilation
Venue: arXiv cs.CC 2013
Year: 2013

Knowledge Compilation (KC) studies compilation of boolean functions f into some formalism F, which allows to answer all queries of a certain kind in polynomial time. Due to its relevance for SAT solving, we concentrate on the query type "clausal entailment" (CE), i.e., whether a clause C follows from f or not, and we consider subclasses of CNF, i.e., clause-sets F with special properties. In this report we do not allow auxiliary variables (except of the Outlook), and thus F needs to be equivalent to f. We consider the hierarchies UC_k <= WC_k, which were introduced by the authors in 2012. Each level allows CE queries. The first two levels are well-known classes for KC. Namely UC_0 = WC_0 is the same as PI as studied in KC, that is, f is represented by the set of all prime implicates, while UC_1 = WC_1 is the same as UC, the class of unit-refutation complete clause-sets introduced by del Val 1994. We show that for each k there are (sequences of) boolean functions with polysize representations in UC_{k+1}, but with an exponential lower bound on representations in WC_k. Such a separation was previously only know for k=0. We also consider PC < UC, the class of propagation-complete clause-sets. We show that there are (sequences of) boolean functions with polysize representations in UC, while there is an exponential lower bound for representations in PC. These separations are steps towards a general conjecture determining the representation power of the hierarchies PC_k < UC_k <= WC_k. The strong form of this conjecture also allows auxiliary variables, as discussed in depth in the Outlook.
RANSAC: Identification of Higher-Order Geometric Features and Applications in Humanoid Robot Soccer
Venue: arXiv cs.RO 2013
Year: 2013

The ability for an autonomous agent to self-localise is directly proportional to the accuracy and precision with which it can perceive salient features within its local environment. The identification of such features by recognising geometric profile allows robustness against lighting variations, which is necessary in most industrial robotics applications. This paper details a framework by which the random sample consensus (RANSAC) algorithm, often applied to parameter fitting in linear models, can be extended to identify higher-order geometric features. Goalpost identification within humanoid robot soccer is investigated as an application, with the developed system yielding an order-of-magnitude improvement in classification performance relative to a traditional histogramming methodology.