Scholarlink

Let \(d \in \{0, 1, 2, 3, 4\}\) and W be a 2-dimensional word of dimensions \(h \times w\) on the binary alphabet \(\{\square,\blacksquare \}\) , where \(h,w \in \mathbb {Z}_{>0}\) . Assume that each occurrence of the letter \(\blacksquare \) in W is adjacent to at most d letters \(\blacksquare \) and let \(|W|_{\blacksquare}\) be the number of letters \(\blacksquare \) in W. We provide an exact formula for the maximum value of \(|W|_{\blacksquare}\) for fixed (h, w). As a byproduct, we deduce an upper bound on the length of maximum snake polyominoes contained in a \(h \times w\) rectangle.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Maximal 2-Dimensional Binary Words of Bounded Degree

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Alexandre Blondin Massé,
  • Alain Goupil,
  • Raphael L’ Heureux,
  • Louis Marin

摘要

Let \(d \in \{0, 1, 2, 3, 4\}\) and W be a 2-dimensional word of dimensions \(h \times w\) on the binary alphabet \(\{\square,\blacksquare \}\) , where \(h,w \in \mathbb {Z}_{>0}\) . Assume that each occurrence of the letter \(\blacksquare \) in W is adjacent to at most d letters \(\blacksquare \) and let \(|W|_{\blacksquare}\) be the number of letters \(\blacksquare \) in W. We provide an exact formula for the maximum value of \(|W|_{\blacksquare}\) for fixed (h, w). As a byproduct, we deduce an upper bound on the length of maximum snake polyominoes contained in a \(h \times w\) rectangle.