OpenRaiser/Intern-Atlas huggingface dataset:
On the Hierarchy of Block Deterministic Languages
Venue: arXiv cs.FL 2015
Year: 2015

A regular language is $k$-lookahead deterministic (resp. $k$-block deterministic) if it is specified by a $k$-lookahead deterministic (resp. $k$-block deterministic) regular expression. These two subclasses of regular languages have been respectively introduced by Han and Wood ($k$-lookahead determinism) and by Giammarresi et al. ($k$-block determinism) as a possible extension of one-unambiguous languages defined and characterized by Brüggemann-Klein and Wood. In this paper, we study the hierarchy and the inclusion links of these families. We first show that each $k$-block deterministic language is the alphabetic image of some one-unambiguous language. Moreover, we show that the conversion from a minimal DFA of a $k$-block deterministic regular language to a $k$-block deterministic automaton not only requires state elimination, and that the proof given by Han and Wood of a proper hierarchy in $k$-block deterministic languages based on this result is erroneous. Despite these results, we show by giving a parameterized family that there is a proper hierarchy in $k$-block deterministic regular languages. We also prove that there is a proper hierarchy in $k$-lookahead deterministic regular languages by studying particular properties of unary regular expressions. Finally, using our valid results, we confirm that the family of $k$-block deterministic regular languages is strictly included into the one of $k$-lookahead deterministic regular languages by showing that any $k$-block deterministic unary language is one-unambiguous.
Deep Active Object Recognition by Joint Label and Action Prediction
Venue: arXiv cs.AI 2015
Year: 2015

An active object recognition system has the advantage of being able to act in the environment to capture images that are more suited for training and that lead to better performance at test time. In this paper, we propose a deep convolutional neural network for active object recognition that simultaneously predicts the object label, and selects the next action to perform on the object with the aim of improving recognition performance. We treat active object recognition as a reinforcement learning problem and derive the cost function to train the network for joint prediction of the object label and the action. A generative model of object similarities based on the Dirichlet distribution is proposed and embedded in the network for encoding the state of the system. The training is carried out by simultaneously minimizing the label and action prediction errors using gradient descent. We empirically show that the proposed network is able to predict both the object label and the actions on GERMS, a dataset for active object recognition. We compare the test label prediction accuracy of the proposed model with Dirichlet and Naive Bayes state encoding. The results of experiments suggest that the proposed model equipped with Dirichlet state encoding is superior in performance, and selects images that lead to better training and higher accuracy of label prediction at test time.
On A Testing and Implementation of Quantum Gate and Measurement Emulator (QGAME)
Venue: arXiv cs.OH 2015
Year: 2015

Today, people are looking forward to get an awesome computational power. This kind of desire can be answered by quantum computing. By adopting quantum mechanics theory, it can generate a very fast computation result. As known, quantum mechanics can establish that particle can also become wave; it shows that electron can be in duality. Through this theory, even a human teleportation is issued can be really happened in the future. However, it needs a high requirement of hardware support to implement the real quantum computing. That is why it is difficult to bring quantum computing into reality. This research presents a study about quantum computing. Here it is studied, a specialty of quantum computing, like superposition, as if the classical computer can do it. Since there was a marvellous research about quantum computer simulation that runs on classical computer, this research provides an analysis about our testing and implementation of Quantum Gate and Measurement Emulator (QGAME). Our analysis, testing and implementation are based on a method that always use in the software engineering field.
Ontology-driven Information Extraction
Venue: arXiv cs.AI 2015
Year: 2015

Homogeneous unstructured data (HUD) are collections of unstructured documents that share common properties, such as similar layout, common file format, or common domain of values. Building on such properties, it would be desirable to automatically process HUD to access the main information through a semantic layer -- typically an ontology -- called semantic view. Hence, we propose an ontology-based approach for extracting semantically rich information from HUD, by integrating and extending recent technologies and results from the fields of classical information extraction, table recognition, ontologies, text annotation, and logic programming. Moreover, we design and implement a system, named KnowRex, that has been successfully applied to curriculum vitae in the Europass style to offer a semantic view of them, and be able, for example, to select those which exhibit required skills.
Modeling and Querying Data Cubes on the Semantic Web
Venue: arXiv cs.DB 2015
Year: 2015

The web is changing the way in which data warehouses are designed, used, and queried. With the advent of initiatives such as Open Data and Open Government, organizations want to share their multidimensional data cubes and make them available to be queried online. The RDF data cube vocabulary (QB), the W3C standard to publish statistical data in RDF, presents several limitations to fully support the multidimensional model. The QB4OLAP vocabulary extends QB to overcome these limitations, allowing to im- plement the typical OLAP operations, such as rollup, slice, dice, and drill-across using standard SPARQL queries. In this paper we introduce a formal data model where the main object is the data cube, and define OLAP operations using this model, independent of the underlying representation of the cube. We show then that a cube expressed using our model can be represented using the QB4OLAP vocabulary, and finally we provide a SPARQL implementation of OLAP operations over data cubes in QB4OLAP.
The interface for functions in the dune-functions module
Venue: arXiv cs.MS 2015
Year: 2015

The dune-functions dune module introduces a new programmer interface for discrete and non-discrete functions. Unlike the previous interfaces considered in the existing dune modules, it is based on overloading operator(), and returning values by-value. This makes user code much more readable, and allows the incorporation of newer C++ features such as lambda expressions. Run-time polymorphism is implemented not by inheritance, but by type erasure, generalizing the ideas of the std::function class from the C++11 standard library. We describe the new interface, show its possibilities, and measure the performance impact of type erasure and return-by-value.
A Necessary Condition for Byzantine $k$-Set Agreement
Venue: arXiv cs.DC 2015
Year: 2015

This short paper presents a necessary condition for Byzantine $k$-set agreement in (synchronous or asynchronous) message-passing systems and asynchronous shared memory systems where the processes communicate through atomic single-writer multi-reader registers. It gives a proof, which is particularly simple, that $k$-set agreement cannot be solved $t$-resiliently in an $n$-process system when $n \leq 2t + \frac{t}{k}$. This bound is tight for the case $k=1$ (Byzantine consensus) in synchronous message-passing systems.
Leveraging Deliberately Generated Interferences for Multi-sensor Wireless RF Power Transmission
Venue: arXiv cs.NI 2015
Year: 2015

Wireless RF power transmission promises battery-less, resilient, and perpetual wireless sensor networks. Through the action of controllable Energy Transmitters (ETs) that operate at-a-distance, the sensors can be re-charged by harvesting the radiated RF energy. However, both the charging rate and effective charging range of the ETs are limited, and thus multiple ETs are required to cover large areas. While this action increases the amount of wireless energy injected into the network, there are certain areas where the RF energy combines destructively. To address this problem, we propose a duty-cycled random-phase multiple access (DRAMA). Non-intuitively, our approach relies on deliberately generating random interferences, both destructive and constructive, at the destination nodes. We demonstrate that DRAMA optimizes the power conversion efficiency, and the total amount of energy harvested. Through real-testbed experiments, we prove that our proposed scheme provides significant advantages over the current state of the art in our considered scenario, as it requires up to 70\% less input RF power to recharge the energy buffer of the sensor in the same time.
Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation
Venue: arXiv cs.DB 2015
Year: 2015

Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query, also referred to as parallel-correctness. This paper extends the study of the complexity of parallel-correctness and its constituents, parallel-soundness and parallel-completeness, to unions of conjunctive queries with and without negation. As a by-product it is shown that the containment problem for conjunctive queries with negation is coNEXPTIME-complete.
Flexible Widely-Linear Multi-Branch Decision Feedback Detection Algorithms for Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents widely-linear multi-branch decision feedback detection techniques for large-scale multiuser multiple-antenna systems. We consider a scenario with impairments in the radio-frequency chain in which the in-phase (I) and quadrature (Q) components exhibit an imbalance, which degrades the receiver performance and originates non-circular signals. A widely-linear multi-branch decision feedback receiver is developed to mitigate both the multiuser interference and the I/Q imbalance effects. An iterative detection and decoding scheme with the proposed receiver and convolutional codes is also devised. Simulation results show that the proposed techniques outperform existing algorithms.
Predicting the Sentiment Polarity and Rating of Yelp Reviews
Venue: arXiv cs.IR 2015
Year: 2015

Online reviews of businesses have become increasingly important in recent years, as customers and even competitors use them to judge the quality of a business. Yelp is one of the most popular websites for users to write such reviews, and it would be useful for them to be able to predict the sentiment or even the star rating of a review. In this paper, we develop two classifiers to perform positive/negative classification and 5-star classification. We use Naive Bayes, Support Vector Machines, and Logistic Regression as models, and achieved the best accuracy with Logistic Regression: 92.90% for positive/negative classification, and 63.92% for 5-star classification. These results demonstrate the quality of the Logistic Regression model using only the text of the review, yet there is a promising opportunity for improvement with more data, more features, and perhaps different models.
Generating Searchable Public-Key Ciphertexts with Hidden Structures for Fast Keyword Search
Venue: arXiv cs.CR 2015
Year: 2015

Existing semantically secure public-key searchable encryption schemes take search time linear with the total number of the ciphertexts. This makes retrieval from large-scale databases prohibitive. To alleviate this problem, this paper proposes Searchable Public-Key Ciphertexts with Hidden Structures (SPCHS) for keyword search as fast as possible without sacrificing semantic security of the encrypted keywords. In SPCHS, all keyword-searchable ciphertexts are structured by hidden relations, and with the search trapdoor corresponding to a keyword, the minimum information of therelations is disclosed to a search algorithm as the guidance to find all matching ciphertexts efficiently. We construct a simple SPCHS scheme from scratch in which the ciphertexts have a hidden star-like structure. We prove our scheme to be semantically secure based on the decisional bilinear Diffie-Hellman assumption in the Random Oracle (RO) model. The search complexity of our scheme is dependent on the actual number of the ciphertexts containing the queried keyword, rather than the number of all ciphertexts. Finally, we present a generic SPCHS construction from anonymous identity-based encryption and collision-free full-identity malleable Identity-Based Key Encapsulation Mechanism (IBKEM) with anonymity. We illustrate two collision-free full-identity malleable IBKEM instances, which are semantically secure and anonymous, respectively, in the RO and standard models. The latter instance enables us to construct an SPCHS scheme with semantic security in the standard model.
Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures (full version)
Venue: arXiv cs.DC 2015
Year: 2015

Distributed applications are commonly based on overlay networks interconnecting their sites so that they can exchange information. For these overlay networks to preserve their functionality, they should be able to recover from various problems like membership changes or faults. Various self-stabilizing overlay networks have already been proposed in recent years, which have the advantage of being able to recover from any illegal state, but none of these networks can give any guarantees on its functionality while the recovery process is going on. We initiate research on overlay networks that are not only self-stabilizing but that also ensure that searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node $u$ to another node $v$ is successfully delivered, all future search messages from $u$ to $v$ succeed as well. We call this property monotonic searchability. We show that in general it is impossible to provide monotonic searchability if corrupted messages are present in the system, which justifies the restriction to system states without corrupted messages. Furthermore, we provide a self-stabilizing protocol for the line for which we can also show monotonic searchability. It turns out that even for the line it is non-trivial to achieve this property. Additionally, we extend our protocol to deal with node departures in terms of the Finite Departure Problem of Foreback et. al (SSS 2014). This makes our protocol even capable of handling node dynamics. This is the full version of a correspondent paper published at OPODIS'15.
Constrained Sampling and Counting: Universal Hashing Meets SAT Solving
Venue: arXiv cs.AI 2015
Year: 2015

Constrained sampling and counting are two fundamental problems in artificial intelligence with a diverse range of applications, spanning probabilistic reasoning and planning to constrained-random verification. While the theory of these problems was thoroughly investigated in the 1980s, prior work either did not scale to industrial size instances or gave up correctness guarantees to achieve scalability. Recently, we proposed a novel approach that combines universal hashing and SAT solving and scales to formulas with hundreds of thousands of variables without giving up correctness guarantees. This paper provides an overview of the key ingredients of the approach and discusses challenges that need to be overcome to handle larger real-world instances.
Addressing Complex and Subjective Product-Related Queries with Customer Reviews
Venue: arXiv cs.IR 2015
Year: 2015

Online reviews are often our first port of call when considering products and purchases online. When evaluating a potential purchase, we may have a specific query in mind, e.g. `will this baby seat fit in the overhead compartment of a 747?' or `will I like this album if I liked Taylor Swift's 1989?'. To answer such questions we must either wade through huge volumes of consumer reviews hoping to find one that is relevant, or otherwise pose our question directly to the community via a Q/A system. In this paper we hope to fuse these two paradigms: given a large volume of previously answered queries about products, we hope to automatically learn whether a review of a product is relevant to a given query. We formulate this as a machine learning problem using a mixture-of-experts-type framework---here each review is an `expert' that gets to vote on the response to a particular query; simultaneously we learn a relevance function such that `relevant' reviews are those that vote correctly. At test time this learned relevance function allows us to surface reviews that are relevant to new queries on-demand. We evaluate our system, Moqa, on a novel corpus of 1.4 million questions (and answers) and 13 million reviews. We show quantitatively that it is effective at addressing both binary and open-ended queries, and qualitatively that it surfaces reviews that human evaluators consider to be relevant.
Where Chicagoans tweet the most: Semantic analysis of preferential return locations of Twitter users
Venue: arXiv cs.SI 2015
Year: 2015

Recent studies on human mobility show that human movements are not random and tend to be clustered. In this connection, the movements of Twitter users captured by geo-located tweets were found to follow similar patterns, where a few geographic locations dominate the tweeting activity of individual users. However, little is known about the semantics (landuse types) and temporal tweeting behavior at those frequently-visited locations. Furthermore, it is generally assumed that the top two visited locations for most of the users are home and work locales (Hypothesis A) and people tend to tweet at their top locations during a particular time of the day (Hypothesis B). In this paper, we tested these two frequently cited hypotheses by examining the tweeting patterns of more than 164,000 unique Twitter users whom were residents of the city of Chicago during 2014. We extracted landuse attributes for each geo-located tweet from the detailed inventory of the Chicago Metropolitan Agency for Planning. Top-visited locations were identified by clustering semantic enriched tweets using a DBSCAN algorithm. Our results showed that although the top two locations are likely to be residential and occupational/educational, a portion of the users deviated from this case, suggesting that the first hypothesis oversimplify real-world situations. However, our observations indicated that people tweet at specific times and these temporal signatures are dependent on landuse types. We further discuss the implication of confounding variables, such as clustering algorithm parameters and relative accuracy of tweet coordinates, which are critical factors in any experimental design involving Twitter data.
Query Stability in Monotonic Data-Aware Business Processes [Extended Version]
Venue: arXiv cs.DB 2015
Year: 2015

Organizations continuously accumulate data, often according to some business processes. If one poses a query over such data for decision support, it is important to know whether the query is stable, that is, whether the answers will stay the same or may change in the future because business processes may add further data. We investigate query stability for conjunctive queries. To this end, we define a formalism that combines an explicit representation of the control flow of a process with a specification of how data is read and inserted into the database. We consider different restrictions of the process model and the state of the system, such as negation in conditions, cyclic executions, read access to written data, presence of pending process instances, and the possibility to start fresh process instances. We identify for which facet combinations stability of conjunctive queries is decidable and provide encodings into variants of Datalog that are optimal with respect to the worst-case complexity of the problem.
Synthesis of models for order-sorted first-order theories using linear algebra and constraint solving
Venue: arXiv cs.PL 2015
Year: 2015

Recent developments in termination analysis for declarative programs emphasize the use of appropriate models for the logical theory representing the program at stake as a generic approach to prove termination of declarative programs. In this setting, Order-Sorted First-Order Logic provides a powerful framework to represent declarative programs. It also provides a target logic to obtain models for other logics via transformations. We investigate the automatic generation of numerical models for order-sorted first-order logics and its use in program analysis, in particular in termination analysis of declarative programs. We use convex domains to give domains to the different sorts of an order-sorted signature; we interpret the ranked symbols of sorted signatures by means of appropriately adapted convex matrix interpretations. Such numerical interpretations permit the use of existing algorithms and tools from linear algebra and arithmetic constraint solving to synthesize the models.
Restricted Predicates for Hypothetical Datalog
Venue: arXiv cs.DB 2015
Year: 2015

Hypothetical Datalog is based on an intuitionistic semantics rather than on a classical logic semantics, and embedded implications are allowed in rule bodies. While the usual implication (i.e., the neck of a Horn clause) stands for inferring facts, an embedded implication plays the role of assuming its premise for deriving its consequence. A former work introduced both a formal framework and a goal-oriented tabled implementation, allowing negation in rule bodies. While in that work positive assumptions for both facts and rules can occur in the premise, negative assumptions are not allowed. In this work, we cover this subject by introducing a new concept: a restricted predicate, which allows negative assumptions by pruning the usual semantics of a predicate. This new setting has been implemented in the deductive system DES.
Covering Arrays on Product Graphs
Venue: arXiv cs.DM 2015
Year: 2015

Two vectors $x,y$ in $\mathbb{Z}_g^n$ are $ qualitatively$ $ independent$ if for all pairs $(a,b)\in \mathbb{Z}_g\times \mathbb{Z}_g$, there exists $i\in \{1,2,\ldots,n\}$ such that $(x_i,y_i)=(a,b)$. A covering array on a graph $G$, denoted by $CA(n,G,g)$, is a $|V(G)|\times n$ array on $\mathbb{Z}_g$ with the property that any two rows which correspond to adjacent vertices in $G$ are qualitatively independent. The number of columns in such array is called its $size$. Given a graph $G$, a covering array on $G$ with minimum size is called $optimal$. Our primary concern in this paper is with constructions that make optimal covering arrays on large graphs those are obtained from product of smaller graphs. We consider four most extensively studied graph products in literature and give upper and lower bounds on the the size of covering arrays on graph products. We find families of graphs for which the size of covering array on the Cartesian product achieves the lower bound. Finally, we present a polynomial time approximation algorithm with approximation ratio $\log(\frac{V}{2^{k-1}})$ for constructing covering array on graph $G=(V,E)$ with $k>1$ prime factors with respect to the Cartesian product.