Search results for "BINARY"
showing 10 items of 833 documents
Distributed Pseudo-Gossip Algorithm and Finite-Length Computational Codes for Efficient In-Network Subspace Projection
2013
In this paper, we design a practical power-efficient algorithm for Wireless Sensor Networks (WSN) in order to obtain, in a distributed manner, the projection of an observed sampled spatial field on a subspace of lower dimension. This is an important problem that is motivated in various applications where there are well defined subspaces of interest (e.g., spectral maps in cognitive radios). As opposed to traditional Gossip Algorithms used for subspace projection, where separation of channel coding and computation is assumed, our algorithm combines binary finite-length Computational Coding and a novel gossip-like protocol with certain communication rules, achieving important savings in conve…
Balance Properties and Distribution of Squares in Circular Words
2008
We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalised to non periodic infinite words as well.
Weak associativity and restricted rotation
2009
A restricted rotation induced by a weak associative law is introduced. The corresponding equivalence relation is identical to the Glivenko congruence on Tamari lattices, i.e. lattices of binary trees endowed by the well-known rotation operation.
Balanced Words Having Simple Burrows-Wheeler Transform
2009
The investigation of the "clustering effect" of the Burrows-Wheeler transform (BWT) leads to study the words having simple BWT , i.e. words w over an ordered alphabet $A=\{a_1,a_2,\ldots,a_k\}$, with $a_1 < a_2 < \ldots <a_k$, such that $bwt(w)$ is of the form $a_k^{n_k} a_{k-1}^{n_{k-1}} \cdots a_1^{n_1}$, for some non-negative integers $n_1, n_2, \ldots, n_k$. We remark that, in the case of binary alphabets, there is an equivalence between words having simple BWT, the family of (circular) balanced words and the conjugates of standard words. In the case of alphabets of size greater than two, there is no more equivalence between these notions. As a main result of this paper we prove that, u…
On the Quadratic Type of Some Simple Self-Dual Modules over Fields of Characteristic Two
1997
Let G be a finite group and let K be an algebraically closed field of Ž characteristic 2. Let V be a non-trivial simple self-dual KG-module we . say that V is self-dual if it is isomorphic to its dual V * . It is a theorem of w x Fong 4, Lemma 1 that in this case there is a non-degenerate G-invariant alternating bilinear form, F, say, defined on V = V. We say that V is a KG-module of quadratic type if F is the polarization of a non-degenerate w x G-invariant quadratic form defined on V. In a previous paper 6 , the present authors described some methods to decide if such a module V is of w x quadratic type. One of the main results of 6 is the following. Suppose that Ž . G is a group with a s…
When can an equational simple graph be generated by hyperedge replacement?
1998
Infinite hypergraphs with sources arise as the canonical solutions of certain systems of recursive equations written with operations on hypergraphs. There are basically two different sets of such operations known from the literature, HR and VR. VR is strictly more powerful than HR on simple hypergraphs. Necessary conditions are known ensuring that a VR-equational simple hypergraph is also HR-equational. We prove that two of them, namely having finite tree-width or not containing the infinite bipartite graph, are also sufficient. This shows that equational hypergraphs behave like context-free sets of finite hypergraphs.
Ranking and unrankingk-ary trees with a 4k –4 letter alphabet
1997
Abstract The problem of the direct generation in A-order of binary trees was stated by Zaks in 1980. In 1988 Roelants van Baronaigien and Ruskey gave a solution for k-ary trees with n internal nodes using an encoding sequence of kn+1 integers between 1 and n. Vajnovszki and Pallo improved this result for binary trees in 1994 using words of length n–1 on a four letter alphabet. Recently Korsh generalized the Vajnovszki and Pallo’s generating algorithm to k-ary trees using an alphabet whose cardinality depends on k but not on n. We give in this paper ranking and unranking algorithms for k-ary trees using the Korsh’s encoding scheme.
A Loopless Generation of Bitstrings without p Consecutive Ones
2001
Let F n (p) be the set of all n-length bitstrings such that there are no p consecutive ls. F n (p) is counted with the pth order Fibonacci numbers and it may be regarded as the subsets of {1, 2,…, n} without p consecutive elements and bitstrings in F n (p) code a particular class of trees or compositions of an integer. In this paper we give a Gray code for F n (p) which can be implemented in a recursive generating algorithm, and finally in a loopless generating algorithm.
An algorithm for the solution of tree equations
1997
We consider the problem of solving equations over k-ary trees. Here an equation is a pair of labeled α-ary trees, where α is a function associating an arity to each label. A solution to an equation is a morphism from α-ary trees to k-ary trees that maps the left and right hand side of the equation to the same k-ary tree.
Hyperidentities of some generalizations of lattices
1998
In the paper we present bases and hyperbases of hyperidentities of some generalizations of the variety L of all lattices and the variety D of distributive lattices. We describe the form of hyperidentities of some varieties with two binary operations.