A Gray code for cross-bifix-free sets. (11th May 2015)

• Record Type: Journal Article
• Authors: BERNINI, ANTONIO; BILOTTA, STEFANO; PINZANI, RENZO; VAJNOVSZKI, VINCENT
• Is Part Of: Mathematical structures in computer science. Volume 27:Number 2(2017)
• Page Start: 184
• Page End: 196
• Publication Date: 2015-05-11
• Subjects: Computer science -- Mathematics -- Periodicals; 004.015105
• DOI: 10.1017/S0960129515000067
• Languages: English
• ISSNs: 0960-1295

Abstract

Abstract : A cross-bifix-free set of words is a set in which no prefix of any length of any word is the suffix of any other word in the set. A construction of cross-bifix-free sets has recently been proposed in Chee et al. (2013 ) within a constant factor of optimality. We propose a Gray code for these cross-bifix-free sets and a CAT algorithm generating it. Our Gray code list is trace partitioned, that is, words with zero in the same positions are consecutive in the list.