文章基本信息

标题：On the Expressive Power of Linear Algebra on Graphs
本地全文：下载
作者：Floris Geerts
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：127
页码：1-19
DOI：10.4230/LIPIcs.ICDT.2019.7
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Most graph query languages are rooted in logic. By contrast, in this paper we consider graph query languages rooted in linear algebra. More specifically, we consider MATLANG, a matrix query language recently introduced, in which some basic linear algebra functionality is supported. We investigate the problem of characterising equivalence of graphs, represented by their adjacency matrices, for various fragments of MATLANG. A complete picture is painted of the impact of the linear algebra operations in MATLANG on their ability to distinguish graphs.
关键词：matrix query languages; graph queries; graph theory; logics