Restrictions and generalizations on comma-free codes
type: Item
instance of: scholarly article
title: Restrictions and generalizations on comma-free codes
zbMATH Open document ID: 1160.94017
author: Alexander L. Churchill
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129884
full work available at URL: v16i1r25.html
review text: Summary: A significant sector of coding theory is that of comma-free coding; that is, codes which can be received without the need of a letter used for word separation. The major difficulty is in finding bounds on the maximum number of comma-free words which can inhabit a dictionary. We introduce a new class called a self-reflective comma-free dictionary and prove a series of bounds on the size of such a dictionary based upon word length and alphabet size. We also introduce other new classes such as self-swappable comma-free codes and comma-free codes in \(q\) dimensions and prove preliminary bounds for these classes. Finally, we discuss the implications and applications of combining these original concepts, including their implications for the NP-complete Post Correspondence Problem.
Mathematics Subject Classification ID: 94B50
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 5541090
MaRDI profile type: Publication
Recommended article: On the construction of comma-free codes
Recommended article: Q5678754
Recommended article: On maximal comma-free codes (Corresp.)
Recommended article: Varieties of comma-free codes
Recommended article: Combinatorial problems motivated by comma‐free codes
Recommended article: Some properties of maximal comma-free codes
Recommended article: Computer-aided constructions of commafree codes
Recommended article: The Construction of Variable-length Comma-Free Codes
Recommended article: Q4329064
Recommended article: Regent Results in Comma-Free Codes
description: scientific article; zbMATH DE number 5541090