Search results for "COD"
showing 10 items of 2985 documents
Coding Binary Trees by Words over an Alphabet with Four Letters
1992
Abstract We propose a new encoding scheme to represent binary trees with n leaves by words of length n over an alphabet with four letters. We give a characterization of these codewords.
Varieties of Codes and Kraft Inequality
2005
Decipherability conditions for codes are investigated by using the approach of Guzman, who introduced in [7] the notion of variety of codes and established a connection between classes of codes and varieties of monoids. The class of Uniquely Decipherable (UD) codes is a special case of variety of codes, corresponding to the variety of all monoids. It is well known that the Kraft inequality is a necessary condition for UD codes, but it is not sufficient, in the sense that there exist codes that are not UD and that satisfy the Kraft inequality. The main result of the present paper states that, given a variety $\mathcal{V}$ of codes, if all the elements of $\mathcal{V}$ satisfy the Kraft inequ…
Lehmer code transforms and Mahonian statistics on permutations
2012
Abstract In 2000 Babson and Steingrimsson introduced the notion of vincular patterns in permutations. They show that essentially all well-known Mahonian permutation statistics can be written as combinations of such patterns. Also, they proved and conjectured that other combinations of vincular patterns are still Mahonian. These conjectures were proved later: by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006. In this paper we give an alternative proof of some of these results. Our approach is based on permutation codes which, like the Lehmer code, map bijectively permutations onto subexcedant sequences. More precisely, we give several code transforms (i.e., bijections…
Dimensions of random affine code tree fractals
2014
We calculate the almost sure Hausdorff dimension for a general class of random affine planar code tree fractals. The set of probability measures describing the randomness includes natural measures in random $V$-variable and homogeneous Markov constructions.
MMD codes in a more general sense
2002
Summary form only given. The author deals with the characterisation of maximum minimum distance (MMD) codes in a more general sense, which has been completed in a joint work with Olsson. As in the m=1 case the weight distribution of an MMD code /spl Cscr/ is uniquely determined by its parameters [n,k,d]/sub q/.
An efficient Gray code algorithm for generating all permutations with a given major index
2014
Abstract In Effler and Ruskey (2003) [1] the authors give an algorithm, which appears to be CAT, for generating permutations with a given major index. In the present paper we give a new algorithm for generating a Gray code for subexcedant sequences. We show that this algorithm is CAT and modify it into a CAT generating algorithm for a Gray code for permutations with a given major index.
Codimension growth of two-dimensional non-associative algebras
2007
Let F be a field of characteristic zero and let A be a two-dimensional non-associative algebra over F. We prove that the sequence c n (A), n =1,2,..., of codimensions of A is either bounded by n + 1 or grows exponentially as 2 n . We also construct a family of two-dimensional algebras indexed by rational numbers with distinct T-ideals of polynomial identities and whose codimension sequence is n + 1, n > 2.
NP-completeness of the hamming salesman problem
1985
It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.
Strongly invertible links and divides
2008
Abstract To a proper generic immersion of a finite number of copies of the unit interval in a 2-disc, called a divide, A’Campo associates a link in S 3 . From the more general notion of ordered Morse signed divides, one obtains a braid presentation of links of divides. In this paper, we prove that every strongly invertible link is isotopic to the link of an ordered Morse signed divide. We give fundamental moves for ordered Morse signed divides and show that strongly invertible links are equivalent if and only if we can pass from one ordered Morse signed divide to the other by a sequence of such moves. Then we associate a polynomial to an ordered Morse signed divide, invariant for these move…
Universal Lyndon Words
2014
A word w over an alphabet Σ is a Lyndon word if there exists an order defined on Σ for which w is lexicographically smaller than all of its conjugates (other than itself). We introduce and study universal Lyndon words, which are words over an n-letter alphabet that have length n! and such that all the conjugates are Lyndon words. We show that universal Lyndon words exist for every n and exhibit combinatorial and structural properties of these words. We then define particular prefix codes, which we call Hamiltonian lex-codes, and show that every Hamiltonian lex-code is in bijection with the set of the shortest unrepeated prefixes of the conjugates of a universal Lyndon word. This allows us t…