OpenRaiser/Intern-Atlas huggingface dataset:
Computing with Logic as Operator Elimination: The ToyElim System
Venue: arXiv cs.AI 2011
Year: 2011

A prototype system is described whose core functionality is, based on propositional logic, the elimination of second-order operators, such as Boolean quantifiers and operators for projection, forgetting and circumscription. This approach allows to express many representational and computational tasks in knowledge representation - for example computation of abductive explanations and models with respect to logic programming semantics - in a uniform operational system, backed by a uniform classical semantic framework.
Minimalist Grammars and Minimalist Categorial Grammars, definitions toward inclusion of generated languages
Venue: arXiv cs.CL 2011
Year: 2011

Stabler proposes an implementation of the Chomskyan Minimalist Program, Chomsky 95 with Minimalist Grammars - MG, Stabler 97. This framework inherits a long linguistic tradition. But the semantic calculus is more easily added if one uses the Curry-Howard isomorphism. Minimalist Categorial Grammars - MCG, based on an extension of the Lambek calculus, the mixed logic, were introduced to provide a theoretically-motivated syntax-semantics interface, Amblard 07. In this article, we give full definitions of MG with algebraic tree descriptions and of MCG, and take the first steps towards giving a proof of inclusion of their generated languages.
Single-trial EEG Discrimination between Wrist and Finger Movement Imagery and Execution in a Sensorimotor BCI
Venue: arXiv cs.AI 2011
Year: 2011

A brain-computer interface (BCI) may be used to control a prosthetic or orthotic hand using neural activity from the brain. The core of this sensorimotor BCI lies in the interpretation of the neural information extracted from electroencephalogram (EEG). It is desired to improve on the interpretation of EEG to allow people with neuromuscular disorders to perform daily activities. This paper investigates the possibility of discriminating between the EEG associated with wrist and finger movements. The EEG was recorded from test subjects as they executed and imagined five essential hand movements using both hands. Independent component analysis (ICA) and time-frequency techniques were used to extract spectral features based on event-related (de)synchronisation (ERD/ERS), while the Bhattacharyya distance (BD) was used for feature reduction. Mahalanobis distance (MD) clustering and artificial neural networks (ANN) were used as classifiers and obtained average accuracies of 65 % and 71 % respectively. This shows that EEG discrimination between wrist and finger movements is possible. The research introduces a new combination of motor tasks to BCI research.
A Frequent Closed Itemsets Lattice-based Approach for Mining Minimal Non-Redundant Association Rules
Venue: arXiv cs.DB 2011
Year: 2011

There are many algorithms developed for improvement the time of mining frequent itemsets (FI) or frequent closed itemsets (FCI). However, the algorithms which deal with the time of generating association rules were not put in deep research. In reality, in case of a database containing many FI/FCI (from ten thousands up to millions), the time of generating association rules is much larger than that of mining FI/FCI. Therefore, this paper presents an application of frequent closed itemsets lattice (FCIL) for mining minimal non-redundant association rules (MNAR) to reduce a lot of time for generating rules. Firstly, we use CHARM-L for building FCIL. After that, based on FCIL, an algorithm for fast generating MNAR will be proposed. Experimental results show that the proposed algorithm is much faster than frequent itemsets lattice-based algorithm in the mining time.
Checking Finite State Machine Conformance when there are Distributed Observations
Venue: arXiv cs.SE 2011
Year: 2011

This paper concerns state-based systems that interact with their environment at physically distributed interfaces, called ports. When such a system is used a projection of the global trace, called a local trace, is observed at each port. This leads to the environment having reduced observational power: the set of local traces observed need not uniquely define the global trace that occurred. We consider the previously defined implementation relation $\sqsubseteq_s$ and start by investigating the problem of defining a language ${\mathcal {\tilde L}} (M)$ for a multi-port finite state machine (FSM) $M$ such that $N \sqsubseteq_s M$ if and only if every global trace of $N$ is in ${\mathcal {\tilde L}} (M)$. The motivation is that if we can produce such a language ${\mathcal {\tilde L}} (M)$ then this can potentially be used to inform development and testing. We show that ${\mathcal {\tilde L}} (M)$ can be uniquely defined but need not be regular. We then prove that it is generally undecidable whether $N \sqsubseteq_s M$, a consequence of this result being that it is undecidable whether there is a test case that is capable of distinguishing two states or two multi-port FSM in distributed testing. This result complements a previous result that it is undecidable whether there is a test case that is guaranteed to distinguish two states or multi-port FSMs. We also give some conditions under which $N \sqsubseteq_s M$ is decidable. We then consider the implementation relation $\sqsubseteq_s^k$ that only concerns input sequences of length $k$ or less. Naturally, given FSMs $N$ and $M$ it is decidable whether $N \sqsubseteq_s^k M$ since only a finite set of traces is relevant. We prove that if we place bounds on $k$ and the number of ports then we can decide $N \sqsubseteq_s^k M$ in polynomial time but otherwise this problem is NP-hard.
Personalized Web Services for Web Information Extraction
Venue: arXiv cs.IR 2011
Year: 2011

The field of information extraction from the Web emerged with the growth of the Web and the multiplication of online data sources. This paper is an analysis of information extraction methods. It presents a service oriented approach for web information extraction considering both web data management and extraction services. Then we propose an SOA based architecture to enhance flexibility and on-the-fly modification of web extraction services. An implementation of the proposed architecture is proposed on the middleware level of Java Enterprise Edition (JEE) servers.
Improving Ranking Using Quantum Probability
Venue: arXiv cs.IR 2011
Year: 2011

The paper shows that ranking information units by quantum probability differs from ranking them by classical probability provided the same data used for parameter estimation. As probability of detection (also known as recall or power) and probability of false alarm (also known as fallout or size) measure the quality of ranking, we point out and show that ranking by quantum probability yields higher probability of detection than ranking by classical probability provided a given probability of false alarm and the same parameter estimation data. As quantum probability provided more effective detectors than classical probability within other domains that data management, we conjecture that, the system that can implement subspace-based detectors shall be more effective than a system which implements a set-based detectors, the effectiveness being calculated as expected recall estimated over the probability of detection and expected fallout estimated over the probability of false alarm.
Geographic Trough Filling for Internet Datacenters
Venue: arXiv cs.NI 2011
Year: 2011

To reduce datacenter energy consumption and cost, current practice has considered demand-proportional resource provisioning schemes, where servers are turned on/off according to the load of requests. Most existing work considers instantaneous (Internet) requests only, which are explicitly or implicitly assumed to be delay-sensitive. On the other hand, in datacenters, there exist a vast amount of delay-tolerant jobs, such as background/maintainance jobs. In this paper, we explicitly differentiate delay-sensitive jobs and delay tolerant jobs. We focus on the problem of using delay-tolerant jobs to fill the extra capacity of datacenters, referred to as trough/valley filling. Giving a higher priority to delay-sensitive jobs, our schemes complement to most existing demand-proportional resource provisioning schemes. Our goal is to design intelligent trough filling mechanisms that are energy efficient and also achieve good delay performance. Specifically, we propose two joint dynamic speed scaling and traffic shifting schemes, one subgradient-based and the other queue-based. Our schemes assume little statistical information of the system, which is usually difficult to obtain in practice. In both schemes, energy cost saving comes from dynamic speed scaling, statistical multiplexing, electricity price diversity, and service efficiency diversity. In addition, good delay performance is achieved in the queue-based scheme via load shifting and capacity allocation based on queue conditions. Practical issues that may arise in datacenter networks are considered, including capacity and bandwidth constraint, service agility constraint, and load shifting cost. We use both artificial and real datacenter traces to evaluate the proposed schemes.
A Note on Separable Nonlinear Least Squares Problem
Venue: arXiv cs.CG 2011
Year: 2011

Separable nonlinear least squares (SNLS)problem is a special class of nonlinear least squares (NLS)problems, whose objective function is a mixture of linear and nonlinear functions. It has many applications in many different areas, especially in Operations Research and Computer Sciences. They are difficult to solve with the infinite-norm metric. In this paper, we give a short note on the separable nonlinear least squares problem, unseparated scheme for NLS, and propose an algorithm for solving mixed linear-nonlinear minimization problem, method of which results in solving a series of least squares separable problems.
Implementing Equational Constraints in a Functional Language
Venue: arXiv cs.PL 2011
Year: 2011

KiCS2 is a new system to compile functional logic programs of the source language Curry into purely functional Haskell programs. The implementation is based on the idea to represent the search space as a data structure and logic variables as operations that generate their values. This has the advantage that one can apply various, and in particular, complete search strategies to compute solutions. However, the generation of all values for logic variables might be inefficient for applications that exploit constraints on partially known values. To overcome this drawback, we propose new techniques to implement equational constraints in this framework. In particular, we show how unification modulo function evaluation and functional patterns can be added without sacrificing the efficiency of the kernel implementation.
Modification of GTD from Flat File Format to OLAP for Data Mining
Venue: arXiv cs.DB 2011
Year: 2011

This document is part of original research work by the authors in a bid to explore new fields for applying Data Mining Techniques. The sample data is part of a large data set from University of Maryland (UMD) and outlines how more meaningful patterns can be discovered by preprocessing the data in the form of OLAP cubes.
Nested HEX-Programs
Venue: arXiv cs.AI 2011
Year: 2011

Answer-Set Programming (ASP) is an established declarative programming paradigm. However, classical ASP lacks subprogram calls as in procedural programming, and access to external computations (like remote procedure calls) in general. The feature is desired for increasing modularity and---assuming proper access in place---(meta-)reasoning over subprogram results. While HEX-programs extend classical ASP with external source access, they do not support calls of (sub-)programs upfront. We present nested HEX-programs, which extend HEX-programs to serve the desired feature, in a user-friendly manner. Notably, the answer sets of called sub-programs can be individually accessed. This is particularly useful for applications that need to reason over answer sets like belief set merging, user-defined aggregate functions, or preferences of answer sets.
Learning Valuation Functions
Venue: arXiv cs.GT 2011
Year: 2011

In this paper we study the approximate learnability of valuations commonly used throughout economics and game theory for the quantitative encoding of agent preferences. We provide upper and lower bounds regarding the learnability of important subclasses of valuation functions that express no-complementarities. Our main results concern their approximate learnability in the distributional learning (PAC-style) setting. We provide nearly tight lower and upper bounds of $\tildeΘ(n^{1/2})$ on the approximation factor for learning XOS and subadditive valuations, both widely studied superclasses of submodular valuations. Interestingly, we show that the $\tildeΩ(n^{1/2})$ lower bound can be circumvented for XOS functions of polynomial complexity; we provide an algorithm for learning the class of XOS valuations with a representation of polynomial size achieving an $O(n^{\eps})$ approximation factor in time $O(n^{1/\eps})$ for any $\eps > 0$. This highlights the importance of considering the complexity of the target function for polynomial time learning. We also provide new learning results for interesting subclasses of submodular functions. Our upper bounds for distributional learning leverage novel structural results for all these valuation classes. We show that many of these results provide new learnability results in the Goemans et al. model (SODA 2009) of approximate learning everywhere via value queries. We also introduce a new model that is more realistic in economic settings, in which the learner can set prices and observe purchase decisions at these prices rather than observing the valuation function directly. In this model, most of our upper bounds continue to hold despite the fact that the learner receives less information (both for learning in the distributional setting and with value queries), while our lower bounds naturally extend.
E- Learning: An effective pedagogical tool for learning
Venue: arXiv cs.CY 2011
Year: 2011

In the info-tech age E-Methods of learning are becoming the most important vehicle in disseminating knowledge in higher education institutions. This sector is growing and changing at a rapid speed due to developments in technologies. But teaching is an art. Can there be fun learning with raw and dry technology? How can we make the best use of E- Methods, can we make the required information and data available to the students in a flexible manner, at ease all the time? What are the advantages of traditional methods of teaching and learning? Is E-learning a progressive stage incubating all the benefits of the Manual learning or it is only a window dressing on the face of advancement? Can we convert the boring, tedious subjects into interactive, monotony breaking joyous learning? In this paper the researchers have focused on the modernization of E- Pedagogy vis-a-vis the traditional method of learning. They have highlighted the effectiveness of using the E- learning elements and various E- Methods. This work has used the decision tree algorithms particularly Classifiers.trees.J48 The obtained results show that using online examination attribute plays major role in increasing the average grade of the class in higher education. The novelty of this work is that the researchers have focused on the teaching methodology used by the faculty members and the tools available in the universities. We believe that this work will play a constructive role in building higher education system. Our generated rules/output can be used by the decision makers in the improvement of higher education system processes.
Banded Householder representation of linear subspaces
Venue: arXiv cs.NA 2011
Year: 2011

We show how to compactly represent any $n$-dimensional subspace of $R^m$ as a banded product of Householder reflections using $n(m - n)$ floating point numbers. This is optimal since these subspaces form a Grassmannian space $Gr_n(m)$ of dimension $n(m - n)$. The representation is stable and easy to compute: any matrix can be factored into the product of a banded Householder matrix and a square matrix using two to three QR decompositions.
Coordinating Interfering Transmissions in Cooperative Wireless LANs
Venue: arXiv cs.NI 2011
Year: 2011

In this paper we present a cooperative medium access control (MAC) protocol that is designed for a physical layer that can decode interfering transmissions in distributed wireless networks. The proposed protocol pro-actively enforces two independent packet transmissions to interfere in a controlled and cooperative manner. The protocol ensures that when a node desires to transmit a unicast packet, regardless of the destination, it coordinates with minimal overhead with relay nodes in order to concurrently transmit over the wireless channel with a third node. The relay is responsible for allowing packets from the two selected nodes to interfere only when the desired packets can be decoded at the appropriate destinations and increase the sum-rate of the cooperative transmission. In case this is not feasible, classic cooperative or direct transmission is adopted. To enable distributed, uncoordinated, and adaptive operation of the protocol, a relay selection mechanism is introduced so that the optimal relay is selected dynamically and depending on the channel conditions. The most important advantage of the protocol is that interfering transmissions can originate from completely independent unicast transmissions from two senders. We present simulation results that validate the efficacy of our proposed scheme in terms of throughput and delay.
Domain-specific Languages in a Finite Domain Constraint Programming System
Venue: arXiv cs.AI 2011
Year: 2011

In this paper, we present domain-specific languages (DSLs) that we devised for their use in the implementation of a finite domain constraint programming system, available as library(clpfd) in SWI-Prolog and YAP-Prolog. These DSLs are used in propagator selection and constraint reification. In these areas, they lead to concise specifications that are easy to read and reason about. At compilation time, these specifications are translated to Prolog code, reducing interpretative run-time overheads. The devised languages can be used in the implementation of other finite domain constraint solvers as well and may contribute to their correctness, conciseness and efficiency.
Adaptive Locomotion of Multibody Snake-like Robot
Venue: arXiv cs.RO 2011
Year: 2011

This paper represents an adaptive rhythmic control for a snake-like robot with 25 degrees of freedom. The adaptive gait control is implemented in algorithmic way in simulation and on a real robot. We investigated behavioral and energetic properties of this control and a dynamics of different body segments. It turned out that despite using homogeneous generators, physical constraints have an inhomogeneous impact on neighbor body segments. By analytical modeling of such dynamics, it may result in heterogeneous coupling of oscillators for a rhythmic control and impact scalability and synchronization effects of gait pattern generators.
Coprocessor - a Standalone SAT Preprocessor
Venue: arXiv cs.AI 2011
Year: 2011

In this work a stand-alone preprocessor for SAT is presented that is able to perform most of the known preprocessing techniques. Preprocessing a formula in SAT is important for performance since redundancy can be removed. The preprocessor is part of the SAT solver riss and is called Coprocessor. Not only riss, but also MiniSat 2.2 benefit from it, because the SatELite preprocessor of MiniSat does not implement recent techniques. By using more advanced techniques, Coprocessor is able to reduce the redundancy in a formula further and improves the overall solving performance.
Assessing the Feasibility of Developing a Federated ERP System
Venue: arXiv cs.SE 2011
Year: 2011

In past years ERP Systems have become one of the main components within the corporate IT structure. Several problems exist around implementing and operating these systems within companies. In the literature one can find several studies about the problems arising during the implementation of an ERP system. The main problem areas are around the complexity of ERP systems. One vision to overcome some of these problems is federated ERP. Federated ERP systems are built of components from different vendors, which are distributed within a network. All components act as one single ERP system from the user perspective. The decreased complexity of such a system would require lower installation and maintenance cost. Additional, only the components which are needed to cover the company's business processes would be used. Several theories around this concept exist, but a feasibility assessment of developing a federated ERP system has not been done yet. Based on a literary analysis of existing methods for feasibility studies, this paper is applying strategic planning concepts and referential data from the traditional ERP development to provide a first assessment of the overall feasibility of developing a platform for federated ERP systems. An analytical hierarchical approach is used to define effort and effect related criteria and their domain values. The assessment as the criteria is done in comparison to the development of a classical ERP system. Using the developed criteria, a net present value calculation is done. The calculation of the net present value is done on an overall, not company specific level. In order to estimate the weighted average cost of capital, the values from successful software companies are used as a baseline. Additional potential risks and obstacles are identified for further clarification.
aspcud: A Linux Package Configuration Tool Based on Answer Set Programming
Venue: arXiv cs.AI 2011
Year: 2011

We present the Linux package configuration tool aspcud based on Answer Set Programming. In particular, we detail aspcud's preprocessor turning a CUDF specification into a set of logical facts.
Discrete Conservation Law on Curved Surfaces
Venue: arXiv cs.CG 2011
Year: 2011

In this paper we shall introduce a simple, effective numerical method for finding differential operators for scalar and vector-valued functions on surfaces. The key idea of our algorithm is to develop an intrinsic and unified way to compute directly the partial derivatives of functions defined on triangular meshes which are the discretization of regular surfaces under consideration. Most importantly, the divergence theorem and conservation laws on triangular meshes are fulfilled.
Improving the recall of decentralised linked data querying through implicit knowledge
Venue: arXiv cs.DB 2011
Year: 2011

Aside from crawling, indexing, and querying RDF data centrally, Linked Data principles allow for processing SPARQL queries on-the-fly by dereferencing URIs. Proposed link-traversal query approaches for Linked Data have the benefits of up-to-date results and decentralised (i.e., client-side) execution, but operate on incomplete knowledge available in dereferenced documents, thus affecting recall. In this paper, we investigate how implicit knowledge - specifically that found through owl:sameAs and RDFS reasoning - can improve the recall in this setting. We start with an empirical analysis of a large crawl featuring 4 m Linked Data sources and 1.1 g quadruples: we (1) measure expected recall by only considering dereferenceable information, (2) measure the improvement in recall given by considering rdfs:seeAlso links as previous proposals did. We further propose and measure the impact of additionally considering (3) owl:sameAs links, and (4) applying lightweight RDFS reasoning (specifically ρDF) for finding more results, relying on static schema information. We evaluate our methods for live queries over our crawl.