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.2020.12
URN: urn:nbn:de:0030-drops-119361
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11936/
Go to the corresponding LIPIcs Volume Portal

Geerts, Floris

When Can Matrix Query Languages Discern Matrices?

pdf-format:
LIPIcs-ICDT-2020-12.pdf (0.6 MB)

Abstract

We investigate when two graphs, represented by their adjacency matrices, can be distinguished by means of sentences formed in MATLANG, a matrix query language which supports a number of elementary linear algebra operators. When undirected graphs are concerned, and hence the adjacency matrices are real and symmetric, precise characterisations are in place when two graphs (i.e., their adjacency matrices) can be distinguished. Turning to directed graphs, one has to deal with asymmetric adjacency matrices. This complicates matters. Indeed, it requires to understand the more general problem of when two arbitrary matrices can be distinguished in MATLANG. We provide characterisations of the distinguishing power of MATLANG on real and complex matrices, and on adjacency matrices of directed graphs in particular. The proof techniques are a combination of insights from the symmetric matrix case and results from linear algebra and linear control theory.

BibTeX - Entry

@InProceedings{geerts:LIPIcs:2020:11936,
  author =	{Floris Geerts},
  title =	{{When Can Matrix Query Languages Discern Matrices?}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Carsten Lutz and Jean Christoph Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11936},
  URN =		{urn:nbn:de:0030-drops-119361},
  doi =		{10.4230/LIPIcs.ICDT.2020.12},
  annote =	{Keywords: matrix query languages, linear algebra, expressive power}
}

Keywords: matrix query languages, linear algebra, expressive power
Collection: 23rd International Conference on Database Theory (ICDT 2020)
Issue Date: 2020
Date of publication: 11.03.2020
Supplementary Material: Video of the Presentation: https://doi.org/10.5446/46824

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