OpenRaiser/Intern-Atlas huggingface dataset:
T2Script Programming Language
Venue: arXiv cs.PL 2011
Year: 2011

Event-driven programming is used in many fields of modern Computer Science. In event-driven programming languages user interacts with a program by triggering the events. We propose a new approach that we denote command-event driven programming in which the user interacts with a program by means of events and commands. We describe a new programming language, T2Script, which is based on command-event driven paradigm. T2Script has been already implemented and used in one of industrial products. We describe the rationale, basic concepts and advanced programming techniques of new T2Script language. We evaluate the new language and show what advantages and limitations it has.
Active Markov Information-Theoretic Path Planning for Robotic Environmental Sensing
Venue: arXiv cs.LG 2011
Year: 2011

Recent research in multi-robot exploration and mapping has focused on sampling environmental fields, which are typically modeled using the Gaussian process (GP). Existing information-theoretic exploration strategies for learning GP-based environmental field maps adopt the non-Markovian problem structure and consequently scale poorly with the length of history of observations. Hence, it becomes computationally impractical to use these strategies for in situ, real-time active sampling. To ease this computational burden, this paper presents a Markov-based approach to efficient information-theoretic path planning for active sampling of GP-based fields. We analyze the time complexity of solving the Markov-based path planning problem, and demonstrate analytically that it scales better than that of deriving the non-Markovian strategies with increasing length of planning horizon. For a class of exploration tasks called the transect sampling task, we provide theoretical guarantees on the active sampling performance of our Markov-based policy, from which ideal environmental field conditions and sampling task settings can be established to limit its performance degradation due to violation of the Markov assumption. Empirical evaluation on real-world temperature and plankton density field data shows that our Markov-based policy can generally achieve active sampling performance comparable to that of the widely-used non-Markovian greedy policies under less favorable realistic field conditions and task settings while enjoying significant computational gain over them.
Perfect Matchings in 4-uniform hypergraphs
Venue: arXiv cs.DM 2011
Year: 2011

A perfect matching in a 4-uniform hypergraph is a subset of $\lfloor\frac{n}{4}\rfloor$ disjoint edges. We prove that if $H$ is a sufficiently large 4-uniform hypergraph on $n=4k$ vertices such that every vertex belongs to more than ${n-1\choose 3} - {3n/4 \choose 3}$ edges then $H$ contains a perfect matching. This bound is tight and settles a conjecture of H{á}n, Person and Schacht.
The complexity of flood-filling games on graphs
Venue: arXiv cs.DS 2011
Year: 2011

We consider the complexity of problems related to the combinatorial game Free-Flood-It, in which players aim to make a coloured graph monochromatic with the minimum possible number of flooding operations. Although computing the minimum number of moves required to flood an arbitrary graph is known to be NP-hard, we demonstrate a polynomial time algorithm to compute the minimum number of moves required to link each pair of vertices. We apply this result to compute in polynomial time the minimum number of moves required to flood a path, and an additive approximation to this quantity for an arbitrary k x n board, coloured with a bounded number of colours, for any fixed k. On the other hand, we show that, for k>=3, determining the minimum number of moves required to flood a k x n board coloured with at least four colours remains NP-hard.
Multi-Edge type Unequal Error Protection LDPC codes
Venue: arXiv cs.IT 2011
Year: 2011

Irregular low-density parity check (LDPC) codes are particularly well-suited for transmission schemes that require unequal error protection (UEP) of the transmitted data due to the different connection degrees of its variable nodes. However, this UEP capability is strongly dependent on the connection profile among the protection classes. This paper applies a multi-edge type analysis of LDPC codes for optimizing such connection profile according to the performance requirements of each protection class. This allows the construction of UEP-LDPC codes where the difference between the performance of the protection classes can be adjusted and with an UEP capability that does not vanish as the number of decoding iterations grows.
A Design and Implementation of the Extended Andorra Model
Venue: arXiv cs.PL 2011
Year: 2011

Logic programming provides a high-level view of programming, giving implementers a vast latitude into what techniques to explore to achieve the best performance for logic programs. Towards obtaining maximum performance, one of the holy grails of logic programming has been to design computational models that could be executed efficiently and that would allow both for a reduction of the search space and for exploiting all the available parallelism in the application. These goals have motivated the design of the Extended Andorra Model, a model where goals that do not constrain non-deterministic goals can execute first. In this work we present and evaluate the Basic design for Extended Andorra Model (BEAM), a system that builds upon David H. D. Warren's original EAM with Implicit Control. We provide a complete description and implementation of the BEAM System as a set of rewrite and control rules. We present the major data structures and execution algorithms that are required for efficient execution, and evaluate system performance. A detailed performance study of our system is included. Our results show that the system achieves acceptable base performance, and that a number of applications benefit from the advanced search inherent to the EAM.
On Steganography in Lost Audio Packets
Venue: arXiv cs.CR 2011
Year: 2011

The paper presents a new hidden data insertion procedure based on estimated probability of the remaining time of the call for steganographic method called LACK (Lost Audio PaCKets steganography). LACK provides hidden communication for real-time services like Voice over IP. The analytical results presented in this paper concern the influence of LACK's hidden data insertion procedures on the method's impact on quality of voice transmission and its resistance to steganalysis. The proposed hidden data insertion procedure is also compared to previous steganogram insertion approach based on estimated remaining average call duration.
Spatially-Aware Comparison and Consensus for Clusterings
Venue: arXiv cs.LG 2011
Year: 2011

This paper proposes a new distance metric between clusterings that incorporates information about the spatial distribution of points and clusters. Our approach builds on the idea of a Hilbert space-based representation of clusters as a combination of the representations of their constituent points. We use this representation and the underlying metric to design a spatially-aware consensus clustering procedure. This consensus procedure is implemented via a novel reduction to Euclidean clustering, and is both simple and efficient. All of our results apply to both soft and hard clusterings. We accompany these algorithms with a detailed experimental evaluation that demonstrates the efficiency and quality of our techniques.
Control of Multi-Agent Formations with Only Shape Constraints
Venue: arXiv cs.SY 2011
Year: 2011

This paper considers a novel problem of how to choose an appropriate geometry for a group of agents with only shape constraints but with a flexible scale. Instead of assigning the formation system with a specific geometry, here the only requirement on the desired geometry is a shape without any location, rotation and, most importantly, scale constraints. Optimal rigid transformation between two different geometries is discussed with especial focus on the scaling operation, and the cooperative performance of the system is evaluated by what we call the geometries degrees of similarity (DOS) with respect to the desired shape during the entire convergence process. The design of the scale when measuring the DOS is discussed from constant value and time-varying function perspectives respectively. Fixed structured nonlinear control laws that are functions on the scale are developed to guarantee the exponential convergence of the system to the assigned shape. Our research is originated from a three-agent formation system and is further extended to multiple (n > 3) agents by defining a triangular complement graph. Simulations demonstrate that formation system with the time-varying scale function outperforms the one with an arbitrary constant scale, and the relationship between underlying topology and the system performance is further discussed based on the simulation observations. Moveover, the control scheme is applied to bearing-only sensor-target localization to show its application potentials.
Combined Data Structure for Previous- and Next-Smaller-Values
Venue: arXiv cs.DS 2011
Year: 2011

Let $A$ be a static array storing $n$ elements from a totally ordered set. We present a data structure of optimal size at most $n\log_2(3+2\sqrt{2})+o(n)$ bits that allows us to answer the following queries on $A$ in constant time, without accessing $A$: (1) previous smaller value queries, where given an index $i$, we wish to find the first index to the left of $i$ where $A$ is strictly smaller than at $i$, and (2) next smaller value queries, which search to the right of $i$. As an additional bonus, our data structure also allows to answer a third kind of query: given indices $i<j$, find the position of the minimum in $A[i..j]$. Our data structure has direct consequences for the space-efficient storage of suffix trees.
Matrix method for the multi salesmen problem (TSP) with several vehicles
Venue: arXiv cs.DS 2011
Year: 2011

In this paper discussed procedure of separation of the original problem with several vehicles to a number of simpler problems with one vehicle which based on the matrix approach.
Design of an Efficient Neural Key Distribution Centre
Venue: arXiv cs.CR 2011
Year: 2011

The goal of any cryptographic system is the exchange of information among the intended users without any leakage of information to others who may have unauthorized access to it. A common secret key could be created over a public channel accessible to any opponent. Neural networks can be used to generate common secret key. In case of neural cryptography, both the communicating networks receive an identical input vector, generate an output bit and are trained based on the output bit. The two networks and their weight vectors exhibit a novel phenomenon, where the networks synchronize to a state with identical time-dependent weights. The generated secret key over a public channel is used for encrypting and decrypting the information being sent on the channel. This secret key is distributed to the other vendor efficiently by using an agent based approach.
Information theory of massively parallel probe storage channels
Venue: arXiv cs.IT 2011
Year: 2011

Motivated by the concept of probe storage, we study the problem of information retrieval using a large array of N nano-mechanical probes, N ~ 4000. At the nanometer scale it is impossible to avoid errors in the positioning of the array, thus all signals retrieved by the probes of the array at a given sampling moment are affected by the same amount of random position jitter. Therefore a massively parallel probe storage device is an example of a noisy communication channel with long range correlations between channel outputs due to the global positioning errors. We find that these correlations have a profound effect on the channel's properties. For example, it turns out that the channel's information capacity does approach 1 bit per probe in the limit of high signal-to-noise ratio, but the rate of the approach is only polynomial in the channel noise strength. Moreover, any error correction code with block size N >> 1 such that codewords correspond to the instantaneous outputs of the all probes in the array exhibits an error floor independently of the code rate. We illustrate this phenomenon explicitly using Reed-Solomon codes the performance of which is easy to simulate numerically. We also discuss capacity-achieving error correction codes for the global jitter channel and their complexity.
Adaptive Population Models for Offspring Populations and Parallel Evolutionary Algorithms
Venue: arXiv cs.DS 2011
Year: 2011

We present two adaptive schemes for dynamically choosing the number of parallel instances in parallel evolutionary algorithms. This includes the choice of the offspring population size in a (1+$λ$) EA as a special case. Our schemes are parameterless and they work in a black-box setting where no knowledge on the problem is available. Both schemes double the number of instances in case a generation ends without finding an improvement. In a successful generation, the first scheme resets the system to one instance, while the second scheme halves the number of instances. Both schemes provide near-optimal speed-ups in terms of the parallel time. We give upper bounds for the asymptotic sequential time (i.e., the total number of function evaluations) that are not larger than upper bounds for a corresponding non-parallel algorithm derived by the fitness-level method.
Probabilistic and quantum finite automata with postselection
Venue: arXiv cs.CC 2011
Year: 2011

We prove that endowing a real-time probabilistic or quantum computer with the ability of postselection increases its computational power. For this purpose, we provide a new model of finite automata with postselection, and compare it with the model of Lāce et al. We examine the related language classes, and also establish separations between the classical and quantum versions, and between the zero-error vs. bounded-error modes of recognition in this model.
Analyzing the Impact of Visitors on Page Views with Google Analytics
Venue: arXiv cs.IR 2011
Year: 2011

This paper develops a flexible methodology to analyze the effectiveness of different variables on various dependent variables which all are times series and especially shows how to use a time series regression on one of the most important and primary index (page views per visit) on Google analytic and in conjunction it shows how to use the most suitable data to gain a more accurate result. Search engine visitors have a variety of impact on page views which cannot be described by single regression. On one hand referral visitors are well-fitted on linear regression with low impact. On the other hand, direct visitors made a huge impact on page views. The higher connection speed does not simply imply higher impact on page views and the content of web page and the territory of visitors can help connection speed to describe user behavior. Returning visitors have some similarities with direct visitors.
Conical Existence of Closed Curves on Convex Polyhedra
Venue: arXiv cs.DM 2011
Year: 2011

Let C be a simple, closed, directed curve on the surface of a convex polyhedron P. We identify several classes of curves C that "live on a cone," in the sense that C and a neighborhood to one side may be isometrically embedded on the surface of a cone Lambda, with the apex a of Lambda enclosed inside (the image of) C; we also prove that each point of C is "visible to" a. In particular, we obtain that these curves have non-self-intersecting developments in the plane. Moreover, the curves we identify that live on cones to both sides support a new type of "source unfolding" of the entire surface of P to one non-overlapping piece, as reported in a companion paper.
Applying causality principles to the axiomatization of probabilistic cellular automata
Venue: arXiv cs.DM 2011
Year: 2011

Cellular automata (CA) consist of an array of identical cells, each of which may take one of a finite number of possible states. The entire array evolves in discrete time steps by iterating a global evolution G. Further, this global evolution G is required to be shift-invariant (it acts the same everywhere) and causal (information cannot be transmitted faster than some fixed number of cells per time step). At least in the classical, reversible and quantum cases, these two top-down axiomatic conditions are sufficient to entail more bottom-up, operational descriptions of G. We investigate whether the same is true in the probabilistic case. Keywords: Characterization, noise, Markov process, stochastic Einstein locality, screening-off, common cause principle, non-signalling, Multi-party non-local box.
Universal Sets for Straight-Line Embeddings of Bicolored Graphs
Venue: arXiv cs.DM 2011
Year: 2011

A set S of n points is 2-color universal for a graph G on n vertices if for every proper 2-coloring of G and for every 2-coloring of S with the same sizes of color classes as G has, G is straight-line embeddable on S. We show that the so-called double chain is 2-color universal for paths if each of the two chains contains at least one fifth of all the points, but not if one of the chains is more than approximately 28 times longer than the other. A 2-coloring of G is equitable if the sizes of the color classes differ by at most 1. A bipartite graph is equitable if it admits an equitable proper coloring. We study the case when S is the double-chain with chain sizes differing by at most 1 and G is an equitable bipartite graph. We prove that this S is not 2-color universal if G is not a forest of caterpillars and that it is 2-color universal for equitable caterpillars with at most one half non-leaf vertices. We also show that if this S is equitably 2-colored, then equitably properly 2-colored forests of stars can be embedded on it.
Splicing systems and the Chomsky hierarchy
Venue: arXiv cs.FL 2011
Year: 2011

In this paper, we prove decidability properties and new results on the position of the family of languages generated by (circular) splicing systems within the Chomsky hierarchy. The two main results of the paper are the following. First, we show that it is decidable, given a circular splicing language and a regular language, whether they are equal. Second, we prove the language generated by an alphabetic splicing system is context-free. Alphabetic splicing systems are a generalization of simple and semi-simple splicin systems already considered in the literature.
Structured interference-mitigation in two-hop networks
Venue: arXiv cs.IT 2011
Year: 2011

We consider two-hop S-R-D Gaussian networks with a source (S), a relay (R) and a destination (D), some of which experience additive interference. This additive interference, which renders the channels state-dependent, is either a) experienced at the destination D and known non-causally at the source S, or b) experienced at the relay R and known at the destination D. In both cases, one would hope to exploit this knowledge of the channel state at some of the nodes to obtain "clean" or interference-free channels, just as Costa's dirty-paper coding does for one-hop channels with state non-causally known to the transmitter. We demonstrate a scheme which achieves to within 0.5 bit of a "clean" channel. This novel scheme is based on nested-lattice code and a Decode-and-Forward (DF) relay. Intuitively, this strategy uses the structure provided by nested lattice codes to cancel the "integer" (or lattice quantized) part of the interference and treats the "residual" (or quantization noise) as noise.
A Decade of Database Research Publications
Venue: arXiv cs.DL 2011
Year: 2011

We analyze the database research publications of four major core database technology conferences (SIGMOD, VLDB, ICDE, EDBT), two main theoretical database conferences (PODS, ICDT) and three database journals (TODS, VLDB Journal, TKDE) over a period of 10 years (2001 - 2010). Our analysis considers only regular papers as we do not include short papers, demo papers, posters, tutorials or panels into our statistics. We rank the research scholars according to their number of publication in each conference/journal separately and in combined. We also report about the growth in the number of research publications and the size of the research community in the last decade.
Local Maximum Stable Sets Greedoids Stemmed from Very Well-Covered Graphs
Venue: arXiv cs.DM 2011
Year: 2011

A maximum stable set in a graph G is a stable set of maximum cardinality. S is called a local maximum stable set of G if S is a maximum stable set of the subgraph induced by the closed neighborhood of S. A greedoid (V,F) is called a local maximum stable set greedoid if there exists a graph G=(V,E) such that its family of local maximum stable sets coinsides with (V,F). It has been shown that the family local maximum stable sets of a forest T forms a greedoid on its vertex set. In this paper we demonstrate that if G is a very well-covered graph, then its family of local maximum stable sets is a greedoid if and only if G has a unique perfect matching.
CDTOM: A Context-driven Task-oriented Middleware for Pervasive Homecare Environment
Venue: arXiv cs.HC 2011
Year: 2011

With the growing number of the elderly, we see a greater demand for home care, and the vision of pervasive computing is also floating into the domain of the household that aims to build a smart home which can assist inhabitants (users) to live more conveniently and harmoniously. Such health-care pervasive applications in smart home should focus on the inhabitant's goal or task in diverse situations, rather than the various complex devices and services. The core challenge for homecare design is to perceive the environment and assess occurring situations, thus allowing systems to behave intelligently according to the user's intent. Due to the dynamic and heterogeneous nature of pervasive computing environment, it is difficult for an average user to obtain right information and service and in right place at right time. This paper proposes a context-driven task-oriented middleware (CDTOM) to meet the challenge. The most important component is its task model that provides an adequate high-level description of user-oriented tasks and their related contexts. Leveraging the model multiple entities can easily exchange, share and reuse their knowledge. Based on the hierarchy of task ontology, a novel task recognition approach using CBR (case-based reasoning) is presented and the performance of task recognition is evaluated by task number, context size and time costing. Moreover, a dynamic mechanism for mapping the recognized task and services is also discussed. Finally, we present the design and implementation of our task supporting system (TSS) to aid an inhabitant's tasks in light of his lifestyle and environment conditions in pervasive homecare environment, and the results of the prototype system show that our middleware approach achieves good efficiency of context management and good accuracy of user's activity inference, and can improve efficiently quality of user's life.
The hardness of Median in the synchronized bit communication model
Venue: arXiv cs.CC 2011
Year: 2011

The synchronized bit communication model, defined recently by Impagliazzo and Williams in \emph{Communication complexity with synchronized clocks}, CCC '10, is a communication model which allows the participants to share a common clock. The main open problem posed in this paper was the following: does the synchronized bit model allow a logarithmic speed-up for all functions over the standard deterministic model of communication? We resolve this question in the negative by showing that the Median function, whose communication complexity is $O(\log n)$, does not admit polytime synchronized bit protocol with communication complexity $O\left(\log^{1-ε} n\right)$ for any $ε> 0$. Our results follow by a new round-communication trade-off for the Median function in the standard model, which easily translates to its hardness in the synchronized bit model.