OpenRaiser/Intern-Atlas huggingface dataset:
Fastest Distributed Consensus Averaging Problem on Chain of Rhombus Networks
Venue: arXiv cs.IT 2010
Year: 2010

Distributed consensus has appeared as one of the most important and primary problems in the context of distributed computation and it has received renewed interest in the field of sensor networks (due to recent advances in wireless communications), where solving fastest distributed consensus averaging problem over networks with different topologies is one of the primary problems in this issue. Here in this work analytical solution for the problem of fastest distributed consensus averaging algorithm over Chain of Rhombus networks is provided, where the solution procedure consists of stratification of associated connectivity graph of the network and semidefinite programming, particularly solving the slackness conditions, where the optimal weights are obtained by inductive comparing of the characteristic polynomials initiated by slackness conditions. Also characteristic polynomial together with its roots corresponding to eigenvalues of weight matrix including SLEM of network is determined inductively. Moreover to see the importance of rhombus graphs it is indicated that convergence rate of path network increases by replacing a single node by a rhombus sub graph within the path network.
I-Min: An Intelligent Fermat Point Based Energy Efficient Geographic Packet Forwarding Technique for Wireless Sensor and Ad Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

Energy consumption and delay incurred in packet delivery are the two important metrics for measuring the performance of geographic routing protocols for Wireless Adhoc and Sensor Networks (WASN). A protocol capable of ensuring both lesser energy consumption and experiencing lesser delay in packet delivery is thus suitable for networks which are delay sensitive and energy hungry at the same time. Thus a smart packet forwarding technique addressing both the issues is thus the one looked for by any geographic routing protocol. In the present paper we have proposed a Fermat point based forwarding technique which reduces the delay experienced during packet delivery as well as the energy consumed for transmission and reception of data packets.
The Use of Probabilistic Systems to Mimic the Behaviour of Idiotypic AIS Robot Controllers
Venue: arXiv cs.AI 2010
Year: 2010

Previous work has shown that robot navigation systems that employ an architecture based upon the idiotypic network theory of the immune system have an advantage over control techniques that rely on reinforcement learning only. This is thought to be a result of intelligent behaviour selection on the part of the idiotypic robot. In this paper an attempt is made to imitate idiotypic dynamics by creating controllers that use reinforcement with a number of different probabilistic schemes to select robot behaviour. The aims are to show that the idiotypic system is not merely performing some kind of periodic random behaviour selection, and to try to gain further insight into the processes that govern the idiotypic mechanism. Trials are carried out using simulated Pioneer robots that undertake navigation exercises. Results show that a scheme that boosts the probability of selecting highly-ranked alternative behaviours to 50% during stall conditions comes closest to achieving the properties of the idiotypic system, but remains unable to match it in terms of all round performance.
Modelling Reactive and Proactive Behaviour in Simulation
Venue: arXiv cs.AI 2010
Year: 2010

This research investigated the simulation model behaviour of a traditional and combined discrete event as well as agent based simulation models when modelling human reactive and proactive behaviour in human centric complex systems. A departmental store was chosen as human centric complex case study where the operation system of a fitting room in WomensWear department was investigated. We have looked at ways to determine the efficiency of new management policies for the fitting room operation through simulating the reactive and proactive behaviour of staff towards customers. Once development of the simulation models and their verification had been done, we carried out a validation experiment in the form of a sensitivity analysis. Subsequently, we executed a statistical analysis where the mixed reactive and proactive behaviour experimental results were compared with some reactive experimental results from previously published works. Generally, this case study discovered that simple proactive individual behaviour could be modelled in both simulation models. In addition, we found the traditional discrete event model performed similar in the simulation model output compared to the combined discrete event and agent based simulation when modelling similar human behaviour.
Should Static Search Trees Ever Be Unbalanced?
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we study the question of whether or not a static search tree should ever be unbalanced. We present several methods to restructure an unbalanced k-ary search tree $T$ into a new tree $R$ that preserves many of the properties of $T$ while having a height of $\log_k n +1$ which is one unit off of the optimal height. More specifically, we show that it is possible to ensure that the depth of the elements in $R$ is no more than their depth in $T$ plus at most $\log_k \log_k n +2$. At the same time it is possible to guarantee that the average access time $P(R)$ in tree $R$ is no more than the average access time $P(T)$ in tree $T$ plus $O(\log_k P(T))$. This suggests that for most applications, a balanced tree is always a better option than an unbalanced one since the balanced tree has similar average access time and much better worst case access time.
On the concentration of the number of solutions of random satisfiability formulas
Venue: arXiv cs.DM 2010
Year: 2010

Let $Z(F)$ be the number of solutions of a random $k$-satisfiability formula $F$ with $n$ variables and clause density $α$. Assume that the probability that $F$ is unsatisfiable is $O(1/\log(n)^{1+\e})$ for $\e>0$. We show that (possibly excluding a countable set of `exceptional' $α$'s) the number of solutions concentrate in the logarithmic scale, i.e., there exists a non-random function $ϕ(α)$ such that, for any $δ>0$, $(1/n)\log Z(F)\in [ϕ-δ,ϕ+δ]$ with high probability. In particular, the assumption holds for all $α<1$, which proves the above concentration claim in the whole satisfiability regime of random $2$-SAT. We also extend these results to a broad class of constraint satisfaction problems. The proof is based on an interpolation technique from spin-glass theory, and on an application of Friedgut's theorem on sharp thresholds for graph properties.
Impact of Channel Asymmetry on Performance of Channel Estimation and Precoding for Downlink Base Station Cooperative Transmission
Venue: arXiv cs.IT 2010
Year: 2010

Base station (BS) cooperative transmission can improve the spectrum efficiency of cellular systems, whereas using which the channels will become asymmetry. In this paper, we study the impact of the asymmetry on the performance of channel estimation and precoding in downlink BS cooperative multiple-antenna multiple-carrier systems. We first present three linear estimators which jointly estimate the channel coefficients from users in different cells with minimum mean square error, robust design and least square criterion, and then study the impact of uplink channel asymmetry on their performance. It is shown that when the large scale channel information is exploited for channel estimation, using non-orthogonal training sequences among users in different cells leads to minor performance loss. Next, we analyze the impact of downlink channel asymmetry on the performance of precoding with channel estimation errors. Our analysis shows that although the estimation errors of weak cross links are large, the resulting rate loss is minor because their contributions are weighted by the receive signal to noise ratio. The simulation results verify our analysis and show that the rate loss per user is almost constant no matter where the user is located, when the channel estimators exploiting the large scale fading gains.
Towards OpenMath Content Dictionaries as Linked Data
Venue: arXiv cs.DL 2010
Year: 2010

"The term 'Linked Data' refers to a set of best practices for publishing and connecting structured data on the web". Linked Data make the Semantic Web work practically, which means that information can be retrieved without complicated lookup mechanisms, that a lightweight semantics enables scalable reasoning, and that the decentral nature of the Web is respected. OpenMath Content Dictionaries (CDs) have the same characteristics - in principle, but not yet in practice. The Linking Open Data movement has made a considerable practical impact: Governments, broadcasting stations, scientific publishers, and many more actors are already contributing to the "Web of Data". Queries can be answered in a distributed way, and services aggregating data from different sources are replacing hard-coded mashups. However, these services are currently entirely lacking mathematical functionality. I will discuss real-world scenarios, where today's RDF-based Linked Data do not quite get their job done, but where an integration of OpenMath would help - were it not for certain conceptual and practical restrictions. I will point out conceptual shortcomings in the OpenMath 2 specification and common bad practices in publishing CDs and then propose concrete steps to overcome them and to contribute OpenMath CDs to the Web of Data.
Characterisation of observability and controllability for nonuniformly sampled discrete systems
Venue: arXiv cs.DM 2010
Year: 2010

A joint characterisation of the observability and controllability of a particular kind of discrete system has been developed. The key idea of the procedure can be reduced to a correct choice of the sampling sequence. This freedom, owing to the arbitrary choice of the sampling instants, is used to improve the sensitivity of system observability and controllability, by exploiting an adequate geometric structure. Some qualitative examples are presented for illustrative purposes.
Abstract Certification of Global Non-Interference in Rewriting Logic
Venue: arXiv cs.CR 2010
Year: 2010

Non-interference is a semantic program property that assigns confidentiality levels to data objects and prevents illicit information flows from occurring from high to low security levels. In this paper, we present a novel security model for global non-interference which approximates non-interference as a safety property. We also propose a certification technique for global non-interference of complete Java classes based on rewriting logic, a very general logical and semantic framework that is efficiently implemented in the high-level programming language Maude. Starting from an existing Java semantics specification written in Maude, we develop an extended, information-flow Java semantics that allows us to correctly observe global non-interference policies. In order to achieve a finite state transition system, we develop an abstract Java semantics that we use for secure and effective non-interference Java analysis. The analysis produces certificates that are independently checkable and are small enough to be used in practice.
Prize-Collecting Steiner Tree and Forest in Planar Graphs
Venue: arXiv cs.DS 2010
Year: 2010

We obtain polynomial-time approximation-preserving reductions (up to a factor of 1 + ε) from the prize-collecting Steiner tree and prize-collecting Steiner forest problems in planar graphs to the corresponding problems in graphs of bounded treewidth. We also give an exact algorithm for the prize-collecting Steiner tree problem that runs in polynomial time for graphs of bounded treewidth. This, combined with our reductions, yields a PTAS for the prize-collecting Steiner tree problem in planar graphs and generalizes the PTAS of Borradaile, Klein and Mathieu for the Steiner tree problem in planar graphs. Our results build upon the ideas of Borradaile, Klein and Mathieu and the work of Bateni, Hajiaghayi and Marx on a PTAS for the Steiner forest problem in planar graphs. Our main technical result is on the properties of primal-dual algorithms for Steiner tree and forest problems in general graphs when they are run with scaled up penalties.
On the Implementation of the Probabilistic Logic Programming Language ProbLog
Venue: arXiv cs.PL 2010
Year: 2010

The past few years have seen a surge of interest in the field of probabilistic logic learning and statistical relational learning. In this endeavor, many probabilistic logics have been developed. ProbLog is a recent probabilistic extension of Prolog motivated by the mining of large biological networks. In ProbLog, facts can be labeled with probabilities. These facts are treated as mutually independent random variables that indicate whether these facts belong to a randomly sampled program. Different kinds of queries can be posed to ProbLog programs. We introduce algorithms that allow the efficient execution of these queries, discuss their implementation on top of the YAP-Prolog system, and evaluate their performance in the context of large networks of biological entities.
Enhancing and Analyzing Search performance in Unstructured Peer to Peer Networks Using Enhanced Guided search protocol (EGSP)
Venue: arXiv cs.NI 2010
Year: 2010

Peer-to-peer (P2P) networks establish loosely coupled application-level overlays on top of the Internet to facilitate efficient sharing of resources. It can be roughly classified as either structured or unstructured networks. Without stringent constraints over the network topology, unstructured P2P networks can be constructed very efficiently and are therefore considered suitable to the Internet environment. However, the random search strategies adopted by these networks usually perform poorly with a large network size. To enhance the search performance in unstructured P2P networks through exploiting users' common interest patterns captured within a probability-theoretic framework termed the user interest model (UIM). A search protocol and a routing table updating protocol are further proposed in order to expedite the search process through self organizing the P2P network into a small world. Both theoretical and experimental analyses are conducted and demonstrated the effectiveness and efficiency of the approach.
Search Engine Optimization Techniques Practiced in Organizations: A Study of Four Organizations
Venue: arXiv cs.OH 2010
Year: 2010

Web spammers used Search Engine Optimization (SEO) techniques to increase search-ranking of web sites. In this paper we have study the essentials SEO techniques, such as; directory submission, keyword generation and link exchanges. The impact of SEO techniques can be applied as marketing technique and to get top listing in major search engines like Google, Yahoo, and MSN. Our study focuses on these techniques from four different companies' perspectives of United Kingdom and Pakistan. According to the these companies, these techniques are low cost and high impacts in profit, because mostly customers focus on major search engine to find different products on internet, so SEO technique provides best opportunity to grow their business. This paper also describes the pros and cons of using these searh engine optimization techniques in above four companies. We have concluded that these techniques are essential to increase their business profit and minimize their marketing cost.
Approaches, Challenges and Future Direction of Image Retrieval
Venue: arXiv cs.IR 2010
Year: 2010

This paper attempts to discuss the evolution of the retrieval approaches focusing on development, challenges and future direction of the image retrieval. It highlights both the already addressed and outstanding issues. The explosive growth of image data leads to the need of research and development of Image Retrieval. However, Image retrieval researches are moving from keyword, to low level features and to semantic features. Drive towards semantic features is due to the problem of the keywords which can be very subjective and time consuming while low level features cannot always describe high level concepts in the users' mind. Hence, introducing an interpretation inconsistency between image descriptors and high level semantics that known as the semantic gap. This paper also discusses the semantic gap issues, user query mechanisms as well as common ways used to bridge the gap in image retrieval.
A Framework for Constraint-Based Deployment and Autonomic Management of Distributed Applications
Venue: arXiv cs.DC 2010
Year: 2010

We propose a framework for deployment and subsequent autonomic management of component-based distributed applications. An initial deployment goal is specified using a declarative constraint language, expressing constraints over aspects such as component-host mappings and component interconnection topology. A constraint solver is used to find a configuration that satisfies the goal, and the configuration is deployed automatically. The deployed application is instrumented to allow subsequent autonomic management. If, during execution, the manager detects that the original goal is no longer being met, the satisfy/deploy process can be repeated automatically in order to generate a revised deployment that does meet the goal.
The Question of Expressiveness in the Generation of Referring Expressions
Venue: arXiv cs.LO 2010
Year: 2010

We study the problem of generating referring expressions modulo different notions of expressive power. We define the notion of $\+L$-referring expression, for a formal language $\+L$ equipped with a semantics in terms of relational models. We show that the approach is independent of the particular algorithm used to generate the referring expression by providing examples using the frameworks of \cite{AKS08} and \cite{Krahmer2003}. We provide some new complexity bounds, discuss the issue of the length of the generated descriptions, and propose ways in which the two approaches can be combined.
State Complexity of Two Combined Operations: Reversal-Catenation and Star-Catenation
Venue: arXiv cs.FL 2010
Year: 2010

In this paper, we show that, due to the structural properties of the resulting automaton obtained from a prior operation, the state complexity of a combined operation may not be equal but close to the mathematical composition of the state complexities of its component operations. In particular, we provide two witness combined operations: reversal combined with catenation and star combined with catenation.
Support for Evolving Software Architectures in the ArchWare ADL
Venue: arXiv cs.SE 2010
Year: 2010

Software that cannot evolve is condemned to atrophy: it cannot accommodate the constant revision and re-negotiation of its business goals nor intercept the potential of new technology. To accommodate change in software systems we have defined an active software architecture to be: dynamic in that the structure and cardinality of the components and interactions are changeable during execution; updatable in that components can be replaced; decomposable in that an executing system may be (partially) stopped and split up into its components and interactions; and reflective in that the specification of components and interactions may be evolved during execution. Here we describe the facilities of the ArchWare architecture description language (ADL) for specifying active architectures. The contribution of the work is the unique combination of concepts including: a π-calculus based communication and expression language for specifying executable architectures; hyper-code as an underlying representation of system execution that can be used for introspection; a decomposition operator to incrementally break up executing systems; and structural reflection for creating new components and binding them into running systems.
Active Sites model for the B-Matrix Approach
Venue: arXiv cs.NE 2010
Year: 2010

This paper continues on the work of the B-Matrix approach in hebbian learning proposed by Dr. Kak. It reports the results on methods of improving the memory retrieval capacity of the hebbian neural network which implements the B-Matrix approach. Previously, the approach to retrieving the memories from the network was to clamp all the individual neurons separately and verify the integrity of these memories. Here we present a network with the capability to identify the "active sites" in the network during the training phase and use these "active sites" to generate the memories retrieved from these neurons. Three methods are proposed for obtaining the update order of the network from the proximity matrix when multiple neurons are to be clamped. We then present a comparison between the new methods to the classical case and also among the methods themselves.
Toric degenerations of Bezier patches
Venue: arXiv cs.GR 2010
Year: 2010

The control polygon of a Bezier curve is well-defined and has geometric significance---there is a sequence of weights under which the limiting position of the curve is the control polygon. For a Bezier surface patch, there are many possible polyhedral control structures, and none are canonical. We propose a not necessarily polyhedral control structure for surface patches, regular control surfaces, which are certain C^0 spline surfaces. While not unique, regular control surfaces are exactly the possible limiting positions of a Bezier patch when the weights are allowed to vary.
Proof-theoretic Analysis of Rationality for Strategic Games with Arbitrary Strategy Sets
Venue: arXiv cs.GT 2010
Year: 2010

In the context of strategic games, we provide an axiomatic proof of the statement Common knowledge of rationality implies that the players will choose only strategies that survive the iterated elimination of strictly dominated strategies. Rationality here means playing only strategies one believes to be best responses. This involves looking at two formal languages. One is first-order, and is used to formalise optimality conditions, like avoiding strictly dominated strategies, or playing a best response. The other is a modal fixpoint language with expressions for optimality, rationality and belief. Fixpoints are used to form expressions for common belief and for iterated elimination of non-optimal strategies.
Enumeration Order Equivalency
Venue: arXiv cs.LO 2010
Year: 2010

In this paper we have investigated enumeration orders of elements of r.e. sets enumerated by means of Turing machines. We have defined a reducibility based on enumeration orders named "Enumeration Order Reducibility" on computable functions and also r.e. sets and studied their properties. Based on this reducibility we introduce an equivalence relation "Enumeration Order Equivalency". We have reached some properties of it. In subsequent, we have introduced another concept named "type-2 Enumeration Order Equivalency" and studied its properties too.