论文标题
通过2D无逗号代码降低瓷砖系统中局部字母大小
Reducing the local alphabet size in tiling systems by means of 2D comma-free codes
论文作者
论文摘要
可识别的图片语言被定义为由一组由两乘两块瓷砖定义的本地图片语言的投影，即由严格的易于检验的（SLT）的语言2的命令2。可识别的图片语言的家族也定义为$ k $ k $ k $ k> 2 $，使用较大的$ k $ by $ k $ k $ k> 2 $。图片语言的描述性复杂性的基本度量是使用SLT字母的大小使用两乘两个瓷砖给出的，更准确地说是由所谓的字母比例的大小的字母比例：SLT-Alphabet / Picture-Alphabet。我们研究字母比率如何从尺寸二大的瓷砖变为较大尺寸的瓷砖如何变化，并且我们获得以下结果：在大小$ n $的字母上，任何可识别的图片语言都是SLT语言的标准，而不是$ 2N $的字母。 此外，两个是最小的字母比率。证明依赖于一个新的无逗号图片代码，为此建立了数字的下限；以及用SLT语言编码图片的语言的关系。我们的结果在二维中复制了常规单词语言的类似属性（称为扩展Medvedev的定理），涉及通过SLT单词语言的投影来定义语言所需的最小字母比率。
A recognizable picture language is defined as the projection of a local picture language defined by a set of two-by-two tiles, i.e. by a strictly-locally-testable (SLT) language of order 2. The family of recognizable picture languages is also defined, using larger $k$ by $k$ tiles, $k>2$, by the projection of the corresponding SLT language. A basic measure of the descriptive complexity of a picture language is given by the size of the SLT alphabet using two-by-two tiles, more precisely by the so-called alphabetic ratio of sizes: SLT-alphabet / picture-alphabet. We study how the alphabetic ratio changes moving from tiles of size two to tiles of larger size, and we obtain the following result: any recognizable picture language over an alphabet of size $n$ is the projection of an SLT language over an alphabet of size $2n$. Moreover, two is the minimal alphabetic ratio possible in general. The proof relies on a new family of comma-free picture codes, for which a lower bound on numerosity is established; and on the relation of languages of encoded pictures with SLT languages. Our result reproduces in two dimensions a similar property (known as Extended Medvedev's theorem) of the regular word languages, concerning the minimal alphabetic ratio needed to define a language by means of a projection of an SLT word language.
