License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2019.7
URN: urn:nbn:de:0030-drops-103093
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10309/
Go to the corresponding LIPIcs Volume Portal

Geerts, Floris

On the Expressive Power of Linear Algebra on Graphs

pdf-format:
LIPIcs-ICDT-2019-7.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{geerts:LIPIcs:2019:10309,
  author =	{Floris Geerts},
  title =	{{On the Expressive Power of Linear Algebra on Graphs}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Pablo Barcelo and Marco Calautti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10309},
  doi =		{10.4230/LIPIcs.ICDT.2019.7},
  annote =	{Keywords: matrix query languages, graph queries, graph theory, logics}
}

Keywords: matrix query languages, graph queries, graph theory, logics
Collection: 22nd International Conference on Database Theory (ICDT 2019)
Issue Date: 2019
Date of publication: 19.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI