6533b830fe1ef96bd12966ce
RESEARCH PRODUCT
On the lattice of prefix codes
Antonio RestivoPedro V. Silvasubject
Block codeDiscrete mathematicsPrefix codeGeneral Computer ScienceRational languagesJoinsKraft's inequalityDecidabilityTheoretical Computer SciencePrefixCombinatoricsLattice (order)Computer Science::Formal Languages and Automata TheoryMathematicsComputer Science(all)description
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2002-10-01 | Theoretical Computer Science |