OpenRaiser/Intern-Atlas huggingface dataset:
Quantum, Stochastic, and Pseudo Stochastic Languages with Few States
Venue: arXiv cs.FL 2014
Year: 2014

Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all these numbers of states are optimal. After this, we completely characterize the class of languages recognized by 1-state GFAs, which is the only nontrivial class of languages recognized by 1-state automata. Finally, we consider the variations of PFAs, QFAs, and GFAs based on the notion of inclusive/exclusive cutpoint, and present some results on their expressive power.
Review of MANETS Using Distributed Public-key Cryptography
Venue: arXiv cs.NI 2014
Year: 2014

Ensuring security is something that is not easily done as many of the demands of network security conflict with the demands of mobile networks, majorly because of the nature of the mobile devices (e.g. low power consumption, low processing load). The study of secure distributed key agreement has great theoretical and practical significance. Securing Mobile Ad-hoc Networks using Distributed Public-key Cryptography in pairing with Mobile Ad hoc Networks and various protocols are essential for secure communications in open and distributed environment.
Natural User Interfaces: Trend in Virtual Interaction
Venue: arXiv cs.HC 2014
Year: 2014

Based on the fundamental constraints of natural way of interacting such as speech, touch, contextual and environmental awareness,immersive 3D experiences-all with a goal of a computer that can see listen, learn talk and act. We drive a set of trends prevailing for the next generation of user interface: Natural User Interface (NUI).New technologies are pushing the boundaries of what is possible without touching or clicking an interface- paving the way of interaction to information visualization and opportunities in human towards more natural interaction than ever before. In this paper we consider the trends in computer interaction through that must be taken into consideration to come up-in the near future with a well-designed-NUI.
Retrieval in Long Surveillance Videos using User Described Motion and Object Attributes
Venue: arXiv cs.CV 2014
Year: 2014

We present a content-based retrieval method for long surveillance videos both for wide-area (Airborne) as well as near-field imagery (CCTV). Our goal is to retrieve video segments, with a focus on detecting objects moving on routes, that match user-defined events of interest. The sheer size and remote locations where surveillance videos are acquired, necessitates highly compressed representations that are also meaningful for supporting user-defined queries. To address these challenges we archive long-surveillance video through lightweight processing based on low-level local spatio-temporal extraction of motion and object features. These are then hashed into an inverted index using locality-sensitive hashing (LSH). This local approach allows for query flexibility as well as leads to significant gains in compression. Our second task is to extract partial matches to the user-created query and assembles them into full matches using Dynamic Programming (DP). DP exploits causality to assemble the indexed low level features into a video segment which matches the query route. We examine CCTV and Airborne footage, whose low contrast makes motion extraction more difficult. We generate robust motion estimates for Airborne data using a tracklets generation algorithm while we use Horn and Schunck approach to generate motion estimates for CCTV. Our approach handles long routes, low contrasts and occlusion. We derive bounds on the rate of false positives and demonstrate the effectiveness of the approach for counting, motion pattern recognition and abandoned object applications.
Coal Blending: Business Value, Analysis, and Optimization
Venue: arXiv cs.OH 2014
Year: 2014

Coal blending is a critically important process in the coal mining industry as it directly influences the number of product tonnes and the total revenue generated by a mine site. Coal blending represents a challenging and complex problem with numerous blending possibilities, multiple constraints and competing objectives. At many mine sites, blending decisions are made using heuristics that have been developed through experience or made by using computer assisted control algorithms or linear programming. While current blending procedures have achieved profitable outcomes in the past, they often result in a sub-optimal utilization of high quality coal. This sub-optimality has a considerable negative impact on mine site productivity as it can reduce the amount of lower quality ROM that is blended and sold. This article reviews the coal blending problem and discusses some of the difficult trade-offs and challenges that arise in trying to address this problem. We highlight some of the risks from making simplifying assumptions and the limitations of current software optimization systems. We conclude by explaining how the mining industry would significantly benefit from research and development into optimization algorithms and technologies that are better able to combine computer optimization algorithm capabilities with the important insights of engineers and quality control specialists.
Clausal Resolution for Modal Logics of Confluence
Venue: arXiv cs.LO 2014
Year: 2014

We present a clausal resolution-based method for normal multimodal logics of confluence, whose Kripke semantics are based on frames characterised by appropriate instances of the Church-Rosser property. Here we restrict attention to eight families of such logics. We show how the inference rules related to the normal logics of confluence can be systematically obtained from the parametrised axioms that characterise such systems. We discuss soundness, completeness, and termination of the method. In particular, completeness can be modularly proved by showing that the conclusions of each newly added inference rule ensures that the corresponding conditions on frames hold. Some examples are given in order to illustrate the use of the method.
Reservoir Computing Approach to Robust Computation using Unreliable Nanoscale Networks
Venue: arXiv cs.ET 2014
Year: 2014

As we approach the physical limits of CMOS technology, advances in materials science and nanotechnology are making available a variety of unconventional computing substrates that can potentially replace top-down-designed silicon-based computing devices. Inherent stochasticity in the fabrication process and nanometer scale of these substrates inevitably lead to design variations, defects, faults, and noise in the resulting devices. A key challenge is how to harness such devices to perform robust computation. We propose reservoir computing as a solution. In reservoir computing, computation takes place by translating the dynamics of an excited medium, called a reservoir, into a desired output. This approach eliminates the need for external control and redundancy, and the programming is done using a closed-form regression problem on the output, which also allows concurrent programming using a single device. Using a theoretical model, we show that both regular and irregular reservoirs are intrinsically robust to structural noise as they perform computation.
On Formalisms for Dynamic Reconfiguration of Dependable Systems
Venue: arXiv cs.SE 2014
Year: 2014

Three formalisms of different kinds - VDM, Maude, and basic CCSdp - are evaluated for their suitability for the modelling and verification of dynamic software reconfiguration using as a case study the dynamic reconfiguration of a simple office workflow for order processing. The research is ongoing, and initial results are reported.
Computing all Affine Solution Sets of Binomial Systems
Venue: arXiv cs.SC 2014
Year: 2014

To compute solutions of sparse polynomial systems efficiently we have to exploit the structure of their Newton polytopes. While the application of polyhedral methods naturally excludes solutions with zero components, an irreducible decomposition of a variety is typically understood in affine space, including also those components with zero coordinates. For the problem of computing solution sets in the intersection of some coordinate planes, the direct application of a polyhedral method fails, because the original facial structure of the Newton polytopes may alter completely when selected variables become zero. Our new proposed method enumerates all factors contributing to a generalized permanent and toric solutions as a special case of this enumeration. For benchmark problems such as the adjacent 2-by-2 minors of a general matrix, our methods scale much better than the witness set representations of numerical algebraic geometry.
Forbidden Induced Subgraphs of Normal Helly Circular-Arc Graphs: Characterization and Detection
Venue: arXiv cs.DM 2014
Year: 2014

A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin, Soulignac, and Szwarcfiter [Discrete Appl. Math. 2013] characterized circular-arc graphs that are not normal Helly circular-arc graphs, and used it to develop the first recognition algorithm for this graph class. As open problems, they ask for the forbidden induced subgraph characterization and a direct recognition algorithm for normal Helly circular-arc graphs, both of which are resolved by the current paper. Moreover, when the input is not a normal Helly circular-arc graph, our recognition algorithm finds in linear time a minimal forbidden induced subgraph as certificate.
Extension-based Semantics of Abstract Dialectical Frameworks
Venue: arXiv cs.AI 2014
Year: 2014

One of the most prominent tools for abstract argumentation is the Dung's framework, AF for short. It is accompanied by a variety of semantics including grounded, complete, preferred and stable. Although powerful, AFs have their shortcomings, which led to development of numerous enrichments. Among the most general ones are the abstract dialectical frameworks, also known as the ADFs. They make use of the so-called acceptance conditions to represent arbitrary relations. This level of abstraction brings not only new challenges, but also requires addressing existing problems in the field. One of the most controversial issues, recognized not only in argumentation, concerns the support cycles. In this paper we introduce a new method to ensure acyclicity of the chosen arguments and present a family of extension-based semantics built on it. We also continue our research on the semantics that permit cycles and fill in the gaps from the previous works. Moreover, we provide ADF versions of the properties known from the Dung setting. Finally, we also introduce a classification of the developed sub-semantics and relate them to the existing labeling-based approaches.
Safraless Synthesis for Epistemic Temporal Specifications
Venue: arXiv cs.LO 2014
Year: 2014

In this paper we address the synthesis problem for specifications given in linear temporal single-agent epistemic logic, KLTL (or $KL_1$), over single-agent systems having imperfect information of the environment state. Van der Meyden and Vardi have shown that this problem is 2Exptime complete. However, their procedure relies on complex automata constructions that are notoriously resistant to efficient implementations as they use Safra-like determinization. We propose a "Safraless" synthesis procedure for a large fragment of KLTL. The construction transforms first the synthesis problem into the problem of checking emptiness for universal co-Büchi tree automata using an information-set construction. Then we build a safety game that can be solved using an antichain-based symbolic technique exploiting the structure of the underlying automata. The technique is implemented and applied to a couple of case studies.
A Note on Parameterised Knowledge Operations in Temporal Logic
Venue: arXiv cs.LO 2014
Year: 2014

We consider modeling the conception of knowledge in terms of temporal logic. The study of knowledge logical operations is originated around 1962 by representation of knowledge and belief using modalities. Nowadays, it is very good established area. However, we would like to look to it from a bit another point of view, our paper models knowledge in terms of linear temporal logic with {\em past}. We consider various versions of logical knowledge operations which may be defined in this framework. Technically, semantics, language and temporal knowledge logics based on our approach are constructed. Deciding algorithms are suggested, unification in terms of this approach is commented. This paper does not offer strong new technical outputs, instead we suggest new approach to conception of knowledge (in terms of time).
Perceptron-like Algorithms and Generalization Bounds for Learning to Rank
Venue: arXiv cs.LG 2014
Year: 2014

Learning to rank is a supervised learning problem where the output space is the space of rankings but the supervision space is the space of relevance scores. We make theoretical contributions to the learning to rank problem both in the online and batch settings. First, we propose a perceptron-like algorithm for learning a ranking function in an online setting. Our algorithm is an extension of the classic perceptron algorithm for the classification problem. Second, in the setting of batch learning, we introduce a sufficient condition for convex ranking surrogates to ensure a generalization bound that is independent of number of objects per query. Our bound holds when linear ranking functions are used: a common practice in many learning to rank algorithms. En route to developing the online algorithm and generalization bound, we propose a novel family of listwise large margin ranking surrogates. Our novel surrogate family is obtained by modifying a well-known pairwise large margin ranking surrogate and is distinct from the listwise large margin surrogates developed using the structured prediction framework. Using the proposed family, we provide a guaranteed upper bound on the cumulative NDCG (or MAP) induced loss under the perceptron-like algorithm. We also show that the novel surrogates satisfy the generalization bound condition.
Flexible Network Bandwidth and Latency Provisioning in the Datacenter
Venue: arXiv cs.NI 2014
Year: 2014

Predictably sharing the network is critical to achieving high utilization in the datacenter. Past work has focussed on providing bandwidth to endpoints, but often we want to allocate resources among multi-node services. In this paper, we present Parley, which provides service-centric minimum bandwidth guarantees, which can be composed hierarchically. Parley also supports service-centric weighted sharing of bandwidth in excess of these guarantees. Further, we show how to configure these policies so services can get low latencies even at high network load. We evaluate Parley on a multi-tiered oversubscribed network connecting 90 machines, each with a 10Gb/s network interface, and demonstrate that Parley is able to meet its goals.
Feature Selection On Boolean Symbolic Objects
Venue: arXiv cs.IR 2014
Year: 2014

With the boom in IT technology, the data sets used in application are more and more larger and are described by a huge number of attributes, therefore, the feature selection become an important discipline in Knowledge discovery and data mining, allowing the experts to select the most relevant features to improve the quality of their studies and to reduce the time processing of their algorithm. In addition to that, the data used by the applications become richer. They are now represented by a set of complex and structured objects, instead of simple numerical matrixes. The purpose of our algorithm is to do feature selection on rich data, called Boolean Symbolic Objects (BSOs). These objects are described by multivalued features. The BSOs are considered as higher level units which can model complex data, such as cluster of individuals, aggregated data or taxonomies. In this paper we will introduce a new feature selection criterion for BSOs, and we will explain how we improved its complexity.
Finding a Curve in a Point Set
Venue: arXiv cs.CG 2014
Year: 2014

Let $P$ be a polygonal curve in $\mathbb{R}^D$ of length $n$, and $S$ be a point set of size $k$. The Curve/Point Set Matching problem consists of finding a polygonal curve $Q$ on $S$ such that its Fréchet distance from $P$ is less than a given $\varepsilon$. In this paper, we consider this problem with the added freedom to transform the input curve $P$ by translating it, rotating it, or applying an arbitrary affine transform. We present exact and approximation algorithms for several variations of this problem.
Implementing Default and Autoepistemic Logics via the Logic of GK
Venue: arXiv cs.AI 2014
Year: 2014

The logic of knowledge and justified assumptions, also known as logic of grounded knowledge (GK), was proposed by Lin and Shoham as a general logic for nonmonotonic reasoning. To date, it has been used to embed in it default logic (propositional case), autoepistemic logic, Turner's logic of universal causation, and general logic programming under stable model semantics. Besides showing the generality of GK as a logic for nonmonotonic reasoning, these embeddings shed light on the relationships among these other logics. In this paper, for the first time, we show how the logic of GK can be embedded into disjunctive logic programming in a polynomial but non-modular translation with new variables. The result can then be used to compute the extension/expansion semantics of default logic, autoepistemic logic and Turner's logic of universal causation by disjunctive ASP solvers such as claspD(-2), DLV, GNT and cmodels.
The average representation - a cornucopia of power indices?
Venue: arXiv cs.GT 2014
Year: 2014

For the classical power indices there is a disproportion between power and relative weights, in general. We introduce two new indices, based on weighted representations, which are proportional to suitable relative weights and which also share several important properties of the classical power indices. Imposing further restrictions on the set of representations may lead to a whole family of such indices.
Market Coupling as the Universal Algorithm to Assess Zonal Divisions
Venue: arXiv cs.CE 2014
Year: 2014

Adopting a zonal structure of electricity market requires specification of zones' borders. In this paper we use social welfare as the measure to assess quality of various zonal divisions. The social welfare is calculated by Market Coupling algorithm. The analyzed divisions are found by the usage of extended Locational Marginal Prices (LMP) methodology presented in paper [1], which takes into account variable weather conditions. The offered method of assessment of a proposed division of market into zones is however not limited to LMP approach but can evaluate the social welfare of divisions obtained by any methodology.
Towards a Benchmark of Natural Language Arguments
Venue: arXiv cs.AI 2014
Year: 2014

The connections among natural language processing and argumentation theory are becoming stronger in the latest years, with a growing amount of works going in this direction, in different scenarios and applying heterogeneous techniques. In this paper, we present two datasets we built to cope with the combination of the Textual Entailment framework and bipolar abstract argumentation. In our approach, such datasets are used to automatically identify through a Textual Entailment system the relations among the arguments (i.e., attack, support), and then the resulting bipolar argumentation graphs are analyzed to compute the accepted arguments.
K-NS: Section-Based Outlier Detection in High Dimensional Space
Venue: arXiv cs.AI 2014
Year: 2014

Finding rare information hidden in a huge amount of data from the Internet is a necessary but complex issue. Many researchers have studied this issue and have found effective methods to detect anomaly data in low dimensional space. However, as the dimension increases, most of these existing methods perform poorly in detecting outliers because of "high dimensional curse". Even though some approaches aim to solve this problem in high dimensional space, they can only detect some anomaly data appearing in low dimensional space and cannot detect all of anomaly data which appear differently in high dimensional space. To cope with this problem, we propose a new k-nearest section-based method (k-NS) in a section-based space. Our proposed approach not only detects outliers in low dimensional space with section-density ratio but also detects outliers in high dimensional space with the ratio of k-nearest section against average value. After taking a series of experiments with the dimension from 10 to 10000, the experiment results show that our proposed method achieves 100% precision and 100% recall result in the case of extremely high dimensional space, and better improvement in low dimensional space compared to our previously proposed method.
Rapture in the Cartesian Wall between Real World Entities and their Abstract Models
Venue: arXiv cs.OH 2014
Year: 2014

This short paper envisages that the advancements made with respect to Big Data (BD), High Performance Computing, etc. would give rise to a new paradigm of concrete information models, which would closely replicate the real world and the consequences such as self-verifying information models, BD warehouses as intermediaries between data sources and information systems, etc.
On state complexity of unions of binary factor-free languages
Venue: arXiv cs.FL 2014
Year: 2014

It has been conjectured in 2011 by Brzozowski et al. that if $K$ and $L$ are factor-free regular languages over a binary alphabet having state complexity $m$ and $n$, resp, then the state complexity of $K\cup L$ is at most $mn-(m+n)+3-\min\{m,n\}$. We disprove this conjecture by giving a lower bound of $mn-(m+n)-2-\lfloor\frac{\min\{m,n\}-2}{2}\rfloor$, which exceeds the conjectured bound whenever $\min\{m,n\}\geq 10$.
Directed Security Policies: A Stateful Network Implementation
Venue: arXiv cs.CR 2014
Year: 2014

Large systems are commonly internetworked. A security policy describes the communication relationship between the networked entities. The security policy defines rules, for example that A can connect to B, which results in a directed graph. However, this policy is often implemented in the network, for example by firewalls, such that A can establish a connection to B and all packets belonging to established connections are allowed. This stateful implementation is usually required for the network's functionality, but it introduces the backflow from B to A, which might contradict the security policy. We derive compliance criteria for a policy and its stateful implementation. In particular, we provide a criterion to verify the lack of side effects in linear time. Algorithms to automatically construct a stateful implementation of security policy rules are presented, which narrows the gap between formalization and real-world implementation. The solution scales to large networks, which is confirmed by a large real-world case study. Its correctness is guaranteed by the Isabelle/HOL theorem prover.