OpenRaiser/Intern-Atlas huggingface dataset:
Hybrid Rules with Well-Founded Semantics
Venue: arXiv cs.LO 2009
Year: 2009

A general framework is proposed for integration of rules and external first order theories. It is based on the well-founded semantics of normal logic programs and inspired by ideas of Constraint Logic Programming (CLP) and constructive negation for logic programs. Hybrid rules are normal clauses extended with constraints in the bodies; constraints are certain formulae in the language of the external theory. A hybrid program is a pair of a set of hybrid rules and an external theory. Instances of the framework are obtained by specifying the class of external theories, and the class of constraints. An example instance is integration of (non-disjunctive) Datalog with ontologies formalized as description logics. The paper defines a declarative semantics of hybrid programs and a goal-driven formal operational semantics. The latter can be seen as a generalization of SLS-resolution. It provides a basis for hybrid implementations combining Prolog with constraint solvers. Soundness of the operational semantics is proven. Sufficient conditions for decidability of the declarative semantics, and for completeness of the operational semantics are given.
Fixed-parameter tractability and lower bounds for stabbing problems
Venue: arXiv cs.CG 2009
Year: 2009

We study the following general stabbing problem from a parameterized complexity point of view: Given a set $\mathcal S$ of $n$ translates of an object in $\Rd$, find a set of $k$ lines with the property that every object in $\mathcal S$ is ''stabbed'' (intersected) by at least one line. We show that when $S$ consists of axis-parallel unit squares in $\Rtwo$ the (decision) problem of stabbing $S$ with axis-parallel lines is W[1]-hard with respect to $k$ (and thus, not fixed-parameter tractable unless FPT=W[1]) while it becomes fixed-parameter tractable when the squares are disjoint. We also show that the problem of stabbing a set of disjoint unit squares in $\Rtwo$ with lines of arbitrary directions is W[1]--hard with respect to $k$. Several generalizations to other types of objects and lines with arbitrary directions are also presented. Finally, we show that deciding whether a set of unit balls in $\Rd$ can be stabbed by one line is W[1]--hard with respect to the dimension $d$.
A Type System Theory for Higher-Order Intensional Logic Support for Variable Bindings in Hybrid Intensional-Imperative Programs in GIPSY
Venue: arXiv cs.LO 2009
Year: 2009

We describe a type system for a platform called the General Intensional Programming System (GIPSY), designed to support intensional programming languages built upon intensional logic and their imperative counter-parts for the intensional execution model. In GIPSY, the type system glues the static and dynamic typing between intensional and imperative languages in its compiler and run-time environments to support the intensional evaluation of expressions written in various dialects of the intensional programming language Lucid. The intensionality makes expressions to explicitly take into the account a multidimensional context of evaluation with the context being a first-class value that serves a number of applications that need the notion of context to proceed. We describe and discuss the properties of such a type system and the related type theory as well as particularities of the semantics, design and implementation of the GIPSY type system.
Service-oriented Context-aware Framework
Venue: arXiv cs.SE 2009
Year: 2009

Location- and context-aware services are emerging technologies in mobile and desktop environments, however, most of them are difficult to use and do not seem to be beneficial enough. Our research focuses on designing and creating a service-oriented framework that helps location- and context-aware, client-service type application development and use. Location information is combined with other contexts such as the users' history, preferences and disabilities. The framework also handles the spatial model of the environment (e.g. map of a room or a building) as a context. The framework is built on a semantic backend where the ontologies are represented using the OWL description language. The use of ontologies enables the framework to run inference tasks and to easily adapt to new context types. The framework contains a compatibility layer for positioning devices, which hides the technical differences of positioning technologies and enables the combination of location data of various sources.
Towards Activity Context using Software Sensors
Venue: arXiv cs.OH 2009
Year: 2009

Service-Oriented Computing delivers the promise of configuring and reconfiguring software systems to address user's needs in a dynamic way. Context-aware computing promises to capture the user's needs and hence the requirements they have on systems. The marriage of both can deliver ad-hoc software solutions relevant to the user in the most current fashion. However, here it is a key to gather information on the users' activity (that is what they are doing). Traditionally any context sensing was conducted with hardware sensors. However, software can also play the same role and in some situations will be more useful to sense the activity of the user. Furthermore they can make use of the fact that Service-oriented systems exchange information through standard protocols. In this paper we discuss our proposed approach to sense the activity of the user making use of software.
Two generalizations on the minimum Hamming distance of repeated-root constacyclic codes
Venue: arXiv cs.IT 2009
Year: 2009

We study constacyclic codes, of length $np^s$ and $2np^s$, that are generated by the polynomials $(x^n + γ)^{\ell}$ and $(x^n - ξ)^i(x^n + ξ)^j$\ respectively, where $x^n + γ$, $x^n - ξ$ and $x^n + ξ$ are irreducible over the alphabet $\F_{p^a}$. We generalize the results of [5], [6] and [7] by computing the minimum Hamming distance of these codes. As a particular case, we determine the minimum Hamming distance of cyclic and negacyclic codes, of length $2p^s$, over a finite field of characteristic $p$.
Rough Set Model for Discovering Hybrid Association Rules
Venue: arXiv cs.DB 2009
Year: 2009

In this paper, the mining of hybrid association rules with rough set approach is investigated as the algorithm RSHAR.The RSHAR algorithm is constituted of two steps mainly. At first, to join the participant tables into a general table to generate the rules which is expressing the relationship between two or more domains that belong to several different tables in a database. Then we apply the mapping code on selected dimension, which can be added directly into the information system as one certain attribute. To find the association rules, frequent itemsets are generated in second step where candidate itemsets are generated through equivalence classes and also transforming the mapping code in to real dimensions. The searching method for candidate itemset is similar to apriori algorithm. The analysis of the performance of algorithm has been carried out.
A Rough Sets Partitioning Model for Mining Sequential Patterns with Time Constraint
Venue: arXiv cs.DB 2009
Year: 2009

Now a days, data mining and knowledge discovery methods are applied to a variety of enterprise and engineering disciplines to uncover interesting patterns from databases. The study of Sequential patterns is an important data mining problem due to its wide applications to real world time dependent databases. Sequential patterns are inter-event patterns ordered over a time-period associated with specific objects under study. Analysis and discovery of frequent sequential patterns over a predetermined time-period are interesting data mining results, and can aid in decision support in many enterprise applications. The problem of sequential pattern mining poses computational challenges as a long frequent sequence contains enormous number of frequent subsequences. Also useful results depend on the right choice of event window. In this paper, we have studied the problem of sequential pattern mining through two perspectives, one the computational aspect of the problem and the other is incorporation and adjustability of time constraint. We have used Indiscernibility relation from theory of rough sets to partition the search space of sequential patterns and have proposed a novel algorithm that allows previsualization of patterns and allows adjustment of time constraint prior to execution of mining task. The algorithm Rough Set Partitioning is at least ten times faster than the naive time constraint based sequential pattern mining algorithm GSP. Besides this an additional knowledge of time interval of sequential patterns is also determined with the method.
Robust Watermarking in Multiresolution Walsh-Hadamard Transform
Venue: arXiv cs.CR 2009
Year: 2009

In this paper, a newer version of Walsh-Hadamard Transform namely multiresolution Walsh-Hadamard Transform (MR-WHT) is proposed for images. Further, a robust watermarking scheme is proposed for copyright protection using MRWHT and singular value decomposition. The core idea of the proposed scheme is to decompose an image using MR-WHT and then middle singular values of high frequency sub-band at the coarsest and the finest level are modified with the singular values of the watermark. Finally, a reliable watermark extraction scheme is developed for the extraction of the watermark from the distorted image. The experimental results show better visual imperceptibility and resiliency of the proposed scheme against intentional or un-intentional variety of attacks.
Verifying the Interplay of Authorization Policies and Workflow in Service-Oriented Architectures (Full version)
Venue: arXiv cs.CR 2009
Year: 2009

A widespread design approach in distributed applications based on the service-oriented paradigm, such as web-services, consists of clearly separating the enforcement of authorization policies and the workflow of the applications, so that the interplay between the policy level and the workflow level is abstracted away. While such an approach is attractive because it is quite simple and permits one to reason about crucial properties of the policies under consideration, it does not provide the right level of abstraction to specify and reason about the way the workflow may interfere with the policies, and vice versa. For example, the creation of a certificate as a side effect of a workflow operation may enable a policy rule to fire and grant access to a certain resource; without executing the operation, the policy rule should remain inactive. Similarly, policy queries may be used as guards for workflow transitions. In this paper, we present a two-level formal verification framework to overcome these problems and formally reason about the interplay of authorization policies and workflow in service-oriented architectures. This allows us to define and investigate some verification problems for SO applications and give sufficient conditions for their decidability.
Fast Probabilistic Ranking under x-Relation Model
Venue: arXiv cs.DB 2009
Year: 2009

The probabilistic top-k queries based on the interplay of score and probability, under the possible worlds semantic, become an important research issue that considers both score and uncertainty on the same basis. In the literature, many different probabilistic top-k queries are proposed. Almost all of them need to compute the probability of a tuple t_i to be ranked at the j-th position across the entire set of possible worlds. The cost of such computing is the dominant cost and is known as O(kn^2), where n is the size of dataset. In this paper, we propose a new novel algorithm that computes such probability in O(kn).
Towards the Patterns of Hard CSPs with Association Rule Mining
Venue: arXiv cs.DB 2009
Year: 2009

The hardness of finite domain Constraint Satisfaction Problems (CSPs) is a very important research area in Constraint Programming (CP) community. However, this problem has not yet attracted much attention from the researchers in the association rule mining community. As a popular data mining technique, association rule mining has an extremely wide application area and it has already been successfully applied to many interdisciplines. In this paper, we study the association rule mining techniques and propose a cascaded approach to extract the interesting patterns of the hard CSPs. As far as we know, this problem is investigated with the data mining techniques for the first time. Specifically, we generate the random CSPs and collect their characteristics by solving all the CSP instances, and then apply the data mining techniques on the data set and further to discover the interesting patterns of the hardness of the randomly generated CSPs
AFPTAS results for common variants of bin packing: A new method to handle the small items
Venue: arXiv cs.DS 2009
Year: 2009

We consider two well-known natural variants of bin packing, and show that these packing problems admit asymptotic fully polynomial time approximation schemes (AFPTAS). In bin packing problems, a set of one-dimensional items of size at most 1 is to be assigned (packed) to subsets of sum at most 1 (bins). It has been known for a while that the most basic problem admits an AFPTAS. In this paper, we develop methods that allow to extend this result to other variants of bin packing. Specifically, the problems which we study in this paper, for which we design asymptotic fully polynomial time approximation schemes, are the following. The first problem is "Bin packing with cardinality constraints", where a parameter k is given, such that a bin may contain up to k items. The goal is to minimize the number of bins used. The second problem is "Bin packing with rejection", where every item has a rejection penalty associated with it. An item needs to be either packed to a bin or rejected, and the goal is to minimize the number of used bins plus the total rejection penalty of unpacked items. This resolves the complexity of two important variants of the bin packing problem. Our approximation schemes use a novel method for packing the small items. This new method is the core of the improved running times of our schemes over the running times of the previous results, which are only asymptotic polynomial time approximation schemes (APTAS).
Incidence Handling and Response System
Venue: arXiv cs.CR 2009
Year: 2009

A computer network can be attacked in a number of ways. The security-related threats have become not only numerous but also diverse and they may also come in the form of blended attacks. It becomes difficult for any security system to block all types of attacks. This gives rise to the need of an incidence handling capability which is necessary for rapidly detecting incidents, minimizing loss and destruction, mitigating the weaknesses that were exploited and restoring the computing services. Incidence response has always been an important aspect of information security but it is often overlooked by security administrators. in this paper, we propose an automated system which will handle the security threats and make the computer network capable enough to withstand any kind of attack. we also present the state-of-the-art technology in computer, network and software which is required to build such a system.
Restricted Global Grammar Constraints
Venue: arXiv cs.AI 2009
Year: 2009

We investigate the global GRAMMAR constraint over restricted classes of context free grammars like deterministic and unambiguous context-free grammars. We show that detecting disentailment for the GRAMMAR constraint in these cases is as hard as parsing an unrestricted context free grammar.We also consider the class of linear grammars and give a propagator that runs in quadratic time. Finally, to demonstrate the use of linear grammars, we show that a weighted linear GRAMMAR constraint can efficiently encode the EDITDISTANCE constraint, and a conjunction of the EDITDISTANCE constraint and the REGULAR constraint
Measurable & Scalable NFRs using Fuzzy Logic and Likert Scale
Venue: arXiv cs.SE 2009
Year: 2009

Most of the research related to Non Functional Requirements (NFRs) have presented NFRs frameworks by integrating non functional requirements with functional requirements while we proposed that measurement of NFRs is possible e.g. cost and performance and NFR like usability can be scaled. Our novel hybrid approach integrates three things rather than two i.e. Functional Requirements (FRs), Measurable NFRs (M-NFRs) and Scalable NFRs (S-NFRs). We have also found the use of Fuzzy Logic and Likert Scale effective for handling of discretely measurable as well as scalable NFRs as these techniques can provide a simple way to arrive at a discrete or scalable NFR in contrast to vague, ambiguous, imprecise, noisy or missing NFR. Our approach can act as baseline for new NFR and aspect oriented frameworks by using all types of UML diagrams.
Citing and Reading Behaviours in High-Energy Physics. How a Community Stopped Worrying about Journals and Learned to Love Repositories
Venue: arXiv cs.DL 2009
Year: 2009

Contemporary scholarly discourse follows many alternative routes in addition to the three-century old tradition of publication in peer-reviewed journals. The field of High- Energy Physics (HEP) has explored alternative communication strategies for decades, initially via the mass mailing of paper copies of preliminary manuscripts, then via the inception of the first online repositories and digital libraries. This field is uniquely placed to answer recurrent questions raised by the current trends in scholarly communication: is there an advantage for scientists to make their work available through repositories, often in preliminary form? Is there an advantage to publishing in Open Access journals? Do scientists still read journals or do they use digital repositories? The analysis of citation data demonstrates that free and immediate online dissemination of preprints creates an immense citation advantage in HEP, whereas publication in Open Access journals presents no discernible advantage. In addition, the analysis of clickstreams in the leading digital library of the field shows that HEP scientists seldom read journals, preferring preprints instead.
The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
Venue: arXiv cs.FL 2009
Year: 2009

In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Sigma is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Sigma*? In the case of testing universality for factors of languages represented by DFA's, we find an interesting connection to Cerny's conjecture on synchronizing words.
A new model of artificial neuron: cyberneuron and its use
Venue: arXiv cs.NE 2009
Year: 2009

This article describes a new type of artificial neuron, called the authors "cyberneuron". Unlike classical models of artificial neurons, this type of neuron used table substitution instead of the operation of multiplication of input values for the weights. This allowed to significantly increase the information capacity of a single neuron, but also greatly simplify the process of learning. Considered an example of the use of "cyberneuron" with the task of detecting computer viruses.
Generating functions of Chebyshev-like polynomials
Venue: arXiv cs.SC 2009
Year: 2009

In this short note, we give simple proofs of several results and conjectures formulated by Stolarsky and Tran concerning generating functions of some families of Chebyshev-like polynomials.
Steganography in Handling Oversized IP Packets
Venue: arXiv cs.CR 2009
Year: 2009

This paper identifies new class of network steganography methods that utilize mechanisms to handle oversized packets in IP networks: IP fragmentation, PMTUD (Path MTU Discovery) and PLPMTUD (Packetization Layer Path MTU Discovery). In particular, we propose two new steganographic methods and two extensions of existing ones. We show how IP fragmentation simplifies utilizing steganographic methods which requires transmitter-receiver synchronization. We present how mentioned mechanisms can be used to enable hidden communication for both versions of IP protocol: 4 and 6. Also the detection of the proposed methods is enclosed in this paper.
Agent based Model for providing optimized, synchronized and failure free execution of workflow process
Venue: arXiv cs.SE 2009
Year: 2009

The main objective of this paper is to provide an optimized solution and algorithm for the execution of a workflow process by ensuring the data consistency, correctness, completeness among various tasks involved. The solution proposed provides a synchronized and failure free flow of execution among various tasks involved in a workflow process. A synchronizing agent is bound at a very low level, i.e. with the workflow activity or task to get the desired goals to be done and an algorithm is provided to show the execution of workflow process completely.
Computational Scenario-based Capability Planning
Venue: arXiv cs.NE 2009
Year: 2009

Scenarios are pen-pictures of plausible futures, used for strategic planning. The aim of this investigation is to expand the horizon of scenario-based planning through computational models that are able to aid the analyst in the planning process. The investigation builds upon the advances of Information and Communication Technology (ICT) to create a novel, flexible and customizable computational capability-based planning methodology that is practical and theoretically sound. We will show how evolutionary computation, in particular evolutionary multi-objective optimization, can play a central role - both as an optimizer and as a source for innovation.
Generalized Collective Inference with Symmetric Clique Potentials
Venue: arXiv cs.AI 2009
Year: 2009

Collective graphical models exploit inter-instance associative dependence to output more accurate labelings. However existing models support very limited kind of associativity which restricts accuracy gains. This paper makes two major contributions. First, we propose a general collective inference framework that biases data instances to agree on a set of {\em properties} of their labelings. Agreement is encouraged through symmetric clique potentials. We show that rich properties leads to bigger gains, and present a systematic inference procedure for a large class of such properties. The procedure performs message passing on the cluster graph, where property-aware messages are computed with cluster specific algorithms. This provides an inference-only solution for domain adaptation. Our experiments on bibliographic information extraction illustrate significant test error reduction over unseen domains. Our second major contribution consists of algorithms for computing outgoing messages from clique clusters with symmetric clique potentials. Our algorithms are exact for arbitrary symmetric potentials on binary labels and for max-like and majority-like potentials on multiple labels. For majority potentials, we also provide an efficient Lagrangian Relaxation based algorithm that compares favorably with the exact algorithm. We present a 13/15-approximation algorithm for the NP-hard Potts potential, with runtime sub-quadratic in the clique size. In contrast, the best known previous guarantee for graphs with Potts potentials is only 1/2. We empirically show that our method for Potts potentials is an order of magnitude faster than the best alternatives, and our Lagrangian Relaxation based algorithm for majority potentials beats the best applicable heuristic -- ICM.