Search results for "prefix code"
showing 10 items of 13 documents
On the lattice of prefix codes
2002
AbstractThe natural correspondence between prefix codes and trees is explored, generalizing the results obtained in Giammarresi et al. (Theoret. Comput. Sci. 205 (1998) 1459) for the lattice of finite trees under division and the lattice of finite maximal prefix codes. Joins and meets of prefix codes are studied in this light in connection with such concepts as finiteness, maximality and varieties of rational languages. Decidability results are obtained for several problems involving rational prefix codes, including the solution to the primeness problem.
On the decomposition of prefix codes
2017
Abstract In this paper we focus on the decomposition of rational and maximal prefix codes. We present an effective procedure that allows us to decide whether such a code is decomposable. In this case, the procedure also produces the factors of some of its decompositions. We also give partial results on the problem of deciding whether a rational maximal prefix code decomposes over a finite prefix code.
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.
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…
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…
A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay
2012
In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers asso…
On prefix normal words and prefix normal forms
2016
A $1$-prefix normal word is a binary word with the property that no factor has more $1$s than the prefix of the same length; a $0$-prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching, where the aim is to decide whether a word has a factor with a given number of $1$s and $0$s (a given Parikh vector). Each binary word has an associated set of Parikh vectors of the factors of the word. Using prefix normal words, we provide a characterization of the equivalence class of binary words having the same set of Parikh vectors of their factors. We prove that the language of prefix normal words is not context-free and is strictly contai…
Diagonal space time hadamard codes with erasure decoding algorithm
2005
A major challenge in the area of space time (ST) codes is to find codes suitable for efficient decoding, thus overcoming the problem of many existing ST code designs which require maximum-likelihood (ML) decoding. A solution could be to apply single-input single-output (SISO) channel codes and theory over temporal channel fading to the multi-input single-output (MISO) code construction and classical suboptimum decoding methods. For these purposes, an ST code construction which allows the use of efficient decoding algorithms is described. We propose a concatenated code, where the inner code is the diagonal ST Hadamard (D-STH) code with Paley constructions and the outer code is an algebraic b…
Recent results on syntactic groups of prefix codes
2012
International audience; We give a simplified presentation of groups in transformation monoids. We use this presentation to describe two recent results on syntactic groups of prefix codes. The first one uses Sturmian words to build finite bifix codes with a given permutation group as syntactic group. The second one describes a class of prefix codes such that all their syntactic groups are cyclic.
Transducers for the bidirectional decoding of prefix codes
2010
AbstractWe construct a transducer for the bidirectional decoding of words encoded by the method introduced by Girod (1999) in [5] and we prove that it is bideterministic and that it can be used both for the left-to-right and the right-to-left decoding.We also give a similar construction for a transducer that decodes in both directions words encoded by a generalization of Girod’s encoding method. We prove that it has the same properties as those of the previous transducer. In addition we show that it has a single initial/final state and that it is minimal.