Prism complexity of matrices

Abstract. Let \(d, \ m\), and \(q\) be positive integers and \(A(q) = \{ 0, \ldots, q - 1 \}\) be an alphabet. We investigate a generalization of the well-known subword complexity of \(d\)-dimensional matrices containing the elements of \(A(q)\). Let \(\mathcal{L} = (\textbf{L}_1, \ldots, \textbf{L}_m)\) be a list of distinct \(d\)-dimensional vectors, where \(\textbf{L}_i = (a_{i1}, \ldots, a_{id})\). The prism complexity of a \(d\)-dimensional \(q\)-ary matrix \(\mathcal{M}\) is denoted by \(C(d,q,\mathcal{L},\mathcal{M})\) and is defined as the number of distinct \(d\)-dimensional \(q\)-ary submatrices, whose permitted sizes are listed in \(\mathcal{L}\). We review and extend the earlier results, first of all results concerning maximum complexity of matrices and performance parameters of the construction algorithms.