OpenRaiser/Intern-Atlas huggingface dataset:
Merging Multiparty Protocols in Multiparty Choreographies
Venue: arXiv cs.PL 2013
Year: 2013

Choreography-based programming is a powerful paradigm for defining communication-based systems from a global viewpoint. A choreography can be checked against multiparty protocol specifications, given as behavioural types, that may be instantiated indefinitely at runtime. Each protocol instance is started with a synchronisation among the involved peers. We analyse a simple transformation from a choreography with a possibly unbounded number of protocol instantiations to a choreography instantiating a single protocol, which is the merge of the original ones. This gives an effective methodology for obtaining new protocols by composing existing ones. Moreover, by removing all synchronisations required for starting protocol instances, our transformation reduces the number of communications and resources needed to execute a choreography.
Term Graph Representations for Cyclic Lambda-Terms
Venue: arXiv cs.LO 2013
Year: 2013

We study various representations for cyclic lambda-terms as higher-order or as first-order term graphs. We focus on the relation between 'lambda-higher-order term graphs' (lambda-ho-term-graphs), which are first-order term graphs endowed with a well-behaved scope function, and their representations as 'lambda-term-graphs', which are plain first-order term graphs with scope-delimiter vertices that meet certain scoping requirements. Specifically we tackle the question: Which class of first-order term graphs admits a faithful embedding of lambda-ho-term-graphs in the sense that (i) the homomorphism-based sharing-order on lambda-ho-term-graphs is preserved and reflected, and (ii) the image of the embedding corresponds closely to a natural class (of lambda-term-graphs) that is closed under homomorphism? We systematically examine whether a number of classes of lambda-term-graphs have this property, and we find a particular class of lambda-term-graphs that satisfies this criterion. Term graphs of this class are built from application, abstraction, variable, and scope-delimiter vertices, and have the characteristic feature that the latter two kinds of vertices have back-links to the corresponding abstraction. This result puts a handle on the concept of subterm sharing for higher-order term graphs, both theoretically and algorithmically: We obtain an easily implementable method for obtaining the maximally shared form of lambda-ho-term-graphs. Furthermore, we open up the possibility to pull back properties from first-order term graphs to lambda-ho-term-graphs, properties such as the complete lattice structure of bisimulation equivalence classes with respect to the sharing order.
A Fuzzy Logic based Method for Efficient Retrieval of Vague and Uncertain Spatial Expressions in Text Exploiting the Granulation of the Spatial Event Queries
Venue: arXiv cs.IR 2013
Year: 2013

The arrangement of things in n-dimensional space is specified as Spatial. Spatial data consists of values that denote the location and shape of objects and areas on the earths surface. Spatial information includes facts such as location of features, the relationship of geographic features and measurements of geographic features. The spatial cognition is a primal area of study in various other fields such as Robotics, Psychology, Geosciences, Geography, Political Sciences, Geographic Economy, Environmental, Mining and Petroleum Engineering, Natural Resources, Epidemiology, Demography etc., Any text document which contains physical location specifications such as place names, geographic coordinates, landmarks, country names etc., are supposed to contain the spatial information. The spatial information may also be represented using vague or fuzzy descriptions involving linguistic terms such as near to, far from, to the east of, very close. Given a query involving events, the aim of this ongoing research work is to extract the relevant information from multiple text documents, resolve the uncertainty and vagueness and translate them in to locations in a map. The input to the system would be a text Corpus and a Spatial Query event. The output of the system is a map showing the most possible, disambiguated location of the event queried. The author proposes Fuzzy Logic Techniques for resolving the uncertainty in the spatial expressions.
An Improvement to Levenshtein's Upper Bound on the Cardinality of Deletion Correcting Codes
Venue: arXiv cs.IT 2013
Year: 2013

We consider deletion correcting codes over a q-ary alphabet. It is well known that any code capable of correcting s deletions can also correct any combination of s total insertions and deletions. To obtain asymptotic upper bounds on code size, we apply a packing argument to channels that perform different mixtures of insertions and deletions. Even though the set of codes is identical for all of these channels, the bounds that we obtain vary. Prior to this work, only the bounds corresponding to the all insertion case and the all deletion case were known. We recover these as special cases. The bound from the all deletion case, due to Levenshtein, has been the best known for more than forty five years. Our generalized bound is better than Levenshtein's bound whenever the number of deletions to be corrected is larger than the alphabet size.
Combining Multiple Time Series Models Through A Robust Weighted Mechanism
Venue: arXiv cs.AI 2013
Year: 2013

Improvement of time series forecasting accuracy through combining multiple models is an important as well as a dynamic area of research. As a result, various forecasts combination methods have been developed in literature. However, most of them are based on simple linear ensemble strategies and hence ignore the possible relationships between two or more participating models. In this paper, we propose a robust weighted nonlinear ensemble technique which considers the individual forecasts from different models as well as the correlations among them while combining. The proposed ensemble is constructed using three well-known forecasting models and is tested for three real-world time series. A comparison is made among the proposed scheme and three other widely used linear combination methods, in terms of the obtained forecast errors. This comparison shows that our ensemble scheme provides significantly lower forecast errors than each individual model as well as each of the four linear combination methods.
Decentralized set-valued state estimation based on non-deterministic chains
Venue: arXiv cs.SY 2013
Year: 2013

A general decentralized computational framework for set-valued state estimation and prediction for the class of systems that accept a hybrid state machine representation is considered in this article. The decentralized scheme consists of a conjunction of distributed state machines that are specified by a decomposition of the external signal space. While this is shown to produce, in general, outer approximations of the outcomes of the original monolithic state machine, here, specific rules for the signal space decomposition are devised by utilizing structural properties of the underyling transition relation, leading to a recovery of the exact state set results. By applying a suitable approximation algorithm, we show that computational complexity in the decentralized setting may thereby essentially reduce as compared to the centralized estimation scheme.
Categorizing Bugs with Social Networks: A Case Study on Four Open Source Software Communities
Venue: arXiv cs.SE 2013
Year: 2013

Efficient bug triaging procedures are an important precondition for successful collaborative software engineering projects. Triaging bugs can become a laborious task particularly in open source software (OSS) projects with a large base of comparably inexperienced part-time contributors. In this paper, we propose an efficient and practical method to identify valid bug reports which a) refer to an actual software bug, b) are not duplicates and c) contain enough information to be processed right away. Our classification is based on nine measures to quantify the social embeddedness of bug reporters in the collaboration network. We demonstrate its applicability in a case study, using a comprehensive data set of more than 700,000 bug reports obtained from the Bugzilla installation of four major OSS communities, for a period of more than ten years. For those projects that exhibit the lowest fraction of valid bug reports, we find that the bug reporters' position in the collaboration network is a strong indicator for the quality of bug reports. Based on this finding, we develop an automated classification scheme that can easily be integrated into bug tracking platforms and analyze its performance in the considered OSS communities. A support vector machine (SVM) to identify valid bug reports based on the nine measures yields a precision of up to 90.3% with an associated recall of 38.9%. With this, we significantly improve the results obtained in previous case studies for an automated early identification of bugs that are eventually fixed. Furthermore, our study highlights the potential of using quantitative measures of social organization in collaborative software engineering. It also opens a broad perspective for the integration of social awareness in the design of support infrastructures.
Ending-based Strategies for Part-of-speech Tagging
Venue: arXiv cs.CL 2013
Year: 2013

Probabilistic approaches to part-of-speech tagging rely primarily on whole-word statistics about word/tag combinations as well as contextual information. But experience shows about 4 per cent of tokens encountered in test sets are unknown even when the training set is as large as a million words. Unseen words are tagged using secondary strategies that exploit word features such as endings, capitalizations and punctuation marks. In this work, word-ending statistics are primary and whole-word statistics are secondary. First, a tagger was trained and tested on word endings only. Subsequent experiments added back whole-word statistics for the words occurring most frequently in the training set. As grew larger, performance was expected to improve, in the limit performing the same as word-based taggers. Surprisingly, the ending-based tagger initially performed nearly as well as the word-based tagger; in the best case, its performance significantly exceeded that of the word-based tagger. Lastly, and unexpectedly, an effect of negative returns was observed - as grew larger, performance generally improved and then declined. By varying factors such as ending length and tag-list strategy, we achieved a success rate of 97.5 percent.
An Evaluation of an Algorithm for Inductive Learning of Bayesian Belief Networks Usin
Venue: arXiv cs.AI 2013
Year: 2013

Bayesian learning of belief networks (BLN) is a method for automatically constructing belief networks (BNs) from data using search and Bayesian scoring techniques. K2 is a particular instantiation of the method that implements a greedy search strategy. To evaluate the accuracy of K2, we randomly generated a number of BNs and for each of those we simulated data sets. K2 was then used to induce the generating BNs from the simulated data. We examine the performance of the program, and the factors that influence it. We also present a simple BN model, developed from our results, which predicts the accuracy of K2, when given various characteristics of the data set.
Planning with External Events
Venue: arXiv cs.AI 2013
Year: 2013

I describe a planning methodology for domains with uncertainty in the form of external events that are not completely predictable. The events are represented by enabling conditions and probabilities of occurrence. The planner is goal-directed and backward chaining, but the subgoals are suggested by analyzing the probability of success of the partial plan rather than being simply the open conditions of the operators in the plan. The partial plan is represented as a Bayesian belief net to compute its probability of success. Since calculating the probability of success of a plan can be very expensive I introduce two other techniques for computing it, one that uses Monte Carlo simulation to estimate it and one based on a Markov chain representation that uses knowledge about the dependencies between the predicates describing the domain.
An Ordinal View of Independence with Application to Plausible Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

An ordinal view of independence is studied in the framework of possibility theory. We investigate three possible definitions of dependence, of increasing strength. One of them is the counterpart to the multiplication law in probability theory, and the two others are based on the notion of conditional possibility. These two have enough expressive power to support the whole possibility theory, and a complete axiomatization is provided for the strongest one. Moreover we show that weak independence is well-suited to the problems of belief change and plausible reasoning, especially to address the problem of blocking of property inheritance in exception-tolerant taxonomic reasoning.
On Testing Whether an Embedded Bayesian Network Represents a Probability Model
Venue: arXiv cs.AI 2013
Year: 2013

Testing the validity of probabilistic models containing unmeasured (hidden) variables is shown to be a hard task. We show that the task of testing whether models are structurally incompatible with the data at hand, requires an exponential number of independence evaluations, each of the form: "X is conditionally independent of Y, given Z." In contrast, a linear number of such evaluations is required to test a standard Bayesian network (one per vertex). On the positive side, we show that if a network with hidden variables G has a tree skeleton, checking whether G represents a given probability model P requires the polynomial number of such independence evaluations. Moreover, we provide an algorithm that efficiently constructs a tree-structured Bayesian network (with hidden variables) that represents P if such a network exists, and further recognizes when such a network does not exist.
Operator Selection While Planning Under Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes the best first search strategy used by U-Plan (Mansell 1993a), a planning system that constructs quantitatively ranked plans given an incomplete description of an uncertain environment. U-Plan uses uncertain and incomplete evidence de scribing the environment, characterizes it using a Dempster-Shafer interval, and generates a set of possible world states. Plan construction takes place in an abstraction hierarchy where strategic decisions are made before tactical decisions. Search through this abstraction hierarchy is guided by a quantitative measure (expected fulfillment) based on decision theory. The search strategy is best first with the provision to update expected fulfillment and review previous decisions in the light of planning developments. U-Plan generates multiple plans for multiple possible worlds, and attempts to use existing plans for new world situations. A super-plan is then constructed, based on merging the set of plans and appropriately timed knowledge acquisition operators, which are used to decide between plan alternatives during plan execution.
A Probabilistic Calculus of Actions
Venue: arXiv cs.AI 2013
Year: 2013

We present a symbolic machinery that admits both probabilistic and causal information about a given domain and produces probabilistic statements about the effect of actions and the impact of observations. The calculus admits two types of conditioning operators: ordinary Bayes conditioning, P(y|X = x), which represents the observation X = x, and causal conditioning, P(y|do(X = x)), read the probability of Y = y conditioned on holding X constant (at x) by deliberate action. Given a mixture of such observational and causal sentences, together with the topology of the causal graph, the calculus derives new conditional probabilities of both types, thus enabling one to quantify the effects of actions (and policies) from partially specified knowledge bases, such as Bayesian networks in which some conditional probabilities may not be available.
Belief Induced by the Partial Knowledge of the Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

We construct the belief function that quantifies the agent, beliefs about which event of Q will occurred when he knows that the event is selected by a chance set-up and that the probability function associated to the chance set up is only partially known.
Maximizing Acceptance Probability for Active Friending in On-Line Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

Friending recommendation has successfully contributed to the explosive growth of on-line social networks. Most friending recommendation services today aim to support passive friending, where a user passively selects friending targets from the recommended candidates. In this paper, we advocate recommendation support for active friending, where a user actively specifies a friending target. To the best of our knowledge, a recommendation designed to provide guidance for a user to systematically approach his friending target, has not been explored in existing on-line social networking services. To maximize the probability that the friending target would accept an invitation from the user, we formulate a new optimization problem, namely, \emph{Acceptance Probability Maximization (APM)}, and develop a polynomial time algorithm, called \emph{Selective Invitation with Tree and In-Node Aggregation (SITINA)}, to find the optimal solution. We implement an active friending service with SITINA in Facebook to validate our idea. Our user study and experimental results manifest that SITINA outperforms manual selection and the baseline approach in solution quality efficiently.
Interference-Based Cell Selection in Heterogenous Networks
Venue: arXiv cs.NI 2013
Year: 2013

Heterogeneous cellular networks provide significant improvements in terms of increased data rates and cell coverage, and offer reduced user rate starvation. However, there are important problems to be solved. In this paper, we identify that the cell selection criterion is an important factor determining the user rates especially in the uplink transmissions and apply cell breathing to determine the user and base station assignments. We observe that the proposed interference-based cell selection algorithm provides better load balancing among the base stations in the system to improve the uplink user rates. We present the implementation steps in a typical LTE network and demonstrate the performance improvements through simulations.
Using Artificial Intelligence Models in System Identification
Venue: arXiv cs.NE 2013
Year: 2013

Artificial Intelligence (AI) techniques are known for its ability in tackling problems found to be unyielding to traditional mathematical methods. A recent addition to these techniques are the Computational Intelligence (CI) techniques which, in most cases, are nature or biologically inspired techniques. Different CI techniques found their way to many control engineering applications, including system identification, and the results obtained by many researchers were encouraging. However, most control engineers and researchers used the basic CI models as is or slightly modified them to match their needs. Henceforth, the merits of one model over the other was not clear, and full potential of these models was not exploited. In this research, Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) methods, which are different CI techniques, are modified to best suit the multimodal problem of system identification. In the first case of GA, an extension to the basic algorithm, which is inspired from nature as well, was deployed by introducing redundant genetic material. This extension, which come in handy in living organisms, did not result in significant performance improvement to the basic algorithm. In the second case, the Clubs-based PSO (C-PSO) dynamic neighborhood structure was introduced to replace the basic static structure used in canonical PSO algorithms. This modification of the neighborhood structure resulted in significant performance of the algorithm regarding convergence speed, and equipped it with a tool to handle multimodal problems. To understand the suitability of different GA and PSO techniques in the problem of system identification, they were used in an induction motor's parameter identification problem. The results enforced previous conclusions and showed the superiority of PSO in general over the GA in such a multimodal problem.
Order effects in dynamic semantics
Venue: arXiv cs.LO 2013
Year: 2013

In their target article, \citet{WangBusemeyer13} [A quantum question order model supported by empirical tests of an a priori and precise prediction. \emph{Topics in Cognitive Science}] discuss question order effects in terms of incompatible projectors on a Hilbert space. In a similar vein, Blutner recently presented an orthoalgebraic query language essentially relying on dynamic update semantics. Here, I shall comment on some interesting analogies between the different variants of dynamic semantics and generalized quantum theory to illustrate other kinds of order effects in human cognition, such as belief revision, the resolution of anaphors, and default reasoning that result from the crucial non-commutativity of mental operations upon the belief state of a cognitive agent.
Should ΔΣ Modulators Used in AC Motor Drives be Adapted to the Mechanical Load of the Motor?
Venue: arXiv cs.SY 2013
Year: 2013

We consider the use of ΔΣ modulators in ac motor drives, focusing on the many additional degrees of freedom that this option offers over Pulse Width Modulation (PWM). Following some recent results, we show that it is possible to fully adapt the ΔΣ modulator Noise Transfer Function (NTF) to the rest of the drive chain and that the approach can be pushed even to a fine adaptation of the NTF to the specific motor loading condition. We investigate whether and to what extent the adaptation should be pursued. Using a representative test case and extensive simulation, we conclude that a mild adaptation can be beneficial, leading to Signal to Noise Ratio (SNR) improvements in the order a few dB, while the advantage pushing the adaptation to the load tracking is likely to be minimal.