OpenRaiser/Intern-Atlas huggingface dataset:
On the Information of the Second Moments Between Random Variables Using Mutually Unbiased Bases
Venue: arXiv cs.IT 2007
Year: 2007

The notation of mutually unbiased bases(MUB) was first introduced by Ivanovic to reconstruct density matrixes\cite{Ivanovic}. The subject about how to use MUB to analyze, process, and utilize the information of the second moments between random variables is studied in this paper. In the first part, the mathematical foundation will be built. It will be shown that the spectra of MUB have complete information for the correlation matrixes of finite discrete signals, and the nice properties of them. Roughly speaking, it will be shown that each spectrum from MUB plays an equal role for finite discrete signals, and the effect between any two spectra can be treated as a global constant shift. These properties will be used to find some important and natural characterizations of random vectors and random discrete operators/filters. For a technical reason, it will be shown that any MUB spectra can be found as fast as Fourier spectrum when the length of the signal is a prime number. In the second part, some applications will be presented. First of all, a protocol about how to increase the number of users in a basic digital communication model will be studied, which has bring some deep insights about how to encode the information into the second moments between random variables. Secondly, the application of signal analysis will be studied. It is suggested that complete "MUB" spectra analysis works well in any case, and people can just choose the spectra they are interested in to do analysis. For instance, single Fourier spectra analysis can be also applied in nonstationary case. Finally, the application of MUB in dimensionality reduction will be considered, when the prior knowledge of the data isn't reliable.
Some A Priori Torah Decryption Principles
Venue: arXiv cs.CR 2007
Year: 2007

The author proposes, a priori, a simple set of principles that can be developed into a range of algorithms by which means the Torah might be decoded. It is assumed that the Torah is some form of transposition cipher with the unusual property that the plain text of the Torah may also be the cipher text of one or more other documents written in Biblical Hebrew. The decryption principles are based upon the use of Equidistant Letter Sequences (ELS) and the notions of Message Length, Dimensionality, Euclidean Dimension, Topology, Read Direction, Skip Distance and offset. The principles can be applied recursively and define numerous large subsets of the 304,807! theoretically possible permutations of the characters of the Torah.
Automata-based Adaptive Behavior for Economical Modelling Using Game Theory
Venue: arXiv cs.GT 2007
Year: 2007

In this chapter, we deal with some specific domains of applications to game theory. This is one of the major class of models in the new approaches of modelling in the economic domain. For that, we use genetic automata which allow to build adaptive strategies for the players. We explain how the automata-based formalism proposed - matrix representation of automata with multiplicities - allows to define semi-distance between the strategy behaviors. With that tools, we are able to generate an automatic processus to compute emergent systems of entities whose behaviors are represented by these genetic automata.
Algorithms for Generating Convex Sets in Acyclic Digraphs
Venue: arXiv cs.DM 2007
Year: 2007

A set $X$ of vertices of an acyclic digraph $D$ is convex if $X\neq \emptyset$ and there is no directed path between vertices of $X$ which contains a vertex not in $X$. A set $X$ is connected if $X\neq \emptyset$ and the underlying undirected graph of the subgraph of $D$ induced by $X$ is connected. Connected convex sets and convex sets of acyclic digraphs are of interest in the area of modern embedded processor technology. We construct an algorithm $\cal A$ for enumeration of all connected convex sets of an acyclic digraph $D$ of order $n$. The time complexity of $\cal A$ is $O(n\cdot cc(D))$, where $cc(D)$ is the number of connected convex sets in $D$. We also give an optimal algorithm for enumeration of all (not just connected) convex sets of an acyclic digraph $D$ of order $n$. In computational experiments we demonstrate that our algorithms outperform the best algorithms in the literature. Using the same approach as for $\cal A$, we design an algorithm for generating all connected sets of a connected undirected graph $G$. The complexity of the algorithm is $O(n\cdot c(G)),$ where $n$ is the order of $G$ and $c(G)$ is the number of connected sets of $G.$ The previously reported algorithm for connected set enumeration is of running time $O(mn\cdot c(G))$, where $m$ is the number of edges in $G.$
The source coding game with a cheating switcher
Venue: arXiv cs.IT 2007
Year: 2007

Motivated by the lossy compression of an active-vision video stream, we consider the problem of finding the rate-distortion function of an arbitrarily varying source (AVS) composed of a finite number of subsources with known distributions. Berger's paper `The Source Coding Game', \emph{IEEE Trans. Inform. Theory}, 1971, solves this problem under the condition that the adversary is allowed only strictly causal access to the subsource realizations. We consider the case when the adversary has access to the subsource realizations non-causally. Using the type-covering lemma, this new rate-distortion function is determined to be the maximum of the IID rate-distortion function over a set of source distributions attainable by the adversary. We then extend the results to allow for partial or noisy observations of subsource realizations. We further explore the model by attempting to find the rate-distortion function when the adversary is actually helpful. Finally, a bound is developed on the uniform continuity of the IID rate-distortion function for finite-alphabet sources. The bound is used to give a sufficient number of distributions that need to be sampled to compute the rate-distortion function of an AVS to within a certain accuracy. The bound is also used to give a rate of convergence for the estimate of the rate-distortion function for an unknown IID finite-alphabet source .
A Class of LULU Operators on Multi-Dimensional Arrays
Venue: arXiv cs.CV 2007
Year: 2007

The LULU operators for sequences are extended to multi-dimensional arrays via the morphological concept of connection in a way which preserves their essential properties, e.g. they are separators and form a four element fully ordered semi-group. The power of the operators is demonstrated by deriving a total variation preserving discrete pulse decomposition of images.
Partial Conway and iteration semirings
Venue: arXiv cs.DM 2007
Year: 2007

A Conway semiring is a semiring $S$ equipped with a unary operation $^*:S \to S$, always called 'star', satisfying the sum star and product star identities. It is known that these identities imply a Kleene type theorem. Some computationally important semirings, such as $N$ or $N^{\rat}\llangle Σ^* \rrangle$ of rational power series of words on $Σ$ with coefficients in $N$, cannot have a total star operation satisfying the Conway identities. We introduce here partial Conway semirings, which are semirings $S$ which have a star operation defined only on an ideal of $S$; when the arguments are appropriate, the operation satisfies the above identities. We develop the general theory of partial Conway semirings and prove a Kleene theorem for this generalization.
Proxy Signature Scheme with Effective Revocation Using Bilinear Pairings
Venue: arXiv cs.CR 2007
Year: 2007

We present a proxy signature scheme using bilinear pairings that provides effective proxy revocation. The scheme uses a binding-blinding technique to avoid secure channel requirements in the key issuance stage. With this technique, the signer receives a partial private key from a trusted authority and unblinds it to get his private key, in turn, overcomes the key escrow problem which is a constraint in most of the pairing-based proxy signature schemes. The scheme fulfills the necessary security requirements of proxy signature and resists other possible threats.
Optimizing Queries in a Logic-based Information Integration System
Venue: arXiv cs.PL 2007
Year: 2007

The SINTAGMA information integration system is an infrastructure for accessing several different information sources together. Besides providing a uniform interface to the information sources (databases, web services, web sites, RDF resources, XML files), semantic integration is also needed. Semantic integration is carried out by providing a high-level model and the mappings to the models of the sources. When executing a query of the high level model, a query is transformed to a low-level query plan, which is a piece of Prolog code that answers the high-level query. This transformation is done in two phases. First, the Query Planner produces a plan as a logic formula expressing the low-level query. Next, the Query Optimizer transforms this formula to executable Prolog code and optimizes it according to structural and statistical information about the information sources. This article discusses the main ideas of the optimization algorithm and its implementation.
Interval Colourings of Some Regular Graphs
Venue: arXiv cs.DM 2007
Year: 2007

A lower bound is obtained for the greatest possible number of colors in an interval colourings of some regular graphs.
On Interval Colorings of Complete k-partite Graphs K_{n}^{k}
Venue: arXiv cs.DM 2007
Year: 2007

Problems of existence, construction and estimation of parameters of interval colorings of complete k-partite graphs K_{n}^{k} are investigated.
CLAIRLIB Documentation v1.03
Venue: arXiv cs.IR 2007
Year: 2007

The Clair library is intended to simplify a number of generic tasks in Natural Language Processing (NLP), Information Retrieval (IR), and Network Analysis. Its architecture also allows for external software to be plugged in with very little effort. Functionality native to Clairlib includes Tokenization, Summarization, LexRank, Biased LexRank, Document Clustering, Document Indexing, PageRank, Biased PageRank, Web Graph Analysis, Network Generation, Power Law Distribution Analysis, Network Analysis (clustering coefficient, degree distribution plotting, average shortest path, diameter, triangles, shortest path matrices, connected components), Cosine Similarity, Random Walks on Graphs, Statistics (distributions, tests), Tf, Idf, Community Finding.
Universal Intelligence: A Definition of Machine Intelligence
Venue: arXiv cs.AI 2007
Year: 2007

A fundamental problem in artificial intelligence is that nobody really knows what intelligence is. The problem is especially acute when we need to consider artificial systems which are significantly different to humans. In this paper we approach this problem in the following way: We take a number of well known informal definitions of human intelligence that have been given by experts, and extract their essential features. These are then mathematically formalised to produce a general measure of intelligence for arbitrary machines. We believe that this equation formally captures the concept of machine intelligence in the broadest reasonable sense. We then show how this formal definition is related to the theory of universal optimal learning agents. Finally, we survey the many other tests and definitions of intelligence that have been proposed for machines.
Compressed Text Indexes:From Theory to Practice!
Venue: arXiv cs.DS 2007
Year: 2007

A compressed full-text self-index represents a text in a compressed form and still answers queries efficiently. This technology represents a breakthrough over the text indexing techniques of the previous decade, whose indexes required several times the size of the text. Although it is relatively new, this technology has matured up to a point where theoretical research is giving way to practical developments. Nonetheless this requires significant programming skills, a deep engineering effort, and a strong algorithmic background to dig into the research results. To date only isolated implementations and focused comparisons of compressed indexes have been reported, and they missed a common API, which prevented their re-use or deployment within other applications. The goal of this paper is to fill this gap. First, we present the existing implementations of compressed indexes from a practitioner's point of view. Second, we introduce the Pizza&Chili site, which offers tuned implementations and a standardized API for the most successful compressed full-text self-indexes, together with effective testbeds and scripts for their automatic validation and test. Third, we show the results of our extensive experiments on these codes with the aim of demonstrating the practical relevance of this novel and exciting technology.
Extending the Overlap Graph for Gene Assembly in Ciliates
Venue: arXiv cs.LO 2007
Year: 2007

Gene assembly is an intricate biological process that has been studied formally and modeled through string and graph rewriting systems. Recently, a restriction of the general (intramolecular) model, called simple gene assembly, has been introduced. This restriction has subsequently been defined as a string rewriting system. We show that by extending the notion of overlap graph it is possible to define a graph rewriting system for two of the three types of rules that make up simple gene assembly. It turns out that this graph rewriting system is less involved than its corresponding string rewriting system. Finally, we give characterizations of the `power' of both types of graph rewriting rules. Because of the equivalence of these string and graph rewriting systems, the given characterizations can be carried over to the string rewriting system.
Tuplix Calculus
Venue: arXiv cs.LO 2007
Year: 2007

We introduce a calculus for tuplices, which are expressions that generalize matrices and vectors. Tuplices have an underlying data type for quantities that are taken from a zero-totalized field. We start with the core tuplix calculus CTC for entries and tests, which are combined using conjunctive composition. We define a standard model and prove that CTC is relatively complete with respect to it. The core calculus is extended with operators for choice, information hiding, scalar multiplication, clearing and encapsulation. We provide two examples of applications; one on incremental financial budgeting, and one on modular financial budget design.
Hopf bifurcation analysis in a dual model of Internet congestion control algorithm with communication delay
Venue: arXiv cs.NI 2007
Year: 2007

This paper focuses on the delay induced Hopf bifurcation in a dual model of Internet congestion control algorithms which can be modeled as a time-delay system described by a one-order delay differential equation (DDE). By choosing communication delay as the bifurcation parameter, we demonstrate that the system loses its stability and a Hopf bifurcation occurs when communication delay passes through a critical value. Moreover, the bifurcating periodic solution of system is calculated by means of perturbation methods. Discussion of stability of the periodic solutions involves the computation of Floquet exponents by considering the corresponding Poincare -Lindstedt series expansion. Finally, numerical simulations for verify the theoretical analysis are provided.
Bottleneck flows in networks
Venue: arXiv cs.DS 2007
Year: 2007

The bottleneck network flow problem (BNFP) is a generalization of several well-studied bottleneck problems such as the bottleneck transportation problem (BTP), bottleneck assignment problem (BAP), bottleneck path problem (BPP), and so on. In this paper we provide a review of important results on this topic and its various special cases. We observe that the BNFP can be solved as a sequence of $O(\log n)$ maximum flow problems. However, special augmenting path based algorithms for the maximum flow problem can be modified to obtain algorithms for the BNFP with the property that these variations and the corresponding maximum flow algorithms have identical worst case time complexity. On unit capacity network we show that BNFP can be solved in $O(\min \{{m(n\log n)}^{2/3}, m^{3/2}\sqrt{\log n}\})$. This improves the best available algorithm by a factor of $\sqrt{\log n}$. On unit capacity simple graphs, we show that BNFP can be solved in $O(m \sqrt {n \log n})$ time. As a consequence we have an $O(m \sqrt {n \log n})$ algorithm for the BTP with unit arc capacities.
Asymptotic Mutual Information Statistics of Separately-Correlated Rician Fading MIMO Channels
Venue: arXiv cs.IT 2007
Year: 2007

Precise characterization of the mutual information of MIMO systems is required to assess the throughput of wireless communication channels in the presence of Rician fading and spatial correlation. Here, we present an asymptotic approach allowing to approximate the distribution of the mutual information as a Gaussian distribution in order to provide both the average achievable rate and the outage probability. More precisely, the mean and variance of the mutual information of the separatelycorrelated Rician fading MIMO channel are derived when the number of transmit and receive antennas grows asymptotically large and their ratio approaches a finite constant. The derivation is based on the replica method, an asymptotic technique widely used in theoretical physics and, more recently, in the performance analysis of communication (CDMA and MIMO) systems. The replica method allows to analyze very difficult system cases in a comparatively simple way though some authors pointed out that its assumptions are not always rigorous. Being aware of this, we underline the key assumptions made in this setting, quite similar to the assumptions made in the technical literature using the replica method in their asymptotic analyses. As far as concerns the convergence of the mutual information to the Gaussian distribution, it is shown that it holds under some mild technical conditions, which are tantamount to assuming that the spatial correlation structure has no asymptotically dominant eigenmodes. The accuracy of the asymptotic approach is assessed by providing a sizeable number of numerical results. It is shown that the approximation is very accurate in a wide variety of system settings even when the number of transmit and receive antennas is as small as a few units.
Security in Wireless Sensor Networks: Issues and Challenges
Venue: arXiv cs.NI 2007
Year: 2007

Wireless Sensor Network (WSN) is an emerging technology that shows great promise for various futuristic applications both for mass public and military. The sensing technology combined with processing power and wireless communication makes it lucrative for being exploited in abundance in future. The inclusion of wireless communication technology also incurs various types of security threats. The intent of this paper is to investigate the security related issues and challenges in wireless sensor networks. We identify the security threats, review proposed security mechanisms for wireless sensor networks. We also discuss the holistic view of security for ensuring layered and robust security in wireless sensor networks.
A Secure Lightweight Approach of Node Membership Verification in Dense HDSN
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, we consider a particular type of deployment scenario of a distributed sensor network (DSN), where sensors of different types and categories are densely deployed in the same target area. In this network, the sensors are associated with different groups, based on their functional types and after deployment they collaborate with one another in the same group for doing any assigned task for that particular group. We term this sort of DSN as a heterogeneous distributed sensor network (HDSN). Considering this scenario, we propose a secure membership verification mechanism using one-way accumulator (OWA) which ensures that, before collaborating for a particular task, any pair of nodes in the same deployment group can verify each other-s legitimacy of membership. Our scheme also supports addition and deletion of members (nodes) in a particular group in the HDSN. Our analysis shows that, the proposed scheme could work well in conjunction with other security mechanisms for sensor networks and is very effective to resist any adversary-s attempt to be included in a legitimate group in the network.
Convergence of Expected Utilities with Algorithmic Probability Distributions
Venue: arXiv cs.AI 2007
Year: 2007

We consider an agent interacting with an unknown environment. The environment is a function which maps natural numbers to natural numbers; the agent's set of hypotheses about the environment contains all such functions which are computable and compatible with a finite set of known input-output pairs, and the agent assigns a positive probability to each such hypothesis. We do not require that this probability distribution be computable, but it must be bounded below by a positive computable function. The agent has a utility function on outputs from the environment. We show that if this utility function is bounded below in absolute value by an unbounded computable function, then the expected utility of any input is undefined. This implies that a computable utility function will have convergent expected utilities iff that function is bounded.
Concepts and their Use for Modelling Objects and References in Programming Languages
Venue: arXiv cs.PL 2007
Year: 2007

In the paper a new programming construct, called concept, is introduced. Concept is pair of two classes: a reference class and an object class. Instances of the reference classes are passed-by-value and are intended to represent objects. Instances of the object class are passed-by-reference. An approach to programming where concepts are used instead of classes is called concept-oriented programming (CoP). In CoP objects are represented and accessed indirectly by means of references. The structure of concepts describes a hierarchical space with a virtual address system. The paper describes this new approach to programming including such mechanisms as reference resolution, complex references, method interception, dual methods, life-cycle management inheritance and polymorphism.
Principles of the Concept-Oriented Data Model
Venue: arXiv cs.DB 2007
Year: 2007

In the paper a new approach to data representation and manipulation is described, which is called the concept-oriented data model (CODM). It is supposed that items represent data units, which are stored in concepts. A concept is a combination of superconcepts, which determine the concept's dimensionality or properties. An item is a combination of superitems taken by one from all the superconcepts. An item stores a combination of references to its superitems. The references implement inclusion relation or attribute-value relation among items. A concept-oriented database is defined by its concept structure called syntax or schema and its item structure called semantics. The model defines formal transformations of syntax and semantics including the canonical semantics where all concepts are merged and the data semantics is represented by one set of items. The concept-oriented data model treats relations as subconcepts where items are instances of the relations. Multi-valued attributes are defined via subconcepts as a view on the database semantics rather than as a built-in mechanism. The model includes concept-oriented query language, which is based on collection manipulations. It also has such mechanisms as aggregation and inference based on semantics propagation through the database schema.