OpenRaiser/Intern-Atlas huggingface dataset:
On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study
Venue: arXiv cs.AI 2011
Year: 2011

Variable elimination is a general technique for constraint processing. It is often discarded because of its high space complexity. However, it can be extremely useful when combined with other techniques. In this paper we study the applicability of variable elimination to the challenging problem of finding still-lifes. We illustrate several alternatives: variable elimination as a stand-alone algorithm, interleaved with search, and as a source of good quality lower bounds. We show that these techniques are the best known option both theoretically and empirically. In our experiments we have been able to solve the n=20 instance, which is far beyond reach with alternative approaches.
Reasoning about Action: An Argumentation - Theoretic Approach
Venue: arXiv cs.AI 2011
Year: 2011

We present a uniform non-monotonic solution to the problems of reasoning about action on the basis of an argumentation-theoretic approach. Our theory is provably correct relative to a sensible minimisation policy introduced on top of a temporal propositional logic. Sophisticated problem domains can be formalised in our framework. As much attention of researchers in the field has been paid to the traditional and basic problems in reasoning about actions such as the frame, the qualification and the ramification problems, approaches to these problems within our formalisation lie at heart of the expositions presented in this paper.
Learning Concept Hierarchies from Text Corpora using Formal Concept Analysis
Venue: arXiv cs.AI 2011
Year: 2011

We present a novel approach to the automatic acquisition of taxonomies or concept hierarchies from a text corpus. The approach is based on Formal Concept Analysis (FCA), a method mainly used for the analysis of data, i.e. for investigating and processing explicitly given information. We follow Harris distributional hypothesis and model the context of a certain term as a vector representing syntactic dependencies which are automatically acquired from the text corpus with a linguistic parser. On the basis of this context information, FCA produces a lattice that we convert into a special kind of partial order constituting a concept hierarchy. The approach is evaluated by comparing the resulting concept hierarchies with hand-crafted taxonomies for two domains: tourism and finance. We also directly compare our approach with hierarchical agglomerative clustering as well as with Bi-Section-KMeans as an instance of a divisive clustering algorithm. Furthermore, we investigate the impact of using different measures weighting the contribution of each attribute as well as of applying a particular smoothing technique to cope with data sparseness.
Characterization of Request Sequences for List Accessing Problem and New Theoretical Results for MTF Algorithm
Venue: arXiv cs.DS 2011
Year: 2011

List Accessing Problem is a well studied research problem in the context of linear search. Input to the list accessing problem is an unsorted linear list of distinct elements along with a sequence of requests, where each request is an access operation on an element of the list. A list accessing algorithm reorganizes the list while processing a request sequence on the list in order to minimize the access cost. Move-To-Front algorithm has been proved to be the best performing list accessing online algorithm till date in the literature. Characterization of the input request sequences corresponding to practical real life situations is a big challenge for the list accessing problem. As far as our knowledge is concerned, no characterization for the request sequences has been done in the literature till date for the list accessing problem. In this paper, we have characterized the request sequences for the list accessing problem based on several factors such as size of the list, size of the request sequence, ordering of elements and frequency of occurrence of elements in the request sequence. We have made a comprehensive study of MTF list accessing algorithm and obtained new theoretical results for our characterized special class of request sequences. Our characterization will open up a new direction of research for empirical analysis of list accessing algorithms for real life inputs.
Heterogeneity for Increasing Performance and Reliability of Self-Reconfigurable Multi-Robot Organisms
Venue: arXiv cs.RO 2011
Year: 2011

Homogeneity and heterogeneity represent a well-known trade-off in the design of modular robot systems. This work addresses the heterogeneity concept, its rationales, design choices and performance evaluation. We introduce challenges for self-reconfigurable systems, show advances of mechatronic and software design of heterogeneous platforms and discuss experiments, which intend to demonstrate usability and performance of this system.
An Efficient Paging Algorithm for Multi-Carrier CDMA System
Venue: arXiv cs.NI 2011
Year: 2011

To cope with the increasing demand of wireless communication services multi-carrier systems are being used. Radio resources are very limited and efficient usages of these resources are inevitable to get optimum performance of the system. Paging channel is a low-bandwidth channel and one of the most important channels on which system performance depends significantly. Therefore it is vulnerable to even moderate overloads. In this paper, an efficient paging algorithm, Concurrent Search, is proposed for efficient use of paging channel in Multi- carrier CDMA system instead of existing sequential searching algorithm. It is shown by the simulation that the paging performance in proposed algorithm is far better than the existing system.
Secured color image watermarking technique in DWT-DCT domain
Venue: arXiv cs.MM 2011
Year: 2011

The multilayer secured DWT-DCT and YIQ color space based image watermarking technique with robustness and better correlation is presented here. The security levels are increased by using multiple pn sequences, Arnold scrambling, DWT domain, DCT domain and color space conversions. Peak signal to noise ratio and Normalized correlations are used as measurement metrics. The 512x512 sized color images with different histograms are used for testing and watermark of size 64x64 is embedded in HL region of DWT and 4x4 DCT is used. 'Haar' wavelet is used for decomposition and direct flexing factor is used. We got PSNR value is 63.9988 for flexing factor k=1 for Lena image and the maximum NC 0.9781 for flexing factor k=4 in Q color space. The comparative performance in Y, I and Q color space is presented. The technique is robust for different attacks like scaling, compression, rotation etc.
CCABC: Cyclic Cellular Automata Based Clustering For Energy Conservation in Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Sensor network has been recognized as the most significant technology for next century. Despites of its potential application, wireless sensor network encounters resource restriction such as low power, reduced bandwidth and specially limited power sources. This work proposes an efficient technique for the conservation of energy in a wireless sensor network (WSN) by forming an effective cluster of the network nodes distributed over a wide range of geographical area. The clustering scheme is developed around a specified class of cellular automata (CA) referred to as the modified cyclic cellular automata (mCCA). It sets a number of nodes in stand-by mode at an instance of time without compromising the area of network coverage and thereby conserves the battery power. The proposed scheme also determines an effective cluster size where the inter-cluster and intra-cluster communication cost is minimum. The simulation results establish that the cyclic cellular automata based clustering for energy conservation in sensor networks (CCABC) is more reliable than the existing schemes where clustering and CA based energy saving technique is used.
Expressiveness of Communication in Answer Set Programming
Venue: arXiv cs.LO 2011
Year: 2011

Answer set programming (ASP) is a form of declarative programming that allows to succinctly formulate and efficiently solve complex problems. An intuitive extension of this formalism is communicating ASP, in which multiple ASP programs collaborate to solve the problem at hand. However, the expressiveness of communicating ASP has not been thoroughly studied. In this paper, we present a systematic study of the additional expressiveness offered by allowing ASP programs to communicate. First, we consider a simple form of communication where programs are only allowed to ask questions to each other. For the most part, we deliberately only consider simple programs, i.e. programs for which computing the answer sets is in P. We find that the problem of deciding whether a literal is in some answer set of a communicating ASP program using simple communication is NP-hard. In other words: we move up a step in the polynomial hierarchy due to the ability of these simple ASP programs to communicate and collaborate. Second, we modify the communication mechanism to also allow us to focus on a sequence of communicating programs, where each program in the sequence may successively remove some of the remaining models. This mimics a network of leaders, where the first leader has the first say and may remove models that he or she finds unsatisfactory. Using this particular communication mechanism allows us to capture the entire polynomial hierarchy. This means, in particular, that communicating ASP could be used to solve problems that are above the second level of the polynomial hierarchy, such as some forms of abductive reasoning as well as PSPACE-complete problems such as STRIPS planning.
A O(1/eps^2)^n Time Sieving Algorithm for Approximate Integer Programming
Venue: arXiv cs.DS 2011
Year: 2011

The Integer Programming Problem (IP) for a polytope P \subseteq R^n is to find an integer point in P or decide that P is integer free. We give an algorithm for an approximate version of this problem, which correctly decides whether P contains an integer point or whether a (1+\eps) scaling of P around its barycenter is integer free in time O(1/\eps^2)^n. We reduce this approximate IP question to an approximate Closest Vector Problem (CVP) in a "near-symmetric" semi-norm, which we solve via a sieving technique first developed by Ajtai, Kumar, and Sivakumar (STOC 2001). Our main technical contribution is an extension of the AKS sieving technique which works for any near-symmetric semi-norm. Our results also extend to general convex bodies and lattices.
Swiss Elections to the National Council: First trials with e-voting in elections at federal level
Venue: arXiv cs.CY 2011
Year: 2011

On October 23rd 2011, around 22'000 voters will be authorized to cast their votes electronically in occasion of the elections to the National Council. These are the first trials ever with e-voting in elections at federal level in Switzerland. Four cantons are going to conduct trials with this new channel. Only Swiss voters living abroad will be authorized to participate. The Swiss Confederation pursues the long term goal of the introduction of e-voting as a third, complementary voting method - in addition to voting in person at the polling station and postal voting.
RedAlert: Determinacy Inference for Prolog
Venue: arXiv cs.PL 2011
Year: 2011

This paper revisits the problem of determinacy inference addressing the problem of how to uniformly handle cut. To this end a new semantics is introduced for cut, which is abstracted to systematically derive a backward analysis that derives conditions sufficient for a goal to succeed at most once. The method is conceptionally simpler and easier to implement than existing techniques, whilst improving the latter's handling of cut. Formal arguments substantiate correctness and experimental work, and a tool called 'RedAlert' demonstrates the method's generality and applicability.
YouTube and political communication -- Macedonian case
Venue: arXiv cs.SI 2011
Year: 2011

Analysis how to use Internet influence to the process of political communication, marketing and the management of public relations, what kind of online communication methods are used by political parties, and to assess satisfaction, means of communication and the services they provide to their party's voters (people) and other interest groups and whether social networks can affect the political and economic changes in the state, and the political power of one party.
A Novel Relay-Aided Transmission Scheme in Cognitive Radio Networks
Venue: arXiv cs.NI 2011
Year: 2011

In underlay cognitive radio networks, unlicensed secondary users are allowed to share the spectrum with licensed primary users when the interference induced on the primary transmission is limited. In this paper, we propose a new cooperative transmission scheme for cognitive radio networks where a relay node is able to help both the primary and secondary transmissions. We derive exact closed-form and upper bound expressions of the conditional primary and secondary outage probabilities over Rayleigh fading channels. Furthermore, we proposed a simple power allocation algorithm. Finally, using numerical evaluation and simulation results we show the potential of our cooperative transmission scheme in improving the secondary outage probability without harming the primary one.
A Delay-Constrained General Achievable Rate and Certain Capacity Results for UWB Relay Channel
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we derive UWB version of (i) general best achievable rate for the relay channel with decode-andforward strategy and (ii) max-flow min-cut upper bound, such that the UWB relay channel can be studied considering the obtained lower and upper bounds. Then, we show that by appropriately choosing the noise correlation coefficients, our new upper bound coincides with the lower bound in special cases of degraded and reversely degraded UWB relay channels. Finally, some numerical results are illustrated.
Rejecting Adaptive Interface
Venue: arXiv cs.HC 2011
Year: 2011

Programs have to be designed in such a way as to make them looking good and being handy for all users. Adaptive interface, with all the numerous achievements throughout 30 years of its history, contains and in reality is based on one fundamental flaw - on the assumption that designer knows better than anyone else what is good for users in each and all cases. Programs of the new type - user-driven applications - still deliver to users the best results of developers' work but at the same time give users the full control over applications and in this way really allow each user to change an application in such a way as he wants it to look at each particular moment. Users can move and resize each and all of the screen objects while an application is running, and this changes the whole programming philosophy.
On Periodic Node Deployment in Wireless Sensor Networks: A Statistical Analysis
Venue: arXiv cs.NI 2011
Year: 2011

Rapid progress made in the field of sensor technology, wireless communication, and computer networks in recent past, led to the development of wireless Ad-hoc sensor networks, consisting of small, low-cost sensors, which can monitor wide and remote areas with precision and liveliness unseen to the date without the intervention of a human operator. This work comes up with a stochastic model for periodic sensor-deployment (in face of their limited amount of battery-life) to maintain a minimal node-connectivity in wireless sensor networks. The node deployment cannot be modeled by using results from conventional continuous birth-death process, since new nodes are added to the network in bursts, i.e. the birth process is not continuous in practical situations. We analyze the periodic node deployment process using discrete birth-continuous death process and obtain two important statistical measures of the existing number of nodes in the network, namely the mean and variance. We show that the above mentioned sequences of mean and variances always converge to finite steady state values, thus ensuring the stability of the system. We also develop a cost function for the process of periodic deployment of sensor nodes and minimize it to find the optimal time (τ) and optimum number of re-deployment (q) for maintaining minimum connectivity in the network.
Neigborhood Selection in Variable Neighborhood Search
Venue: arXiv cs.AI 2011
Year: 2011

Variable neighborhood search (VNS) is a metaheuristic for solving optimization problems based on a simple principle: systematic changes of neighborhoods within the search, both in the descent to local minima and in the escape from the valleys which contain them. Designing these neighborhoods and applying them in a meaningful fashion is not an easy task. Moreover, an appropriate order in which they are applied must be determined. In this paper we attempt to investigate this issue. Assume that we are given an optimization problem that is intended to be solved by applying the VNS scheme, how many and which types of neighborhoods should be investigated and what could be appropriate selection criteria to apply these neighborhoods. More specifically, does it pay to "look ahead" (see, e.g., in the context of VNS and GRASP) when attempting to switch from one neighborhood to another?
Syntactic Complexity of Star-Free Languages
Venue: arXiv cs.FL 2011
Year: 2011

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the maximal syntactic complexity of languages in that subclass, taken as a function of the state complexity of these languages. We study the syntactic complexity of star-free regular languages, that is, languages that can be constructed from finite languages using union, complement and concatenation. We find tight upper bounds on the syntactic complexity of languages accepted by monotonic and partially monotonic automata. We introduce "nearly monotonic" automata, which accept star-free languages, and find a tight upper bound on the syntactic complexity of languages accepted by such automata. We conjecture that this bound is also an upper bound on the syntactic complexity of star-free languages.
One, None and One Hundred Thousand Profiles: Re-imagining the Pirandellian Identity Dilemma in the Era of Online Social Networks
Venue: arXiv cs.SI 2011
Year: 2011

Uno, Nessuno, Centomila ("One, No One and One Hundred Thousand") is a classic novel by Italian playwright Luigi Pirandello. Published in 1925, it recounts the tragedy of Vitangelo Moscarda, a man who struggles to reclaim a coherent and unitary identity for himself in the face of an inherently social and multi-faceted world. What would Moscarda identity tragedy look like today? In this article we transplant Moscarda's identity play from its offline setting to the contemporary arena of social media and online social networks. With reference to established theories on identity construction, performance, and self-presentation, we re-imagine how Moscarda would go about defending the integrity of his selfhood in the face of the discountenancing influences of the online world.
A Characterization of the Combined Effects of Overlap and Imbalance on the SVM Classifier
Venue: arXiv cs.AI 2011
Year: 2011

In this paper we demonstrate that two common problems in Machine Learning---imbalanced and overlapping data distributions---do not have independent effects on the performance of SVM classifiers. This result is notable since it shows that a model of either of these factors must account for the presence of the other. Our study of the relationship between these problems has lead to the discovery of a previously unreported form of "covert" overfitting which is resilient to commonly used empirical regularization techniques. We demonstrate the existance of this covert phenomenon through several methods based around the parametric regularization of trained SVMs. Our findings in this area suggest a possible approach to quantifying overlap in real world data sets.
Towards a Coalgebraic Interpretation of Propositional Dynamic Logic
Venue: arXiv cs.LO 2011
Year: 2011

The interpretation of propositional dynamic logic (PDL) through Kripke models requires the relations constituting the interpreting Kripke model to closely observe the syntax of the modal operators. This poses a significant challenge for an interpretation of PDL through stochastic Kripke models, because the programs' operations do not always have a natural counterpart in the set of stochastic relations. We use rewrite rules for building up an interpretation of PDL. It is shown that each program corresponds to an essentially unique irreducible tree, which in turn is assigned a predicate lifting, serving as the program's interpretation. The paper establishes and studies this interpretation. It discusses the expressivity of probabilistic models for PDL and relates properties like logical and behavioral equivalence or bisimilarity to the corresponding properties of a Kripke model for a closely related non-dynamic logic of the Hennessy-Milner type.
A numerical solution to the minimum-time control problem for linear discrete-time systems
Venue: arXiv cs.SY 2011
Year: 2011

The minimum-time control problem consists in finding a control policy that will drive a given dynamic system from a given initial state to a given target state (or a set of states) as quickly as possible. This is a well-known challenging problem in optimal control theory for which closed-form solutions exist only for a few systems of small dimensions. This paper presents a very generic solution to the minimum-time problem for arbitrary discrete-time linear systems. It is a numerical solution based on sparse optimization, that is the minimization of the number of nonzero elements in the state sequence over a fixed control horizon. We consider both single input and multiple inputs systems. An important observation is that, contrary to the continuous-time case, the minimum-time control for discrete-time systems is not necessarily entirely bang-bang.
Distributed Consensus of Linear Multi-Agent Systems with Adaptive Dynamic Protocols
Venue: arXiv cs.SY 2011
Year: 2011

This paper considers the distributed consensus problem of multi-agent systems with general continuous-time linear dynamics. Two distributed adaptive dynamic consensus protocols are proposed, based on the relative output information of neighboring agents. One protocol assigns an adaptive coupling weight to each edge in the communication graph while the other uses an adaptive coupling weight for each node. These two adaptive protocols are designed to ensure that consensus is reached in a fully distributed fashion for any undirected connected communication graphs without using any global information. A sufficient condition for the existence of these adaptive protocols is that each agent is stabilizable and detectable. The cases with leader-follower and switching communication graphs are also studied.
Designing a CPU model: from a pseudo-formal document to fast code
Venue: arXiv cs.SE 2011
Year: 2011

For validating low level embedded software, engineers use simulators that take the real binary as input. Like the real hardware, these full-system simulators are organized as a set of components. The main component is the CPU simulator (ISS), because it is the usual bottleneck for the simulation speed, and its development is a long and repetitive task. Previous work showed that an ISS can be generated from an Architecture Description Language (ADL). In the work reported in this paper, we generate a CPU simulator directly from the pseudo-formal descriptions of the reference manual. For each instruction, we extract the information describing its behavior, its binary encoding, and its assembly syntax. Next, after automatically applying many optimizations on the extracted information, we generate a SystemC/TLM ISS. We also generate tests for the decoder and a formal specification in Coq. Experiments show that the generated ISS is as fast and stable as our previous hand-written ISS.