Search results for "code"

showing 10 items of 1180 documents

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…

Discrete mathematicsCode (set theory)Mathematics::CombinatoricsValue (computer science)020206 networking & telecommunications0102 computer and information sciences02 engineering and technologyMathematical proof01 natural sciencesPermutation codeTheoretical Computer ScienceCombinatoricsPermutation010201 computation theory & mathematicsLehmer codeStatistics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]FOS: Mathematics0202 electrical engineering electronic engineering information engineeringMathematics - CombinatoricsDiscrete Mathematics and CombinatoricsCombinatorics (math.CO)Bijection injection and surjectionComputingMilieux_MISCELLANEOUSMathematics
researchProduct

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.

Discrete mathematicsCode (set theory)v-variable fractalsApplied MathematicsGeneral MathematicsProbability (math.PR)ta111Dynamical Systems (math.DS)self-similar setsTree (descriptive set theory)Box countingFractalIterated function systemMathematics - Classical Analysis and ODEsHausdorff dimensionClassical Analysis and ODEs (math.CA)FOS: MathematicsAffine transformationMathematics - Dynamical Systems28A80 60D05 37H99RandomnessMathematics - ProbabilityMathematics
researchProduct

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/.

Discrete mathematicsCombinatoricsCode (set theory)Minimum distanceWeight distributionSense (electronics)Linear codeMathematics1998 Information Theory Workshop (Cat. No.98EX131)
researchProduct

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.

Discrete mathematicsCombinatoricsGray codeComputational Theory and MathematicsDiscrete Mathematics and CombinatoricsMajor indexAlgorithmTheoretical Computer ScienceMathematicsJournal of Discrete Algorithms
researchProduct

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.

Discrete mathematicsComputer Networks and CommunicationsApplied MathematicsComputer Science::Neural and Evolutionary ComputationHamming distanceComputer Science::Computational ComplexityTravelling salesman problemCombinatoricsHigh Energy Physics::TheoryComputational MathematicsCompleteness (order theory)Computer Science::Data Structures and AlgorithmsNP-completeBottleneck traveling salesman problemHamming codeSoftwareComputer Science::Information TheoryMathematicsBIT
researchProduct

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…

Discrete mathematicsDividesMorse codelaw.inventionCombinatoricsMorse signed dividesInvertible matrixlawBraidImmersion (mathematics)Strongly invertible linksGeometry and TopologyInvariant (mathematics)Finite setMathematicsTopology
researchProduct

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…

Discrete mathematicsExistential quantificationLyndon word Universal cycle Universal Lyndon wordComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Lyndon word Universal cycle Universal Lyndon word Lex-codeLexicographical orderLyndon wordUniversal Lyndon wordLyndon wordsPrefixCombinatoricsMathematics::Group TheoryCombinatorics on wordsComputer Science::Discrete MathematicsUniversal cycleBijectionAlphabetMathematics::Representation TheoryComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

Minimal Morse flows on compact manifolds

2006

Abstract In this paper we prove, using the Poincare–Hopf inequalities, that a minimal number of non-degenerate singularities can be computed in terms only of abstract homological boundary information. Furthermore, this minimal number can be realized on some manifold with non-empty boundary satisfying the abstract homological boundary information. In fact, we present all possible indices and types (connecting or disconnecting) of singularities realizing this minimal number. The Euler characteristics of all manifolds realizing this minimal number are obtained and the associated Lyapunov graphs of Morse type are described and shown to have the lowest topological complexity.

Discrete mathematicsLyapunov functionTopological complexityBoundary (topology)Type (model theory)Morse codeManifoldLyapunov graphslaw.inventionsymbols.namesakePoincaré–Hopf inequalitieslawEuler's formulasymbolsGravitational singularityGeometry and TopologyMathematics::Symplectic GeometryConley indexMathematicsTopology and its Applications
researchProduct

A-Codes from Rational Functions over Galois Rings

2006

In this paper, we describe authentication codes via (generalized) Gray images of suitable codes over Galois rings. Exponential sums over these rings help determine--or bound--the parameters of such codes.

Discrete mathematicsMathematics::Commutative AlgebraApplied MathematicsFundamental theorem of Galois theoryGalois groupRational functionExponential polynomialComputer Science ApplicationsEmbedding problemDifferential Galois theorysymbols.namesakeGalois rings Gray map codesComputer Science::Computer Vision and Pattern RecognitionComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATIONComputer Science::MultimediasymbolsSettore MAT/03 - GeometriaGalois extensionResolventMathematicsDesigns, Codes and Cryptography
researchProduct

Periodicity vectors for labelled trees

2003

AbstractThe concept of a periodicity vector is introduced in the context of labelled trees, and some new periodicity theorems are obtained. These results constitute generalizations of the classical periodicity theorem of Fine and Wilf for words. The concept of a tree congruence is also generalized and the isomorphism between the lattice of tree congruences and the lattice of unlabelled trees (prefix codes) is established.

Discrete mathematicsMonoidPrefix codePeriodicityApplied MathematicsContext (language use)Congruence relationTree (graph theory)CombinatoricsFormal languagesLattice (music)Labelled treeCongruence (manifolds)Periodicity vectorDiscrete Mathematics and CombinatoricsIsomorphismMathematicsDiscrete Applied Mathematics
researchProduct