OpenRaiser/Intern-Atlas huggingface dataset:
A Complete and Terminating Execution Model for Constraint Handling Rules
Venue: arXiv cs.LO 2010
Year: 2010

We observe that the various formulations of the operational semantics of Constraint Handling Rules proposed over the years fall into a spectrum ranging from the analytical to the pragmatic. While existing analytical formulations facilitate program analysis and formal proofs of program properties, they cannot be implemented as is. We propose a novel operational semantics, which has a strong analytical foundation, while featuring a terminating execution model. We prove its soundness and completeness with respect to existing analytical formulations and we provide an implementation in the form of a source-to-source transformation to CHR with rule priorities.
Loop Formulas for Description Logic Programs
Venue: arXiv cs.AI 2010
Year: 2010

Description Logic Programs (dl-programs) proposed by Eiter et al. constitute an elegant yet powerful formalism for the integration of answer set programming with description logics, for the Semantic Web. In this paper, we generalize the notions of completion and loop formulas of logic programs to description logic programs and show that the answer sets of a dl-program can be precisely captured by the models of its completion and loop formulas. Furthermore, we propose a new, alternative semantics for dl-programs, called the {\em canonical answer set semantics}, which is defined by the models of completion that satisfy what are called canonical loop formulas. A desirable property of canonical answer sets is that they are free of circular justifications. Some properties of canonical answer sets are also explored.
Decoupling data dissemination from the mobile sink's trajectory in wireless sensor networks: Current Research and Open Issues
Venue: arXiv cs.NI 2010
Year: 2010

In this report, firstly, we presents state of the art survey on Data Management and Data Dissemination techniques with Mobile Sink. Moreover we classify these techniques into two ample sub-categories. Under this classification, we identify, review, compare, and highlight these techniques and their pros and cons. We do a SWOT (Strength, Weaknesses, Opportunities, Threats) analysis of each scheme. We also discuss where each scheme is appropriate. Secondly, we presents a new distributed data management scheme which is based upon Random Walk Based Membership Service to facilitate Data Dissemination in Mobile Sink based Wireless Sensor Networks. Our proposed scheme efficiently deals with the aforementioned problems and we also compare the characteristics of our proposed scheme with the state-of-the-art data-dissemination schemes. We propose using Random Walks (RWs) with uniformly distributed views to disseminate data through the WSN with a controlled overhead. This is performed by the use of a Random Walk Based Membership Service - the RaWMS. Our proposal solves then the problems generated when (a) all nodes are storage motes, being no aggregation performed (b) one center node plays the role of storage mote and aggregates data from all the other nodes (c) replication is performed on all nodes in the network. To the best of our knowledge, we are the first to propose an efficient data dissemination approach (in terms of overhead, adaptiveness and representativeness) to allow a mobile sink to gather a representative view of the monitored region covered by n sensor nodes by only visiting any m nodes, where hopefully m << n.
Human Daily Activities Indexing in Videos from Wearable Cameras for Monitoring of Patients with Dementia Diseases
Venue: arXiv cs.MM 2010
Year: 2010

Our research focuses on analysing human activities according to a known behaviorist scenario, in case of noisy and high dimensional collected data. The data come from the monitoring of patients with dementia diseases by wearable cameras. We define a structural model of video recordings based on a Hidden Markov Model. New spatio-temporal features, color features and localization features are proposed as observations. First results in recognition of activities are promising.
Fast Moment Estimation in Data Streams in Optimal Space
Venue: arXiv cs.DS 2010
Year: 2010

We give a space-optimal algorithm with update time O(log^2(1/eps)loglog(1/eps)) for (1+eps)-approximating the pth frequency moment, 0 < p < 2, of a length-n vector updated in a data stream. This provides a nearly exponential improvement in the update time complexity over the previous space-optimal algorithm of [Kane-Nelson-Woodruff, SODA 2010], which had update time Omega(1/eps^2).
Building Blocks Propagation in Quantum-Inspired Genetic Algorithm
Venue: arXiv cs.NE 2010
Year: 2010

This paper presents an analysis of building blocks propagation in Quantum-Inspired Genetic Algorithm, which belongs to a new class of metaheuristics drawing their inspiration from both biological evolution and unitary evolution of quantum systems. The expected number of quantum chromosomes matching a schema has been analyzed and a random variable corresponding to this issue has been introduced. The results have been compared with Simple Genetic Algorithm. Also, it has been presented how selected binary quantum chromosomes cover a domain of one-dimensional fitness function.
Pushdown Control-Flow Analysis of Higher-Order Programs
Venue: arXiv cs.PL 2010
Year: 2010

Context-free approaches to static analysis gain precision over classical approaches by perfectly matching returns to call sites---a property that eliminates spurious interprocedural paths. Vardoulakis and Shivers's recent formulation of CFA2 showed that it is possible (if expensive) to apply context-free methods to higher-order languages and gain the same boost in precision achieved over first-order programs. To this young body of work on context-free analysis of higher-order programs, we contribute a pushdown control-flow analysis framework, which we derive as an abstract interpretation of a CESK machine with an unbounded stack. One instantiation of this framework marks the first polyvariant pushdown analysis of higher-order programs; another marks the first polynomial-time analysis. In the end, we arrive at a framework for control-flow analysis that can efficiently compute pushdown generalizations of classical control-flow analyses.
The Multiple Permutation Problem and Some Conjectures
Venue: arXiv cs.DM 2010
Year: 2010

In this paper, we proposed an interesting problem that might be classified into enumerative combinatorics. Featuring a distinctive two-fold dependence upon the sequences' terms, our problem can be really difficult, which calls for novel approaches to work it out for any given pair $(m,n)$. Complete or partial solutions for $m=2, 3$ with smaller $n$'s are listed. Moreover, we have proved the necessary condition for $p(m,n) \neq 0$ and suggested an elegant asymptotic formula for $p(2,n)$. In addition, several challenging conjectures are provided, together with concise comments.
Public Infrastructure for Monte Carlo Simulation: publicMC@BATAN
Venue: arXiv cs.DC 2010
Year: 2010

The first cluster-based public computing for Monte Carlo simulation in Indonesia is introduced. The system has been developed to enable public to perform Monte Carlo simulation on a parallel computer through an integrated and user friendly dynamic web interface. The beta version, so called publicMC@BATAN, has been released and implemented for internal users at the National Nuclear Energy Agency (BATAN). In this paper the concept and architecture of publicMC@BATAN are presented.
MIMO Wiretap Channels with Arbitrarily Varying Eavesdropper Channel States
Venue: arXiv cs.IT 2010
Year: 2010

In this work, a class of information theoretic secrecy problems is addressed where the eavesdropper channel states are completely unknown to the legitimate parties. In particular, MIMO wiretap channel models are considered where the channel of the eavesdropper is arbitrarily varying over time. Assuming that the number of antennas of the eavesdropper is limited, the secrecy rate of the MIMO wiretap channel in the sense of strong secrecy is derived, and shown to match with the converse in secure degrees of freedom. It is proved that there exists a universal coding scheme that secures the confidential message against any sequence of channel states experienced by the eavesdropper. This yields the conclusion that secure communication is possible regardless of the location or channel states of (potentially infinite number of) eavesdroppers. Additionally, it is observed that, the present setting renders the secrecy capacity problems for multi-terminal wiretap-type channels more tractable as compared the case with full or partial knowledge of eavesdropper channel states. To demonstrate this observation, secure degrees of freedom regions are derived for the Gaussian MIMO multiple access wiretap channel (MIMO MAC-WT) and the Gaussian MIMO broadcast wiretap channel (MIMO BC-WT) where the transmitter(s) and the intended receiver(s) have the same number of antennas.
Decentralized Dynamic Hop Selection and Power Control in Cognitive Multi-hop Relay Systems
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we consider a cognitive multi-hop relay secondary user (SU) system sharing the spectrum with some primary users (PU). The transmit power as well as the hop selection of the cognitive relays can be dynamically adapted according to the local (and causal) knowledge of the instantaneous channel state information (CSI) in the multi-hop SU system. We shall determine a low complexity, decentralized algorithm to maximize the average end-to-end throughput of the SU system with dynamic spatial reuse. The problem is challenging due to the decentralized requirement as well as the causality constraint on the knowledge of CSI. Furthermore, the problem belongs to the class of stochastic Network Utility Maximization (NUM) problems which is quite challenging. We exploit the time-scale difference between the PU activity and the CSI fluctuations and decompose the problem into a master problem and subproblems. We derive an asymptotically optimal low complexity solution using divide-and-conquer and illustrate that significant performance gain can be obtained through dynamic hop selection and power control. The worst case complexity and memory requirement of the proposed algorithm is O(M^2) and O(M^3) respectively, where $M$ is the number of SUs.
The System Kato: Detecting Cases of Plagiarism for Answer-Set Programs
Venue: arXiv cs.LO 2010
Year: 2010

Plagiarism detection is a growing need among educational institutions and solutions for different purposes exist. An important field in this direction is detecting cases of source-code plagiarism. In this paper, we present the tool Kato for supporting the detection of this kind of plagiarism in the area of answer-set programming (ASP). Currently, the tool is implemented for DLV programs but it is designed to handle other logic-programming dialects as well. We review the basic features of Kato, introduce its theoretical underpinnings, and discuss an application of Kato for plagiarism detection in the context of courses on logic programming at the Vienna University of Technology.
Simplified Distributed Programming with Micro Objects
Venue: arXiv cs.DC 2010
Year: 2010

Developing large-scale distributed applications can be a daunting task. object-based environments have attempted to alleviate problems by providing distributed objects that look like local objects. We advocate that this approach has actually only made matters worse, as the developer needs to be aware of many intricate internal details in order to adequately handle partial failures. The result is an increase of application complexity. We present an alternative in which distribution transparency is lessened in favor of clearer semantics. In particular, we argue that a developer should always be offered the unambiguous semantics of local objects, and that distribution comes from copying those objects to where they are needed. We claim that it is often sufficient to provide only small, immutable objects, along with facilities to group objects into clusters.
CREOLE: a Universal Language for Creating, Requesting, Updating and Deleting Resources
Venue: arXiv cs.PL 2010
Year: 2010

In the context of Service-Oriented Computing, applications can be developed following the REST (Representation State Transfer) architectural style. This style corresponds to a resource-oriented model, where resources are manipulated via CRUD (Create, Request, Update, Delete) interfaces. The diversity of CRUD languages due to the absence of a standard leads to composition problems related to adaptation, integration and coordination of services. To overcome these problems, we propose a pivot architecture built around a universal language to manipulate resources, called CREOLE, a CRUD Language for Resource Edition. In this architecture, scripts written in existing CRUD languages, like SQL, are compiled into Creole and then executed over different CRUD interfaces. After stating the requirements for a universal language for manipulating resources, we formally describe the language and informally motivate its definition with respect to the requirements. We then concretely show how the architecture solves adaptation, integration and coordination problems in the case of photo management in Flickr and Picasa, two well-known service-oriented applications. Finally, we propose a roadmap for future work.
An Empirical Study of Borda Manipulation
Venue: arXiv cs.AI 2010
Year: 2010

We study the problem of coalitional manipulation in elections using the unweighted Borda rule. We provide empirical evidence of the manipulability of Borda elections in the form of two new greedy manipulation algorithms based on intuitions from the bin-packing and multiprocessor scheduling domains. Although we have not been able to show that these algorithms beat existing methods in the worst-case, our empirical evaluation shows that they significantly outperform the existing method and are able to find optimal manipulations in the vast majority of the randomly generated elections that we tested. These empirical results provide further evidence that the Borda rule provides little defense against coalitional manipulation.
Where are the hard manipulation problems?
Venue: arXiv cs.AI 2010
Year: 2010

One possible escape from the Gibbard-Satterthwaite theorem is computational complexity. For example, it is NP-hard to compute if the STV rule can be manipulated. However, there is increasing concern that such results may not re ect the difficulty of manipulation in practice. In this tutorial, I survey recent results in this area.
Bayesian Network Based XP Process Modelling
Venue: arXiv cs.SE 2010
Year: 2010

A Bayesian Network based mathematical model has been used for modelling Extreme Programming software development process. The model is capable of predicting the expected finish time and the expected defect rate for each XP release. Therefore, it can be used to determine the success/failure of any XP Project. The model takes into account the effect of three XP practices, namely: Pair Programming, Test Driven Development and Onsite Customer practices. The model's predictions were validated against two case studies. Results show the precision of our model especially in Predicting the project finish time.
Comparison Of Modified Dual Ternary Indexing And Multi-Key Hashing Algorithms For Music Information Retrieval
Venue: arXiv cs.IR 2010
Year: 2010

In this work we have compared two indexing algorithms that have been used to index and retrieve Carnatic music songs. We have compared a modified algorithm of the Dual ternary indexing algorithm for music indexing and retrieval with the multi-key hashing indexing algorithm proposed by us. The modification in the dual ternary algorithm was essential to handle variable length query phrase and to accommodate features specific to Carnatic music. The dual ternary indexing algorithm is adapted for Carnatic music by segmenting using the segmentation technique for Carnatic music. The dual ternary algorithm is compared with the multi-key hashing algorithm designed by us for indexing and retrieval in which features like MFCC, spectral flux, melody string and spectral centroid are used as features for indexing data into a hash table. The way in which collision resolution was handled by this hash table is different than the normal hash table approaches. It was observed that multi-key hashing based retrieval had a lesser time complexity than dual-ternary based indexing The algorithms were also compared for their precision and recall in which multi-key hashing had a better recall than modified dual ternary indexing for the sample data considered.
Interaction With Tilting Gestures In Ubiquitous Environments
Venue: arXiv cs.HC 2010
Year: 2010

In this paper, we introduce a tilting interface that controls direction based applications in ubiquitous environments. A tilt interface is useful for situations that require remote and quick interactions or that are executed in public spaces. We explored the proposed tilting interface with different application types and classified the tilting interaction techniques. Augmenting objects with sensors can potentially address the problem of the lack of intuitive and natural input devices in ubiquitous environments. We have conducted an experiment to test the usability of the proposed tilting interface to compare it with conventional input devices and hand gestures. The experiment results showed greater improvement of the tilt gestures in comparison with hand gestures in terms of speed, accuracy, and user satisfaction.
A Non-Cooperative Game Theoretical Approach For Power Control In Virtual MIMO Wireless Sensor Network
Venue: arXiv cs.NI 2010
Year: 2010

Power management is one of the vital issue in wireless sensor networks, where the lifetime of the network relies on battery powered nodes. Transmitting at high power reduces the lifetime of both the nodes and the network. One efficient way of power management is to control the power at which the nodes transmit. In this paper, a virtual multiple input multiple output wireless sensor network (VMIMO-WSN)communication architecture is considered and the power control of sensor nodes based on the approach of game theory is formulated. The use of game theory has proliferated, with a broad range of applications in wireless sensor networking. Approaches from game theory can be used to optimize node level as well as network wide performance. The game here is categorized as an incomplete information game, in which the nodes do not have complete information about the strategies taken by other nodes. For virtual multiple input multiple output wireless sensor network architecture considered, the Nash equilibrium is used to decide the optimal power level at which a node needs to transmit, to maximize its utility. Outcome shows that the game theoretic approach considered for VMIMO-WSN architecture achieves the best utility, by consuming less power.
I-Interaction: An Intelligent In-Vehicle User Interaction Model
Venue: arXiv cs.HC 2010
Year: 2010

The automobile is always a point of interest where new technology has been deployed. Because of this interest, human-vehicle interaction has been an appealing area for much research in recent years. The current in-vehicle design has been improved but still possesses some of the design from the traditional interaction style. In this paper, we propose a new user-oriented model for in-vehicle interaction model known as i-Interaction. The i-Interaction model provides user with an intuitive approach to interact with the In-Vehicle Information System (IVIS) by the keypad entry. It is the intent that the proposed usability testing for this model will help improve the way research and development is implemented from this topic. This model does not only provide the user with a direct interaction in vehicles but also introduce a new prospective that other research has not addressed.
Tree structure compression with RePair
Venue: arXiv cs.DS 2010
Year: 2010

In this work we introduce a new linear time compression algorithm, called "Re-pair for Trees", which compresses ranked ordered trees using linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars and allow basic tree operations, like traversal along edges, to be executed without prior decompression. Our algorithm can be considered as a generalization of the "Re-pair" algorithm developed by N. Jesper Larsson and Alistair Moffat in 2000. The latter algorithm is a dictionary-based compression algorithm for strings. We also introduce a succinct coding which is specialized in further compressing the grammars generated by our algorithm. This is accomplished without loosing the ability do directly execute queries on this compressed representation of the input tree. Finally, we compare the grammars and output files generated by a prototype of the Re-pair for Trees algorithm with those of similar compression algorithms. The obtained results show that that our algorithm outperforms its competitors in terms of compression ratio, runtime and memory usage.
Belief Propagation Methods for Intercell Interference Coordination
Venue: arXiv cs.NI 2010
Year: 2010

We consider a broad class of interference coordination and resource allocation problems for wireless links where the goal is to maximize the sum of functions of individual link rates. Such problems arise in the context of, for example, fractional frequency reuse (FFR) for macro-cellular networks and dynamic interference management in femtocells. The resulting optimization problems are typically hard to solve optimally even using centralized algorithms but are an essential computational step in implementing rate-fair and queue stabilizing scheduling policies in wireless networks. We consider a belief propagation framework to solve such problems approximately. In particular, we construct approximations to the belief propagation iterations to obtain computationally simple and distributed algorithms with low communication overhead. Notably, our methods are very general and apply to, for example, the optimization of transmit powers, transmit beamforming vectors, and sub-band allocation to maximize the above objective. Numerical results for femtocell deployments demonstrate that such algorithms compute a very good operating point in typically just a couple of iterations.
Dictionary for Sparse Representation of Chirp Echo in Broadband Radar
Venue: arXiv cs.IT 2010
Year: 2010

A new dictionary for sparse representation of chirp echo in broadband radar is put forward in this paper. Different with chirplet decomposition which decomposes echo in time-frequency plane, the dictionary transforms the sparsity of target observed by radar in distance range to the sparsity in frequency domain by stretch processing and the sparse representation of echo is realized. Using strict deduction with mathematics, the sparsity of echo in dictionary is proved and the dictionary is orthogonal. In the application property, the construction of dictionary is simple, the parameters that are needed for dictionary can be obtained conveniently and the dictionary is convenient to use. Furthermore, the object of application can be expanded to the echo of multi-component chirps with single freedom degree.