Search results for "prefix code"

showing 3 items of 13 documents

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

On the size of transducers for bidirectional decoding of prefix codes

2012

In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [ IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer is minimal. Here we consider the number of states of such a transducer, related to some features of the considered prefix code X . We find some bounds of such a number of states in relation wi…

Discrete mathematicsPrefix codeBlock codeSettore INF/01 - InformaticaGeneral MathematicsConcatenated error correction codeprefix codeList decodingSerial concatenated convolutional codesSequential decodingLinear codeComputer Science ApplicationsPrefixbilateral decodingVariable length codetransducersAlgorithmComputer Science::Formal Languages and Automata TheorySoftwareMathematics
researchProduct

Loop-free Gray code algorithm for the e-restricted growth functions

2011

The subject of Gray codes algorithms for the set partitions of {1,2,...,n} had been covered in several works. The first Gray code for that set was introduced by Knuth (1975) [5], later, Ruskey presented a modified version of [email protected]?s algorithm with distance two, Ehrlich (1973) [3] introduced a loop-free algorithm for the set of partitions of {1,2,...,n}, Ruskey and Savage (1994) [9] generalized [email protected]?s results and give two Gray codes for the set of partitions of {1,2,...,n}, and recently, Mansour et al. (2008) [7] gave another Gray code and loop-free generating algorithm for that set by adopting plane tree techniques. In this paper, we introduce the set of e-restricte…

Discrete mathematicsPrefix codeGeneralizationOrder (ring theory)Computer Science ApplicationsTheoretical Computer ScienceCombinatoricsSet (abstract data type)Gray codeTree (descriptive set theory)Signal ProcessingFunction representationRepresentation (mathematics)AlgorithmInformation SystemsMathematicsInformation Processing Letters
researchProduct