On the lattice of prefix codes

• Type: Article in International Scientific Journal
• Date: 2002

Authors

Antonio Restivo (Author) Other; Pedro V. Silva (Author) FCUP

Journal

Title: Theoretical Computer Science

Vol. 289

Pages: 755-782

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 2 Citations

ISI Web of Science

Scopus - 3 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-000-MNN

DOI: 10.1016/s0304-3975(01)00391-7

Abstract (EN): The 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 28