Two-Dimensional Palindromes and Their Properties

详细信息    查看全文

• 关键词：Combinatorics on words ; Two ; Dimensional words ; Two ; Dimensional palindromes ; Recognizable languages ; Primitivity ; Symmetry
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10168
• 期：1
• 页码：155-167
• 丛书名：Language and Automata Theory and Applications
• ISBN：978-3-319-53733-7
• 卷排序：10168

文摘

A two-dimensional word (2D) is a rectangular finite array of letters from the alphabet \(\varSigma \). A 2D word is said to be a 2D palindrome if it is equal to its reverse image. In this paper, we study some combinatorial properties of 2D palindromes. In particular, we provide a sufficient condition under which a 2D word is said to be a 2D palindrome, discuss the necessary and sufficient condition under which a 2D word can be decomposed into 2D palindromes, and find the relation between the set of all 2D palindromes and the set of all 2D primitive words. We also show that the set of all 2D palindromes is not a recognizable language, and study a special class of 2D palindromes, namely 2D palindrome square words.