OpenRaiser/Intern-Atlas huggingface dataset:
Relativized hyperequivalence of logic programs for modular programming
Venue: arXiv cs.AI 2009
Year: 2009

A recent framework of relativized hyperequivalence of programs offers a unifying generalization of strong and uniform equivalence. It seems to be especially well suited for applications in program optimization and modular programming due to its flexibility that allows us to restrict, independently of each other, the head and body alphabets in context programs. We study relativized hyperequivalence for the three semantics of logic programs given by stable, supported and supported minimal models. For each semantics, we identify four types of contexts, depending on whether the head and body alphabets are given directly or as the complement of a given set. Hyperequivalence relative to contexts where the head and body alphabets are specified directly has been studied before. In this paper, we establish the complexity of deciding relativized hyperequivalence with respect to the three other types of context programs. To appear in Theory and Practice of Logic Programming (TPLP).
Modular Verification of Recursive Programs
Venue: arXiv cs.LO 2009
Year: 2009

We argue that verification of recursive programs by means of the assertional method of C.A.R. Hoare can be conceptually simplified using a modular reasoning. In this approach some properties of the program are established first and subsequently used to establish other program properties. We illustrate this approach by providing a modular correctness proof of the Quicksort program.
Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks
Venue: arXiv cs.GT 2009
Year: 2009

Bargaining games on exchange networks have been studied by both economists and sociologists. A Balanced Outcome for such a game is an equilibrium concept that combines notions of stability and fairness. In a recent paper, Kleinberg and Tardos introduced balanced outcomes to the computer science community and provided a polynomial-time algorithm to compute the set of such outcomes. Their work left open a pertinent question: are there natural, local dynamics that converge quickly to a balanced outcome? In this paper, we provide a partial answer to this question by showing that simple edge-balancing dynamics converge to a balanced outcome whenever one exists.
Graphical Probabilistic Routing Model for OBS Networks with Realistic Traffic Scenario
Venue: arXiv cs.NI 2009
Year: 2009

Burst contention is a well-known challenging problem in Optical Burst Switching (OBS) networks. Contention resolution approaches are always reactive and attempt to minimize the BLR based on local information available at the core node. On the other hand, a proactive approach that avoids burst losses before they occur is desirable. To reduce the probability of burst contention, a more robust routing algorithm than the shortest path is needed. This paper proposes a new routing mechanism for JET-based OBS networks, called Graphical Probabilistic Routing Model (GPRM) that selects less utilized links, on a hop-by-hop basis by using a bayesian network. We assume no wavelength conversion and no buffering to be available at the core nodes of the OBS network. We simulate the proposed approach under dynamic load to demonstrate that it reduces the Burst Loss Ratio (BLR) compared to static approaches by using Network Simulator 2 (ns-2) on NSFnet network topology and with realistic traffic matrix. Simulation results clearly show that the proposed approach outperforms static approaches in terms of BLR.
Pattern Recognition Theory of Mind
Venue: arXiv cs.AI 2009
Year: 2009

I propose that pattern recognition, memorization and processing are key concepts that can be a principle set for the theoretical modeling of the mind function. Most of the questions about the mind functioning can be answered by a descriptive modeling and definitions from these principles. An understandable consciousness definition can be drawn based on the assumption that a pattern recognition system can recognize its own patterns of activity. The principles, descriptive modeling and definitions can be a basis for theoretical and applied research on cognitive sciences, particularly at artificial intelligence studies.
Small-step and big-step semantics for call-by-need
Venue: arXiv cs.PL 2009
Year: 2009

We present natural semantics for acyclic as well as cyclic call-by-need lambda calculi, which are proved equivalent to the reduction semantics given by Ariola and Felleisen. The natural semantics are big-step and use global heaps, where evaluation is suspended and memorized. The reduction semantics are small-step and evaluation is suspended and memorized locally in let-bindings. Thus two styles of formalization describe the call-by-need strategy from different angles. The natural semantics for the acyclic calculus is revised from the previous presentation by Maraist et al. and its adequacy is ascribed to its correspondence with the reduction semantics, which has been proved equivalent to call-by-name by Ariola and Felleisen. The natural semantics for the cyclic calculus is inspired by that of Launchbury and Sestoft and we state its adequacy using a denotational semantics in the style of Launchbury; adequacy of the reduction semantics for the cyclic calculus is in turn ascribed to its correspondence with the natural semantics.
Modeling and Simulation of Scalable Cloud Computing Environments and the CloudSim Toolkit: Challenges and Opportunities
Venue: arXiv cs.DC 2009
Year: 2009

Cloud computing aims to power the next generation data centers and enables application service providers to lease data center capabilities for deploying applications depending on user QoS (Quality of Service) requirements. Cloud applications have different composition, configuration, and deployment requirements. Quantifying the performance of resource allocation policies and application scheduling algorithms at finer details in Cloud computing environments for different application and service models under varying load, energy performance (power consumption, heat dissipation), and system size is a challenging problem to tackle. To simplify this process, in this paper we propose CloudSim: an extensible simulation toolkit that enables modelling and simulation of Cloud computing environments. The CloudSim toolkit supports modelling and creation of one or more virtual machines (VMs) on a simulated node of a Data Center, jobs, and their mapping to suitable VMs. It also allows simulation of multiple Data Centers to enable a study on federation and associated policies for migration of VMs for reliability and automatic scaling of applications.
Iterative pushdown automata and hyperbolic contour words
Venue: arXiv cs.CG 2009
Year: 2009

In this paper, we give an application of iterated pushdown automata to contour words of balls and two other domains in infinitely many tilings of the hyperbolic plane. We also give a similar application for the tiling {5,3,4} of the hyperbolic 3D space and for the tiling {5,3,3,4} of the hyperbolic 4D space as well.
Ezhil: A Tamil Programming Language
Venue: arXiv cs.PL 2009
Year: 2009

Ezhil is a Tamil language based interpreted procedural programming language. Tamil keywords and grammar are chosen to make the native Tamil speaker write programs in the Ezhil system. Ezhil allows easy representation of computer program closer to the Tamil language logical constructs equivalent to the conditional, branch and loop statements in modern English based programming languages. Ezhil is a compact programming language aimed towards Tamil speaking novice computer users. Grammar for Ezhil and a few example programs are reported here, from the initial proof-of-concept implementation using the Python programming language1. To the best of our knowledge, Ezhil language is the first freely available Tamil programming language.
Existence of new inequalities for representable polymatroids
Venue: arXiv cs.IT 2009
Year: 2009

An Ingletonian polymatroid satisfies, in addition to the polymatroid axioms, the inequalities of Ingleton (Combin. Math. Appln., 1971). These inequalities are required for a polymatroid to be representable. It is has been an open question as to whether these inequalities are also sufficient. Representable polymatroids are of interest in their own right. They also have a strong connection to network coding. In particular, the problem of finding the linear network coding capacity region is equivalent to the characterization of all representable, entropic polymatroids. In this paper, we describe a new approach to adhere two polymatroids together to produce a new polymatroid. Using this approach, we can construct a polymatroid that is not inside the minimal closed and convex cone containing all representable polymatroids. This polymatroid is proved to satisfy not only the Ingleton inequalities, but also the recently reported inequalities of Dougherty, Freiling and Zeger. A direct consequence is that these inequalities are not sufficient to characterize representable polymatroids.
On Delay Constrained Multicast Capacity of Large-Scale Mobile Ad-Hoc Networks
Venue: arXiv cs.NI 2009
Year: 2009

This paper studies the delay constrained multicast capacity of large scale mobile ad hoc networks (MANETs). We consider a MANET consists of $n_s$ multicast sessions. Each multicast session has one source and $p$ destinations. The wireless mobiles move according to a two-dimensional i.i.d. mobility model. Each source sends identical information to the $p$ destinations in its multicast session, and the information is required to be delivered to all the $p$ destinations within $D$ time-slots. Given the delay constraint $D,$ we first prove that the capacity per multicast session is $O(\min\{1, (\log p)(\log (n_sp)) \sqrt{\frac{D}{n_s}}\}).$ Given non-negative functions $f(n)$ and $g(n)$: $f(n)=O(g(n))$ means there exist positive constants $c$ and $m$ such that $f(n) \leq cg(n)$ for all $ n\geq m;$ $f(n)=Ω(g(n))$ means there exist positive constants $c$ and $m$ such that $f(n)\geq cg(n)$ for all $n\geq m;$ $f(n)=Θ(g(n))$ means that both $f(n)=Ω(g(n))$ and $f(n)=O(g(n))$ hold; $f(n)=o(g(n))$ means that $\lim_{n\to \infty} f(n)/g(n)=0;$ and $f(n)=ω(g(n))$ means that $\lim_{n\to \infty} g(n)/f(n)=0.$ We then propose a joint coding/scheduling algorithm achieving a throughput of $Θ(\min\{1,\sqrt{\frac{D}{n_s}}\}).$ Our simulations show that the joint coding/scheduling algorithm achieves a throughput of the same order ($Θ(\min\{1, \sqrt{\frac{D}{n_s}}\})$) under random walk model and random waypoint model.
Proof Theory at Work: Complexity Analysis of Term Rewrite Systems
Venue: arXiv cs.LO 2009
Year: 2009

This thesis is concerned with investigations into the "complexity of term rewriting systems". Moreover the majority of the presented work deals with the "automation" of such a complexity analysis. The aim of this introduction is to present the main ideas in an easily accessible fashion to make the result presented accessible to the general public. Necessarily some technical points are stated in an over-simplified way.
High-Rate, Distributed Training-Embedded Complex Orthogonal Designs for Relay Networks
Venue: arXiv cs.IT 2009
Year: 2009

Distributed Space-Time Block Codes (DSTBCs) from Complex Orthogonal Designs (CODs) (both square and non-square CODs other than the Alamouti design) are known to lose their single-symbol ML decodable (SSD) property when used in two-hop wireless relay networks using amplify and forward protocol. For such a network, in this paper, a new class of high rate, training-embedded (TE) SSD DSTBCs are constructed from TE-CODs. The proposed codes include the training symbols in the structure of the code which is shown to be the key point to obtain high rate as well as the SSD property. TE-CODs are shown to offer full-diversity for arbitrary complex constellations. Non-square TE-CODs are shown to provide higher rates (in symbols per channel use) compared to the known SSD DSTBCs for relay networks with number of relays less than $10.$
A Novel Generic Session Based Bit Level Encryption Technique to Enhance Information Security
Venue: arXiv cs.CR 2009
Year: 2009

- In this paper a session based symmetric key encryption system has been proposed and is termed as Permutated Cipher Technique (PCT). This technique is more fast, suitable and secure for larger files. In this technique the input file is broken down into blocks of various sizes (of 2 power n order) and encrypted by shifting the position of each bit by a certain value for a certain number of times. A key is generated randomly wherein the length of each block is determined. Each block length generates a unique value of number of bits to be skipped. This value determines the new position of the bits within the block that are to be shifted. After the shifting and inverting each block is XORed with SHA 512 digest of the key. The resultant blocks from the cipher text. The key is generated according to the binary value of the input file size. Decryption is done following the same process as the technique is symmetric.
Knowledge Discovery of Hydrocyclone s Circuit Based on SONFIS and SORST
Venue: arXiv cs.AI 2009
Year: 2009

This study describes application of some approximate reasoning methods to analysis of hydrocyclone performance. In this manner, using a combining of Self Organizing Map (SOM), Neuro-Fuzzy Inference System (NFIS)-SONFIS- and Rough Set Theory (RST)-SORST-crisp and fuzzy granules are obtained. Balancing of crisp granules and non-crisp granules can be implemented in close-open iteration. Using different criteria and based on granulation level balance point (interval) or a pseudo-balance point is estimated. Validation of the proposed methods, on the data set of the hydrocyclone is rendered.
The Levels of Conceptual Interoperability Model: Applying Systems Engineering Principles to M&S
Venue: arXiv cs.SE 2009
Year: 2009

This paper describes the use of the Levels of Conceptual Interoperability Model (LCIM) as a framework for conceptual modeling and its descriptive and prescriptive uses. LCIM is applied to show its potential and shortcomings in the current simulation interoperability approaches, in particular the High Level Architecture (HLA) and Base Object Models (BOM). It emphasizes the need to apply rigorous engineering methods and principles and replace ad-hoc approaches.
On Bijective Variants of the Burrows-Wheeler Transform
Venue: arXiv cs.DS 2009
Year: 2009

The sort transform (ST) is a modification of the Burrows-Wheeler transform (BWT). Both transformations map an arbitrary word of length n to a pair consisting of a word of length n and an index between 1 and n. The BWT sorts all rotation conjugates of the input word, whereas the ST of order k only uses the first k letters for sorting all such conjugates. If two conjugates start with the same prefix of length k, then the indices of the rotations are used for tie-breaking. Both transforms output the sequence of the last letters of the sorted list and the index of the input within the sorted list. In this paper, we discuss a bijective variant of the BWT (due to Scott), proving its correctness and relations to other results due to Gessel and Reutenauer (1993) and Crochemore, Desarmenien, and Perrin (2005). Further, we present a novel bijective variant of the ST.
Region growing for multi-route cuts
Venue: arXiv cs.DS 2009
Year: 2009

We study a number of multi-route cut problems: given a graph G=(V,E) and connectivity thresholds k_(u,v) on pairs of nodes, the goal is to find a minimum cost set of edges or vertices the removal of which reduces the connectivity between every pair (u,v) to strictly below its given threshold. These problems arise in the context of reliability in communication networks; They are natural generalizations of traditional minimum cut problems where the thresholds are either 1 (we want to completely separate the pair) or infinity (we don't care about the connectivity for the pair). We provide the first non-trivial approximations to a number of variants of the problem including for both node-disjoint and edge-disjoint connectivity thresholds. A main contribution of our work is an extension of the region growing technique for approximating minimum multicuts to the multi-route setting. When the connectivity thresholds are either 2 or infinity (the "2-route cut" case), we obtain polylogarithmic approximations while satisfying the thresholds exactly. For arbitrary connectivity thresholds this approach leads to bicriteria approximations where we approximately satisfy the thresholds and approximately minimize the cost. We present a number of different algorithms achieving different cost-connectivity tradeoffs.
Data management in systems biology I - Overview and bibliography
Venue: arXiv cs.DB 2009
Year: 2009

Large systems biology projects can encompass several workgroups often located in different countries. An overview about existing data standards in systems biology and the management, storage, exchange and integration of the generated data in large distributed research projects is given, the pros and cons of the different approaches are illustrated from a practical point of view, the existing software - open source as well as commercial - and the relevant literature is extensively overview, so that the reader should be enabled to decide which data management approach is the best suited for his special needs. An emphasis is laid on the use of workflow systems and of TAB-based formats. The data in this format can be viewed and edited easily using spreadsheet programs which are familiar to the working experimental biologists. The use of workflows for the standardized access to data in either own or publicly available databanks and the standardization of operation procedures is presented. The use of ontologies and semantic web technologies for data management will be discussed in a further paper.
Evaluating Collaborative Search Interfaces with Information Seeking Theory
Venue: arXiv cs.IR 2009
Year: 2009

Despite the many implicit references to the social aspects of search within Information Seeking and Retrieval research, there has been relatively little work that has specifically investigated the additional requirements for collaborative search software. In this paper we re-assess a recent evaluation framework, designed for individual information seeking experiences, to see a) how it could still be applied to collaborative search software; b) how it could produce additional requirements for collaborative search; and c) how it could be extended in future work to be even more appropriate for collaborative search evaluation. The position held after the assessment is that it can be used to evaluate collaborative search software, while providing new insights into their requirements. Finally, future work will validate the frameworks applicability to collaborative search and investigate roles within collaborative groups as a means to extend the framework.
Learning about Potential Users of Collaborative Information Retrieval Systems
Venue: arXiv cs.IR 2009
Year: 2009

One of the key components of designing usable and useful collaborative information retrieval systems is to understand the needs of the users of these systems. Our research team has been exploring collaborative information behavior in a variety of organizational settings. Our research goals have been two-fold: First, to develop a conceptual understanding of collaborative information behavior and second, gather requirements for the design of collaborative information retrieval systems. In this paper, we present a brief overview of our fieldwork in a three different organizational settings, discuss our methodology for collecting data on collaborative information behavior, and highlight some lessons that we are learning about potential users of collaborative information retrieval systems in these domains.
Operating binary strings using gliders and eaters in reaction-diffusion cellular automaton
Venue: arXiv cs.FL 2009
Year: 2009

We study transformations of 2-, 4- and 6-bit numbers in interactions between traveling and stationary localizations in the Spiral Rule reaction-diffusion cellular automaton. The Spiral Rule automaton is a hexagonal ternary-state two-dimensional cellular automaton -- a finite-state machine imitation of an activator-inhibitor reaction-diffusion system. The activator is self-inhibited in certain concentrations. The inhibitor dissociates in the absence of the activator. The Spiral Rule cellular automaton has rich spatio-temporal dynamics of traveling (glider) and stationary (eater) patterns. When a glider brushes an eater the eater may slightly change its configuration, which is updated once more every next hit. We encode binary strings in the states of eaters and sequences of gliders. We study what types of binary compositions of binary strings are implementable by sequences of gliders brushing an eater. The models developed will be used in future laboratory designs of reaction-diffusion chemical computers.
Evaluation of Coordination Techniques in Synchronous Collaborative Information Retrieval
Venue: arXiv cs.IR 2009
Year: 2009

Traditional Information Retrieval (IR) research has focussed on a single user interaction modality, where a user searches to satisfy an information need. Recent advances in web technologies and computer hardware have enabled multiple users to collaborate on many computer-supported tasks, therefore there is an increasing opportunity to support two or more users searching together at the same time in order to satisfy a shared information need, which we refer to as Synchronous Collaborative Information Retrieval (SCIR). SCIR systems represent a significant paradigmatic shift from traditional IR systems. In order to support effective SCIR, new techniques are required to coordinate users' activities. In addition, the novel domain of SCIR presents challenges for effective evaluations of these systems. In this paper we will propose an effective and re-usable evaluation methodology based on simulating users searching together. We will outline how we have used this evaluation in empirical studies of the effects of different division of labour and sharing of knowledge techniques for SCIR.
Collaborative Search Trails for Video Search
Venue: arXiv cs.IR 2009
Year: 2009

In this paper we present an approach for supporting users in the difficult task of searching for video. We use collaborative feedback mined from the interactions of earlier users of a video search system to help users in their current search tasks. Our objective is to improve the quality of the results that users find, and in doing so also assist users to explore a large and complex information space. It is hoped that this will lead to them considering search options that they may not have considered otherwise. We performed a user centred evaluation. The results of our evaluation indicate that we achieved our goals, the performance of the users in finding relevant video clips was enhanced with our system; users were able to explore the collection of video clips more and users demonstrated a preference for our system that provided recommendations.
Automated Spreadsheet Development
Venue: arXiv cs.HC 2009
Year: 2009

Few major commercial or economic decisions are made today which are not underpinned by analysis using spreadsheets. It is virtually impossible to avoid making mistakes during their drafting and some of these errors remain, unseen and uncorrected, until something turns the spotlight on them. By then it may be too late. The challenge is to find a way of creating spreadsheets which will preserve the benefit of their power and flexibility while making their creation more transparent and safer. Full documentation and documented version and quality control, section by section, of the eventual spreadsheet would be a bonus. And if the whole process could be made quicker, too, that would be a further bonus.