OpenRaiser/Intern-Atlas huggingface dataset:
Prime Implicates and Prime Implicants: From Propositional to Modal Logic
Venue: arXiv cs.LO 2014
Year: 2014

Prime implicates and prime implicants have proven relevant to a number of areas of artificial intelligence, most notably abductive reasoning and knowledge compilation. The purpose of this paper is to examine how these notions might be appropriately extended from propositional logic to the modal logic K. We begin the paper by considering a number of potential definitions of clauses and terms for K. The different definitions are evaluated with respect to a set of syntactic, semantic, and complexity-theoretic properties characteristic of the propositional definition. We then compare the definitions with respect to the properties of the notions of prime implicates and prime implicants that they induce. While there is no definition that perfectly generalizes the propositional notions, we show that there does exist one definition which satisfies many of the desirable properties of the propositional case. In the second half of the paper, we consider the computational properties of the selected definition. To this end, we provide sound and complete algorithms for generating and recognizing prime implicates, and we show the prime implicate recognition task to be PSPACE-complete. We also prove upper and lower bounds on the size and number of prime implicates. While the paper focuses on the logic K, all of our results hold equally well for multi-modal K and for concept expressions in the description logic ALC.
The Complexity of Circumscription in DLs
Venue: arXiv cs.LO 2014
Year: 2014

As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an interesting alternative approach to nonmonotonic DLs that, in particular, supports defeasible inheritance in a natural way. We study DLs extended with circumscription under different language restrictions and under different constraints on the sets of minimized, fixed, and varying predicates, and pinpoint the exact computational complexity of reasoning for DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed predicates include only concept names but no role names, then reasoning is complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number of minimized and fixed predicates is bounded by a constant. If roles can be minimized or fixed, then complexity ranges from NExpTime^NP to undecidability.
Complex Question Answering: Unsupervised Learning Approaches and Experiments
Venue: arXiv cs.CL 2014
Year: 2014

Complex questions that require inferencing and synthesizing information from multiple documents can be seen as a kind of topic-oriented, informative multi-document summarization where the goal is to produce a single text as a compressed version of a set of documents with a minimum loss of relevant information. In this paper, we experiment with one empirical method and two unsupervised statistical machine learning techniques: K-means and Expectation Maximization (EM), for computing relative importance of the sentences. We compare the results of these approaches. Our experiments show that the empirical approach outperforms the other two techniques and EM performs better than K-means. However, the performance of these approaches depends entirely on the feature set used and the weighting of these features. In order to measure the importance and relevance to the user query we extract different kinds of features (i.e. lexical, lexical semantic, cosine similarity, basic element, tree kernel based syntactic and shallow-semantic) for each of the document sentences. We use a local search technique to learn the weights of the features. To the best of our knowledge, no study has used tree kernel functions to encode syntactic/semantic information for more complex tasks such as computing the relatedness between the query sentences and the document sentences in order to generate query-focused summaries (or answers to complex questions). For each of our methods of generating summaries (i.e. empirical, K-means and EM) we show the effects of syntactic and shallow-semantic features over the bag-of-words (BOW) features.
Enhancing QA Systems with Complex Temporal Question Processing Capabilities
Venue: arXiv cs.CL 2014
Year: 2014

This paper presents a multilayered architecture that enhances the capabilities of current QA systems and allows different types of complex questions or queries to be processed. The answers to these questions need to be gathered from factual information scattered throughout different documents. Specifically, we designed a specialized layer to process the different types of temporal questions. Complex temporal questions are first decomposed into simple questions, according to the temporal relations expressed in the original question. In the same way, the answers to the resulting simple questions are recomposed, fulfilling the temporal restrictions of the original complex question. A novel aspect of this approach resides in the decomposition which uses a minimal quantity of resources, with the final aim of obtaining a portable platform that is easily extensible to other languages. In this paper we also present a methodology for evaluation of the decomposition of the questions as well as the ability of the implemented temporal layer to perform at a multilingual level. The temporal layer was first performed for English, then evaluated and compared with: a) a general purpose QA system (F-measure 65.47% for QA plus English temporal layer vs. 38.01% for the general QA system), and b) a well-known QA system. Much better results were obtained for temporal questions with the multilayered system. This system was therefore extended to Spanish and very good results were again obtained in the evaluation (F-measure 40.36% for QA plus Spanish temporal layer vs. 22.94% for the general QA system).
Hypertableau Reasoning for Description Logics
Venue: arXiv cs.LO 2014
Year: 2014

We present a novel reasoning calculus for the description logic SHOIQ^+---a knowledge representation formalism with applications in areas such as the Semantic Web. Unnecessary nondeterminism and the construction of large models are two primary sources of inefficiency in the tableau-based reasoning calculi used in state-of-the-art reasoners. In order to reduce nondeterminism, we base our calculus on hypertableau and hyperresolution calculi, which we extend with a blocking condition to ensure termination. In order to reduce the size of the constructed models, we introduce anywhere pairwise blocking. We also present an improved nominal introduction rule that ensures termination in the presence of nominals, inverse roles, and number restrictions---a combination of DL constructs that has proven notoriously difficult to handle. Our implementation shows significant performance improvements over state-of-the-art reasoners on several well-known ontologies.
The Role of Macros in Tractable Planning
Venue: arXiv cs.AI 2014
Year: 2014

This paper presents several new tractability results for planning based on macros. We describe an algorithm that optimally solves planning problems in a class that we call inverted tree reducible, and is provably tractable for several subclasses of this class. By using macros to store partial plans that recur frequently in the solution, the algorithm is polynomial in time and space even for exponentially long plans. We generalize the inverted tree reducible class in several ways and describe modifications of the algorithm to deal with these new classes. Theoretical results are validated in experiments.
The DL-Lite Family and Relations
Venue: arXiv cs.LO 2014
Year: 2014

The recently introduced series of description logics under the common moniker DL-Lite has attracted attention of the description logic and semantic web communities due to the low computational complexity of inference, on the one hand, and the ability to represent conceptual modeling formalisms, on the other. The main aim of this article is to carry out a thorough and systematic investigation of inference in extensions of the original DL-Lite logics along five axes: by (i) adding the Boolean connectives and (ii) number restrictions to concept constructs, (iii) allowing role hierarchies, (iv) allowing role disjointness, symmetry, asymmetry, reflexivity, irreflexivity and transitivity constraints, and (v) adopting or dropping the unique same assumption. We analyze the combined complexity of satisfiability for the resulting logics, as well as the data complexity of instance checking and answering positive existential queries. Our approach is based on embedding DL-Lite logics in suitable fragments of the one-variable first-order logic, which provides useful insights into their properties and, in particular, computational behavior.
ParamILS: An Automatic Algorithm Configuration Framework
Venue: arXiv cs.AI 2014
Year: 2014

The identification of performance-optimizing parameter settings is an important part of the development and application of algorithms. We describe an automatic framework for this algorithm configuration problem. More formally, we provide methods for optimizing a target algorithm's performance on a given class of problem instances by varying a set of ordinal and/or categorical parameters. We review a family of local-search-based algorithm configuration procedures and present novel techniques for accelerating them by adaptively limiting the time spent for evaluating individual configurations. We describe the results of a comprehensive experimental evaluation of our methods, based on the configuration of prominent complete and incomplete algorithms for SAT. We also present what is, to our knowledge, the first published work on automatically configuring the CPLEX mixed integer programming solver. All the algorithms we considered had default parameter settings that were manually identified with considerable effort. Nevertheless, using our automated algorithm configuration procedures, we achieved substantial and consistent performance improvements.
Predicting the Performance of IDA* using Conditional Distributions
Venue: arXiv cs.AI 2014
Year: 2014

Korf, Reid, and Edelkamp introduced a formula to predict the number of nodes IDA* will expand on a single iteration for a given consistent heuristic, and experimentally demonstrated that it could make very accurate predictions. In this paper we show that, in addition to requiring the heuristic to be consistent, their formulas predictions are accurate only at levels of the brute-force search tree where the heuristic values obey the unconditional distribution that they defined and then used in their formula. We then propose a new formula that works well without these requirements, i.e., it can make accurate predictions of IDA*s performance for inconsistent heuristics and if the heuristic values in any level do not obey the unconditional distribution. In order to achieve this we introduce the conditional distribution of heuristic values which is a generalization of their unconditional heuristic distribution. We also provide extensions of our formula that handle individual start states and the augmentation of IDA* with bidirectional pathmax (BPMX), a technique for propagating heuristic values when inconsistent heuristics are used. Experimental results demonstrate the accuracy of our new method and all its variations.
Self-Optimizing Mechanisms for EMF Reduction in Heterogeneous Networks
Venue: arXiv cs.NI 2014
Year: 2014

This paper focuses on the exposure to Radio Frequency (RF) Electromagnetic Fields (EMF) and on optimization methods to reduce it. Within the FP7 LEXNET project, an Exposure Index (EI) has been defined that aggregates the essential components that impact exposure to EMF. The EI includes, among other, downlink (DL) exposure induced by the base stations (BSs) and access points, the uplink (UL) exposure induced by the devices in communication, and the corresponding exposure time. Motivated by the EI definition, this paper develops stochastic approximation based self-optimizing algorithm that dynamically adapts the network to reduce the EI in a heterogeneous network with macro- and small cells. It is argued that the increase of the small cells' coverage can, to a certain extent, reduce the EI, but above a certain limit, will deteriorate DL QoS. A load balancing algorithm is formulated that adapts the small cell' coverage based on UL loads and a DL QoS indicator. The proof of convergence of the algorithm is provided and its performance in terms of EI reduction is illustrated through extensive numerical simulations.
2D Direction Of Arrival Estimation with Modified Propagator
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, a fast algorithm for the Direction Of Arrival (DOA) estimation of radiating sources, based on partial covariance matrix and without eigende- composition of incoming signals is extended to two dimensional problem of joint azimuth and elevation estimation angles using Uniform Circular Array (UCA) in case of non coherent narrowband signals. Simulation results are presented with both Additive White Gaussian Noise (AWGN) and real symmetric Toeplitz noise.
A Brief History of Learning Classifier Systems: From CS-1 to XCS
Venue: arXiv cs.NE 2014
Year: 2014

Modern Learning Classifier Systems can be characterized by their use of rule accuracy as the utility metric for the search algorithm(s) discovering useful rules. Such searching typically takes place within the restricted space of co-active rules for efficiency. This paper gives an historical overview of the evolution of such systems up to XCS, and then some of the subsequent developments of XCS to different types of learning.
Transport Information System using Query Centric Cyber Physical Systems (QCPS)
Venue: arXiv cs.OH 2014
Year: 2014

To incorporate the computation and communication with the physical world, next generation architecture i.e. CPS is viewed as a new technology. To improve the better interaction with the physical world or to perk up the electricity delivery usage, various CPS based approaches have been introduced. Recently several GPS equipped smart phones and sensor based frameworks have been proposed which provide various services i.e. environment estimation, road safety improvement but encounter certain limitations like elevated energy consumption and high computation cost. To meet the high reliability and safety requirements, this paper introduces a novel approach based on QCPS model which provides several users services (discussed in this paper). Further, this paper proposed a Transport Information System (TIS), which provide the communication with lower cost overhead by arranging the similar sensors in the form of grids. Each grid has a coordinator which interacts with cloud to process the user query. In order to evaluate the performance of proposed approach we have implemented a test bed of 16 wireless sensor nodes and have shown the performance in terms of computation and communication cost.
A MILP model for an extended version of the Flexible Job Shop Problem
Venue: arXiv cs.DS 2014
Year: 2014

A MILP model for an extended version of the Flexible Job Shop Scheduling problem is proposed. The extension allows the precedences between operations of a job to be given by an arbitrary directed acyclic graph rather than a linear order. The goal is the minimization of the makespan. Theoretical and practical advantages of the proposed model are discussed. Numerical experiments show the performance of a commercial exact solver when applied to the proposed model. The new model is also compared with a simple extension of the model described by Özgüven, Özbakir, and Yavuz (Mathematical models for job-shop scheduling problems with routing and process plan flexibility, Applied Mathematical Modelling, 34:1539--1548, 2010), using instances from the literature and instances inspired by real data from the printing industry.
Hrebs and Cohesion Chains as similar tools for semantic text properties research
Venue: arXiv cs.CL 2014
Year: 2014

In this study it is proven that the Hrebs used in Denotation analysis of texts and Cohesion Chains (defined as a fusion between Lexical Chains and Coreference Chains) represent similar linguistic tools. This result gives us the possibility to extend to Cohesion Chains (CCs) some important indicators as, for example the Kernel of CCs, the topicality of a CC, text concentration, CC-diffuseness and mean diffuseness of the text. Let us mention that nowhere in the Lexical Chains or Coreference Chains literature these kinds of indicators are introduced and used since now. Similarly, some applications of CCs in the study of a text (as for example segmentation or summarization of a text) could be realized starting from hrebs. As an illustration of the similarity between Hrebs and CCs a detailed analyze of the poem "Lacul" by Mihai Eminescu is given.
The Ginibre Point Process as a Model for Wireless Networks with Repulsion
Venue: arXiv cs.IT 2014
Year: 2014

The spatial structure of transmitters in wireless networks plays a key role in evaluating the mutual interference and hence the performance. Although the Poisson point process (PPP) has been widely used to model the spatial configuration of wireless networks, it is not suitable for networks with repulsion. The Ginibre point process (GPP) is one of the main examples of determinantal point processes that can be used to model random phenomena where repulsion is observed. Considering the accuracy, tractability and practicability tradeoffs, we introduce and promote the $β$-GPP, an intermediate class between the PPP and the GPP, as a model for wireless networks when the nodes exhibit repulsion. To show that the model leads to analytically tractable results in several cases of interest, we derive the mean and variance of the interference using two different approaches: the Palm measure approach and the reduced second moment approach, and then provide approximations of the interference distribution by three known probability density functions. Besides, to show that the model is relevant for cellular systems, we derive the coverage probability of the typical user and also find that the fitted $β$-GPP can closely model the deployment of actual base stations in terms of the coverage probability and other statistics.
$\mathcal R\!\raise2pt\hbox{$\varepsilon$}\!\hbox{$\mathcal L$}$: A Fault Tolerance Linguistic Structure for Distributed Applications
Venue: arXiv cs.DC 2014
Year: 2014

The embedding of fault tolerance provisions into the application layer of a programming language is a non-trivial task that has not found a satisfactory solution yet. Such a solution is very important, and the lack of a simple, coherent and effective structuring technique for fault tolerance has been termed by researchers in this field as the "software bottleneck of system development". The aim of this paper is to report on the current status of a novel fault tolerance linguistic structure for distributed applications characterized by soft real-time requirements. A compliant prototype architecture is also described. The key aspect of this structure is that it allows to decompose the target fault-tolerant application into three distinct components, respectively responsible for (1) the functional service, (2) the management of the fault tolerance provisions, and (3) the adaptation to the current environmental conditions. The paper also briefly mentions a few case studies and preliminary results obtained exercising the prototype.
$2^3$ Quantified Boolean Formula Games and Their Complexities
Venue: arXiv cs.CC 2014
Year: 2014

Consider QBF, the Quantified Boolean Formula problem, as a combinatorial game ruleset. The problem is rephrased as determining the winner of the game where two opposing players take turns assigning values to boolean variables. In this paper, three common variations of games are applied to create seven new games: whether each player is restricted to where they may play, which values they may set variables to, or the condition they are shooting for at the end of the game. The complexity for determining which player can win is analyzed for all games. Of the seven, two are trivially in P and the other five are PSPACE-complete. These varying properties are common for combinatorial games; reductions from these five hard games can simplify the process for showing the PSPACE-hardness of other games.
Physical Realizability and Mean Square Performance of Translation Invariant Networks of Interacting Linear Quantum Stochastic Systems
Venue: arXiv cs.SY 2014
Year: 2014

This paper is concerned with translation invariant networks of linear quantum stochastic systems with nearest neighbour interaction mediated by boson fields. The systems are associated with sites of a one-dimensional chain or a multidimensional lattice and are governed by coupled linear quantum stochastic differential equations (QSDEs). Such interconnections of open quantum systems are relevant, for example, to the phonon theory of crystalline solids, atom trapping in optical lattices and quantum metamaterials. In order to represent a large-scale open quantum harmonic oscillator, the coefficients of the coupled QSDEs must satisfy certain physical realizability conditions. These are established in the form of matrix algebraic equations for the parameters of an individual building block of the network and its interaction with the neighbours and external fields. We also discuss the computation of mean square performance functionals with block Toeplitz weighting matrices for such systems in the thermodynamic limit per site for unboundedly increasing fragments of the lattice.
Lightweight and Secure Two-Party Range Queries over Outsourced Encrypted Databases
Venue: arXiv cs.CR 2014
Year: 2014

With the many benefits of cloud computing, an entity may want to outsource its data and their related analytics tasks to a cloud. When data are sensitive, it is in the interest of the entity to outsource encrypted data to the cloud; however, this limits the types of operations that can be performed on the cloud side. Especially, evaluating queries over the encrypted data stored on the cloud without the entity performing any computation and without ever decrypting the data become a very challenging problem. In this paper, we propose solutions to conduct range queries over outsourced encrypted data. The existing methods leak valuable information to the cloud which can violate the security guarantee of the underlying encryption schemes. In general, the main security primitive used to evaluate range queries is secure comparison (SC) of encrypted integers. However, we observe that the existing SC protocols are not very efficient. To this end, we first propose a novel SC scheme that takes encrypted integers and outputs encrypted comparison result. We empirically show its practical advantage over the current state-of-the-art. We then utilize the proposed SC scheme to construct two new secure range query protocols. Our protocols protect data confidentiality, privacy of user's query, and also preserve the semantic security of the encrypted data; therefore, they are more secure than the existing protocols. Furthermore, our second protocol is lightweight at the user end, and it can allow an authorized user to use any device with limited storage and computing capability to perform the range queries over outsourced encrypted data.