OpenRaiser/Intern-Atlas huggingface dataset:
Semantics of Interaction
Venue: arXiv cs.LO 2013
Year: 2013

This is an introduction to Game Semantics based on some lecture notes given at the CLiCS II summer school in Cambridge in 1995. We will focus on the recent (1994) work on Game semantics, which has led to some striking advances in the Full Abstraction problem for PCF and other programming languages. Our aim is to give a genuinely elementary first introduction; we therefore present a simplified version of game semantics, which nonetheless contains most of the essential concepts. The more complex game semantics used by Abramsky, Jagadeesan and Malacaria and by Hyland and Ong to construct fully abstract models for PCF can be seen as refinements of what we present. Some background in category theory, type theory and linear logic would be helpful in reading these notes.
On Replacing PID Controller with ANN Controller for DC Motor Position Control
Venue: arXiv cs.SY 2013
Year: 2013

The process industry implements many techniques with certain parameters in its operations to control the working of several actuators on field. Amongst these actuators, DC motor is a very common machine. The angular position of DC motor can be controlled to drive many processes such as the arm of a robot. The most famous and well known controller for such applications is PID controller. It uses proportional, integral and derivative functions to control the input signal before sending it to the plant unit. In this paper, another controller based on Artificial Neural Network (ANN) control is examined to replace the PID controller for controlling the angular position of a DC motor to drive a robot arm. Simulation is performed in MATLAB after training the neural network (supervised learning) and it is shown that results are acceptable and applicable in process industry for reference control applications. The paper also indicates that the ANN controller can be less complicated and less costly to implement in industrial control applications as compared to some other proposed schemes.
Query Segmentation for Relevance Ranking in Web Search
Venue: arXiv cs.IR 2013
Year: 2013

In this paper, we try to answer the question of how to improve the state-of-the-art methods for relevance ranking in web search by query segmentation. Here, by query segmentation it is meant to segment the input query into segments, typically natural language phrases, so that the performance of relevance ranking in search is increased. We propose employing the re-ranking approach in query segmentation, which first employs a generative model to create top $k$ candidates and then employs a discriminative model to re-rank the candidates to obtain the final segmentation result. The method has been widely utilized for structure prediction in natural language processing, but has not been applied to query segmentation, as far as we know. Furthermore, we propose a new method for using the result of query segmentation in relevance ranking, which takes both the original query words and the segmented query phrases as units of query representation. We investigate whether our method can improve three relevance models, namely BM25, key n-gram model, and dependency model. Our experimental results on three large scale web search datasets show that our method can indeed significantly improve relevance ranking in all the three cases.
A Unifying Framework for the Electrical Structure-Based Approach to PMU Placement in Electric Power Systems
Venue: arXiv cs.SY 2013
Year: 2013

The electrical structure of the power grid is utilized to address the phasor measurement unit (PMU) placement problem. First, we derive the connectivity matrix of the network using the resistance distance metric and employ it in the linear program formulation to obtain the optimal number of PMUs, for complete network observability without zero injection measurements. This approach was developed by the author in an earlier work, but the solution methodology to address the location problem did not fully utilize the electrical properties of the network, resulting in an ambiguity. In this paper, we settle this issue by exploiting the coupling structure of the grid derived using the singular value decomposition (SVD)-based analysis of the resistance distance matrix to solve the location problem. Our study, which is based on recent advances in complex networks that promote the electrical structure of the grid over its topological structure and the SVD analysis which throws light on the electrical coupling of the network, results in a unified framework for the electrical structure-based PMU placement. The proposed method is tested on IEEE bus systems, and the results uncover intriguing connections between the singular vectors and average resistance distance between buses in the network.
Solving the Petri-Nets to Statecharts Transformation Case with FunnyQT
Venue: arXiv cs.SE 2013
Year: 2013

FunnyQT is a model querying and model transformation library for the functional Lisp-dialect Clojure providing a rich and efficient querying and transformation API. This paper describes the FunnyQT solution to the TTC 2013 Petri-Nets to Statcharts Transformation Case. This solution has won the best overall solution award and the best efficiency award for this case.
Output sensitive algorithm for covering many points
Venue: arXiv cs.CG 2013
Year: 2013

A set of points and a positive integer $m$ are given and our goal is to cover the maximum number of these point with $m$ disks. We devise the first output sensitive algorithm for this problem. We introduce a parameter $ρ$ as the maximum number of points that one disk can cover. In this paper first we solve the problem for $m=2$ in $O({nρ} + {ρ^3}\log ρ))$ time. The previous algorithm for this problem runs in $O({n^3}\log n)$ time. Our algorithm outperforms the previous algorithm because $ρ$ is much smaller than $n$ in many cases. Then we extend the algorithm for any value of $m$ and we solve the problem in $O(m{nρ} + {(mρ)^{2m - 1}}\log mρ)$ time. The previous algorithm for this problem runs in $O({n^{2m - 1}}\log n)$ time. Our algorithm runs faster than the previous algorithm because $mρ$ is smaller than $n$ in many cases. Our technique to obtain an output sensitive algorithm is to use a greedy algorithm to confine the areas that we should search to obtain the result. Our technique in this paper may be applicable in other set covering problems that deploy a greedy algorithm, to obtain faster solutions.
Comprehensive Border Bases for Zero Dimensional Parametric Polynomial Ideals
Venue: arXiv cs.SC 2013
Year: 2013

In this paper, we extend the idea of comprehensive Gröbner bases given by Weispfenning (1992) to border bases for zero dimensional parametric polynomial ideals. For this, we introduce a notion of comprehensive border bases and border system, and prove their existence even in the cases where they do not correspond to any term order. We further present algorithms to compute comprehensive border bases and border system. Finally, we study the relation between comprehensive Gröbner bases and comprehensive border bases w.r.t. a term order and give an algorithm to compute such comprehensive border bases from comprehensive Gröbner bases.
A Generic Position Based Method for Real Root Isolation of Zero-Dimensional Polynomial Systems
Venue: arXiv cs.SC 2013
Year: 2013

We improve the local generic position method for isolating the real roots of a zero-dimensional bivariate polynomial system with two polynomials and extend the method to general zero-dimensional polynomial systems. The method mainly involves resultant computation and real root isolation of univariate polynomial equations. The roots of the system have a linear univariate representation. The complexity of the method is $\tilde{O}_B(N^{10})$ for the bivariate case, where $N=\max(d,τ)$, $d$ resp., $τ$ is an upper bound on the degree, resp., the maximal coefficient bitsize of the input polynomials. The algorithm is certified with probability 1 in the multivariate case. The implementation shows that the method is efficient, especially for bivariate polynomial systems.
Cache-Oblivious Peeling of Random Hypergraphs
Venue: arXiv cs.DS 2013
Year: 2013

The computation of a peeling order in a randomly generated hypergraph is the most time-consuming step in a number of constructions, such as perfect hashing schemes, random $r$-SAT solvers, error-correcting codes, and approximate set encodings. While there exists a straightforward linear time algorithm, its poor I/O performance makes it impractical for hypergraphs whose size exceeds the available internal memory. We show how to reduce the computation of a peeling order to a small number of sequential scans and sorts, and analyze its I/O complexity in the cache-oblivious model. The resulting algorithm requires $O(\mathrm{sort}(n))$ I/Os and $O(n \log n)$ time to peel a random hypergraph with $n$ edges. We experimentally evaluate the performance of our implementation of this algorithm in a real-world scenario by using the construction of minimal perfect hash functions (MPHF) as our test case: our algorithm builds a MPHF of $7.6$ billion keys in less than $21$ hours on a single machine. The resulting data structure is both more space-efficient and faster than that obtained with the current state-of-the-art MPHF construction for large-scale key sets.
SpeedMachines: Anytime Structured Prediction
Venue: arXiv cs.LG 2013
Year: 2013

Structured prediction plays a central role in machine learning applications from computational biology to computer vision. These models require significantly more computation than unstructured models, and, in many applications, algorithms may need to make predictions within a computational budget or in an anytime fashion. In this work we propose an anytime technique for learning structured prediction that, at training time, incorporates both structural elements and feature computation trade-offs that affect test-time inference. We apply our technique to the challenging problem of scene understanding in computer vision and demonstrate efficient and anytime predictions that gradually improve towards state-of-the-art classification performance as the allotted time increases.
An NMF solution for the Petri Nets to State Charts case study at the TTC 2013
Venue: arXiv cs.SE 2013
Year: 2013

Software systems are getting more and more complex. Model-driven engineering (MDE) offers ways to handle such increased complexity by lifting development to a higher level of abstraction. A key part in MDE are transformations that transform any given model into another. These transformations are used to generate all kinds of software artifacts from models. However, there is little consensus about the transformation tools. Thus, the Transformation Tool Contest (TTC) 2013 aims to compare different transformation engines. This is achieved through three different cases that have to be tackled. One of these cases is the Petri Net to State Chart case. A solution has to transform a Petri Net to a State Chart and has to derive a hierarchical structure within the State Chart. This paper presents the solution for this case using NMF Transformations as transformation engine.
Stream Control Transmission Protocol (SCTP): Robust and Efficient for Data Centre Applications
Venue: arXiv cs.NI 2013
Year: 2013

Due to rapid advancement in modern technology, as one of the major concerns is the stability of business. The organizations depend on their systems to provide robust and faster processing of information for their operations. Efficient data centers are key sources to handle these operations. If the organizational system is not fully functional, the performance of organization may be impaired or clogged completely. With the developments of real-time applications into data centers for data communications, there is a need to use an alternative of the standard TCP protocol to provide reliable data transfer. Stream Control Transmission Protocol (SCTP) consists of several well built-in characteristics that make it capable to work efficiently with real-time applications. In this paper, we evaluate an optimized version of STCP. The optimized version of SCTP is tested against a non optimized version of STCP and TCP in a data center environment. Simulations of the protocols are carried using NS2 simulator
Phase Transitions in Community Detection: A Solvable Toy Model
Venue: arXiv cs.SI 2013
Year: 2013

Recently, it was shown that there is a phase transition in the community detection problem. This transition was first computed using the cavity method, and has been proved rigorously in the case of $q=2$ groups. However, analytic calculations using the cavity method are challenging since they require us to understand probability distributions of messages. We study analogous transitions in so-called "zero-temperature inference" model, where this distribution is supported only on the most-likely messages. Furthermore, whenever several messages are equally likely, we break the tie by choosing among them with equal probability. While the resulting analysis does not give the correct values of the thresholds, it does reproduce some of the qualitative features of the system. It predicts a first-order detectability transition whenever $q > 2$, while the finite-temperature cavity method shows that this is the case only when $q > 4$. It also has a regime analogous to the "hard but detectable" phase, where the community structure can be partially recovered, but only when the initial messages are sufficiently accurate. Finally, we study a semisupervised setting where we are given the correct labels for a fraction $ρ$ of the nodes. For $q > 2$, we find a regime where the accuracy jumps discontinuously at a critical value of $ρ$.
Optimization of zero-delay mappings for distributed coding by deterministic annealing
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the optimization of zero-delay analog mappings in a network setting that involves distributed coding. The cost surface is known to be non-convex, and known greedy methods tend to get trapped in poor locally optimal solutions that depend heavily on initialization. We derive an optimization algorithm based on the principles of "deterministic annealing", a powerful global optimization framework that has been successfully employed in several disciplines, including, in our recent work, to a simple zero-delay analog communications problem. We demonstrate strict superiority over the descent based methods, as well as present example mappings whose properties lend insights on the workings of the solution and relations with digital distributed coding.
Adaptive Intelligent Controller for Household Cooling Systems
Venue: arXiv cs.CY 2013
Year: 2013

This paper presents a household cooling system controller which is adaptive and intelligent in nature. It is able to control the speed of a household cooling fan or an air conditioner based on the real time data namely room temperature, humidity and time i.e. duration, which are collected from environment. To control the speed in an adaptive and intelligent manner an associative memory neural network has been used. This embedded system is able to learn from training set i.e. the user can teach the system about his/her feelings through training data sets. When the system starts up it allows the fan to run freely i.e. at full speed and after certain interval it takes the environmental parameters like room temperature, humidity and time i.e. duration, as an input and after that system takes the decision and controls the speed of the fan.
Round-The-Clock Urine Sugar Monitoring System for Diabetic Patients
Venue: arXiv cs.CY 2013
Year: 2013

It is known that diabetes can not be cured completely, but it can be controlled. The objective of this work is to provide an automatic system that will be able to help the diabetic patient to control the blood sugar. This system measures the blood sugar level of the people from their urine round-the-clock. A recorded message based on this input may be displayed so that apart from patient himself others can be informed about his/her present sugar level. That should help him/her in taking medicine; controlling diet etc. This work is an application of image processing and fuzzy logic. It is known that Benedict's reagent changes its colour based on the sugar level. This colour change information is sensed by the transducer and fed to the fuzzy logic unit for decision making.
MPWide: a light-weight library for efficient message passing over wide area networks
Venue: arXiv cs.DC 2013
Year: 2013

We present MPWide, a light weight communication library which allows efficient message passing over a distributed network. MPWide has been designed to connect application running on distributed (super)computing resources, and to maximize the communication performance on wide area networks for those without administrative privileges. It can be used to provide message-passing between application, move files, and make very fast connections in client-server environments. MPWide has already been applied to enable distributed cosmological simulations across up to four supercomputers on two continents, and to couple two different bloodflow simulations to form a multiscale simulation.
Evolution of Communities with Focus on Stability
Venue: arXiv cs.SI 2013
Year: 2013

Community detection is an important tool for analyzing the social graph of mobile phone users. The problem of finding communities in static graphs has been widely studied. However, since mobile social networks evolve over time, static graph algorithms are not sufficient. To be useful in practice (e.g. when used by a telecom analyst), the stability of the partitions becomes critical. We tackle this particular use case in this paper: tracking evolution of communities in dynamic scenarios with focus on stability. We propose two modifications to a widely used static community detection algorithm: we introduce fixed nodes and preferential attachment to pre-existing communities. We then describe experiments to study the stability and quality of the resulting partitions on real-world social networks, represented by monthly call graphs for millions of subscribers.
A Deployment Process for Strategic Measurement Systems
Venue: arXiv cs.SE 2013
Year: 2013

Explicitly linking software-related activities to an organisation's higher-level goals has been shown to be critical for organizational success. GQM+Strategies provides mechanisms for explicitly linking goals and strategies, based on goal-oriented strategic measurement systems. Deploying such strategic measurement systems in an organization is highly challenging. Experience has shown that a clear deployment strategy is needed for achieving sustainable success. In particular, an adequate deployment process as well as corresponding tool support can facilitate the deployment. This paper introduces the systematical GQM+Strategies deployment process and gives an overview of GQM+Strategies modelling and associated tool support. Additionally, it provides an overview of industrial applications and describes success factors and benefits for the usage of GQM+Strategies.
Adapting Software Quality Models: Practical Challenges, Approach, and First Empirical Results
Venue: arXiv cs.SE 2013
Year: 2013

Measuring and evaluating software quality has become a fundamental task. Many models have been proposed to support stakeholders in dealing with software quality. However, in most cases, quality models do not fit perfectly for the target application context. Since approaches for efficiently adapting quality models are largely missing, many quality models in practice are built from scratch or reuse only high-level concepts of existing models. We present a tool-supported approach for the efficient adaptation of quality models. An initial empirical investigation indicates that the quality models obtained applying the proposed approach are considerably more consistently and appropriately adapted than those obtained following an ad-hoc approach. Further, we could observe that model adaptation is significantly more efficient (~factor 8) when using this approach.
Using Early Quality Assurance Metrics to Focus Testing Activities
Venue: arXiv cs.SE 2013
Year: 2013

Testing of software or software-based systems and services is considered as one of the most effort-consuming activities in the lifecycle. This applies especially to those domains where highly iterative development and continuous integration cannot be applied. Several approaches have been proposed to use measurement as a means to improve test effectiveness and efficiency. Most of them rely on using product data, historical data, or in-process data that is not related to quality assurance ac- tivities. Very few approaches use data from early quality assurance activities such as inspection data in order to focus testing activities and thereby reduce test effort. This article gives an overview of potential benefits of using data from early defect detection activities, potentially in addition to other data, in order to focus testing activities. In addition, the article sketches an integrated inspection and testing process and its evaluation in the context of two case studies. Taking the study limitations into account, the results show an overall reduction of testing effort by up to 34%, which mirrors an efficiency improvement of up to about 50% for testing.
Unconventional research in USSR and Russia: short overview
Venue: arXiv cs.OH 2013
Year: 2013

This work briefly surveys unconventional research in Russia from the end of the 19th until the beginning of the 21th centuries in areas related to generation and detection of a 'high-penetrating' emission of non-biological origin. The overview is based on open scientific and journalistic materials. The unique character of this research and its history, originating from governmental programs of the USSR, is shown. Relations to modern studies on biological effects of weak electromagnetic emission, several areas of bioinformatics and theories of physical vacuum are discussed.
Yao's millionaires' problem and decoy-based public key encryption by classical physics
Venue: arXiv cs.CR 2013
Year: 2013

We use various laws of classical physics to offer several solutions of Yao's millionaires' problem without using any one-way functions. We also describe several informationally secure public key encryption protocols, i.e., protocols secure against passive computationally unbounded adversary. This introduces a new paradigm of decoy-based cryptography, as opposed to "traditional" complexity-based cryptography. In particular, our protocols do not employ any one-way functions.
Circular-arc hypergraphs: Rigidity via Connectedness
Venue: arXiv cs.DM 2013
Year: 2013

A circular-arc hypergraph $H$ is a hypergraph admitting an arc ordering, that is, a circular ordering of the vertex set $V(H)$ such that every hyperedge is an arc of consecutive vertices. An arc ordering is tight if, for any two hyperedges $A$ and $B$ such that $A$ is a nonempty subset of $B$ and $B$ is not equal to $V(H)$, the corresponding arcs share a common endpoint. We give sufficient conditions for $H$ to have, up to reversing, a unique arc ordering and a unique tight arc ordering. These conditions are stated in terms of connectedness properties of $H$. It is known that $G$ is a proper circular-arc graph exactly when its closed neighborhood hypergraph $N[G]$ admits a tight arc ordering. We explore connectedness properties of $N[G]$ and prove that, if $G$ is a connected, twin-free, proper circular-arc graph with non-bipartite complement, then $N[G]$ has, up to reversing, a unique arc ordering. If the complement of $G$ is bipartite and connected, then $N[G]$ has, up to reversing, two tight arc orderings. As a corollary, we notice that in both of the two cases $G$ has an essentially unique intersection representation. The last result also follows from the work by Deng, Hell, and Huang based on a theory of local tournaments.