Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/30024
Title: | MATLANG: Matrix operations and their expressive power | Authors: | BRIJDER, Robert GEERTS, Floris VAN DEN BUSSCHE, Jan WEERWAG, Timmy |
Issue Date: | 2019 | Publisher: | ASSOC COMPUTING MACHINERY | Source: | SIGMOD RECORD, 48(1), p. 60-67 | Abstract: | 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 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 there exists R. | Notes: | [Brijder, Robert; Van den Bussche, Jan; Weerwag, Timmy] Hasselt Univ, Hasselt, Belgium. [Geerts, Floris] Univ Antwerp, Antwerp, Belgium. | Document URI: | http://hdl.handle.net/1942/30024 | ISSN: | 0163-5808 | e-ISSN: | 1943-5835 | DOI: | 10.1145/3371316.3371331 | ISI #: | 000489342100014 | Rights: | @2018 Copyright held by the authors. Publication rights licensed to ACM. This is a minor revision of the work published in ICDT 2018 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2020 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
16_mmo-brijder.pdf Restricted Access | Published version | 920.91 kB | Adobe PDF | View/Open Request a copy |
matlang_highlight.pdf | Peer-reviewed author version | 287.67 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
1
checked on Oct 14, 2024
Page view(s)
100
checked on Sep 6, 2022
Download(s)
218
checked on Sep 6, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.