二維有限模式（例如 QR 碼）的線性複雜度
二維模式在資訊交易中無處不在。二維碼、圖片最為常見。我想知道對於二維模式是否有類似於眾所周知的周期性序列線性複雜性概念的概念？
二維線性遞歸在代數上有點複雜。
與線性複雜度相對應的概念在某種意義上是度數 $ (n,m) $ 形式的最小度生成多項式的 $$ x^{n}y^m- \sum_{0\leq i\leq n-1} \sum_{0\leq j\leq m-1} a_{i,j} x^i y^j $$ 這將對應於二維線性遞歸 $$ s_{t+n,t’+m}=\sum_{0\leq i\leq n-1} \sum_{0\leq j\leq m-1} a_{i,j} s_{t+i,t’+j} $$ 在哪裡 $ t,t’ $ 是二維的指標。
Sakata 將 Berlekamp Massey 算法 (BMA) 推廣到 2 維，然後推廣到 N 維；見這裡（似乎是公開的）。從摘要：
我們提出了一種算法，用於找到能夠生成規定的有限二維數組的最小二維線性遞歸關係集。這是 Berlekamp-Massey 算法的二維擴展，用於合成能夠生成給定有限序列的最短線性回饋移位寄存器。大小數組的計算複雜度 $ n $ 是 $ O(n^2) $ 在一些合理的假設下。此外，我們明確了我們的算法和二元多項式理想的 Gröbner 基之間的一些關係，其中多項式與線性遞歸關係一一對應。
它們複雜的原因是（最多一些揮手）對於有限域 $ \mathbb{F} $ 一變多項式環 $ \mathbb{F}[x] $ 所有理想都是主要的（有一個多項式生成器）。因此，要使 BMA 工作，找到一個最小度數的生成器就足夠了。在多個變數中，並非所有的理想 $ \mathbb{F}[x_1,\ldots,x_n] $ 是校長。
兩個可變程度的定義和術語程度的排序是另一個問題，但這可以通過例如詞典排序來完成。