A characterization of non-isometric binary words. (May 2019)

• Record Type: Journal Article
• Authors: Wei, Jianxin; Yang, Yujun; Zhu, Xuena
• Is Part Of: European journal of combinatorics. Volume 78(2019)
• Page Start: 121
• Page End: 133
• Publication Date: 2019-05
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2019.02.001
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: In this paper, first, we introduce two classification criteria of non-isometric words, and characterize every type of non-isometric words. Then, according to those characterizations, a family of words that 2-isometric but not 3-isometric is found, and the words with maximum and minimum index are characterized. Next, an O ( | f | 2 ) algorithm is designed, which is presented to compute the index of a non-isometric word and determine what class that a word belongs to. Finally, several problems are listed for further investigation.