Structure and properties of strong prefix codes of pictures. (28th May 2015)

• Record Type: Journal Article
• Authors: ANSELMO, MARCELLA; GIAMMARRESI, DORA; MADONIA, MARIA
• Is Part Of: Mathematical structures in computer science. Volume 27:Number 2(2017)
• Page Start: 123
• Page End: 142
• Publication Date: 2015-05-28
• Subjects: Computer science -- Mathematics -- Periodicals; 004.015105
• DOI: 10.1017/S0960129515000043
• Languages: English
• ISSNs: 0960-1295

Abstract

Abstract : A set X ⊆ Σ** of pictures is a code if every picture over Σ is tilable in at most one way with pictures in X . The definition of strong prefix code is introduced. The family of finite strong prefix codes is decidable and it has a polynomial time decoding algorithm. Maximality for finite strong prefix codes is also studied and related to the notion of completeness. We prove that any finite strong prefix code can be embedded in a unique maximal strong prefix code that has minimal size and cardinality. A complete characterization of the structure of maximal finite strong prefix codes completes the paper.