论文标题
线性代数查询语言的表达力
Expressive power of linear algebra query languages
论文作者
论文摘要
线性代数算法通常需要某种迭代或递归，如标准算法所示，用于高斯消除，矩阵反转和及时闭合。这些算法共享的关键特征是，它们允许对矩阵维度界的多个步骤进行循环。在本文中，我们使用这种类型的递归扩展了矩阵查询语言matlang，并表明这足以表达经典的线性代数算法。我们研究了这种语言的表现力，并表明它自然与算术电路家族相对应，算术电路家族通常被认为捕获线性代数。此外，我们分析了我们语言的几个子片段，并表明它们的表现力与半通知关系的逻辑形式主义紧密相关。
Linear algebra algorithms often require some sort of iteration or recursion as is illustrated by standard algorithms for Gaussian elimination, matrix inversion, and transitive closure. A key characteristic shared by these algorithms is that they allow looping for a number of steps that is bounded by the matrix dimension. In this paper we extend the matrix query language MATLANG with this type of recursion, and show that this suffices to express classical linear algebra algorithms. We study the expressive power of this language and show that it naturally corresponds to arithmetic circuit families, which are often said to capture linear algebra. Furthermore, we analyze several sub-fragments of our language, and show that their expressive power is closely tied to logical formalisms on semiring-annotated relations.
