On the Expressive Power of Query Languages for Matrices

传递闭包 特征向量 计算机科学 表现力 基质(化学分析) 班级(哲学) 集合(抽象数据类型) 理论计算机科学 域代数上的 离散数学 数学 程序设计语言 纯数学 人工智能 物理 复合材料 材料科学 量子力学
作者
Robert Brijder,Floris Geerts,Jan Van den Bussche,Timmy Weerwag
出处
期刊:ACM Transactions on Database Systems [Association for Computing Machinery]
卷期号:44 (4): 1-31 被引量:13
标识
DOI:10.1145/3331445
摘要

We investigate the expressive power of MATLANG, a formal language for matrix manipulation based on common matrix operations and linear algebra. The language can be extended with the operation inv for inverting a matrix. In MATLANG + inv, we can compute the transitive closure of directed graphs, whereas we show that this is not possible without inversion. Indeed, we show that the basic language can be simulated in the relational algebra with arithmetic operations, grouping, and summation. We also consider an operation eigen for diagonalizing a matrix. It is defined such that for each eigenvalue a set of mutually orthogonal eigenvectors is returned that span the eigenspace of that eigenvalue. We show that inv can be expressed in MATLANG + eigen. We put forward the open question whether there are Boolean queries about matrices, or generic queries about graphs, expressible in MATLANG + eigen but not in MATLANG + inv. Finally, the evaluation problem for MATLANG + eigen is shown to be complete for the complexity class ∃ R.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
阿王不理你完成签到,获得积分10
1秒前
廾匸完成签到,获得积分10
1秒前
lin发布了新的文献求助10
2秒前
wujun完成签到,获得积分10
4秒前
6秒前
7秒前
秃然完成签到,获得积分10
7秒前
wjw完成签到,获得积分10
8秒前
8秒前
CipherSage的应助被哇芽采纳,获得10
8秒前
崔正成完成签到,获得积分10
8秒前
在水一方的应助被坚强孤容采纳,获得10
9秒前
9秒前
bobopoi完成签到,获得积分10
9秒前
pear完成签到,获得积分10
9秒前
10秒前
凡凡完成签到,获得积分10
11秒前
Julian的应助被zzZZZ采纳,获得30
11秒前
一休完成签到 ,获得积分10
11秒前
mooncake187发布了新的文献求助10
12秒前
查找关注了科研通微信公众号
12秒前
李楠楠发布了新的文献求助10
12秒前
飘逸的又夏完成签到 ,获得积分10
13秒前
这就是你的回答吗完成签到 ,获得积分10
13秒前
13秒前
13秒前
14秒前
圥忈完成签到,获得积分10
14秒前
霡霂发布了新的文献求助10
14秒前
bobopoi发布了新的文献求助10
16秒前
胡图图发布了新的文献求助10
17秒前
小情绪发布了新的文献求助10
18秒前
西瓜翠衣完成签到,获得积分10
18秒前
18秒前
xing_xing的应助被一一采纳,获得20
19秒前
19秒前
fff发布了新的文献求助10
19秒前
20秒前
杨承武发布了新的文献求助10
20秒前
宇智波小小怪完成签到,获得积分10
20秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
八旗制度の研究 600
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8186750
求助须知:如何正确求助?哪些是违规求助? 9575027
关于积分的说明 21839240
捐赠科研通 7784331
什么是DOI,文献DOI怎么找? 3434808
关于科研通互助平台的介绍 2559206
邀请新用户注册赠送积分活动 2481611