Expressive power of linear algebra query languages
Loading...
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Los algoritmos del álgebra lineal a menudo requieren algún tipo de iteración o recursión, como lo ilustran los algoritmos estándar para la eliminación gaussiana, la inversión de matrices y la clausura transitiva. Una característica clave compartida por estos
algoritmos es que permiten que se repitan varios pasos, pero limitados por la dimensión
de la matriz. En esta tesis, ampliamos el lenguaje de consulta para matrices MATLANG
con este tipo de recursión, y evidenciamos que esto es suficiente para expresar algoritmos
clásicos del álgebra lineal. Estudiamos el poder expresivo de este lenguaje y demostramos
que corresponde naturalmente a las familias de circuitos aritméticos, que a menudo se
dice que capturan el álgebra lineal. Además, analizamos varios sub-fragmentos de nuestro
lenguaje, y se demuestra que su poder expresivo está estrechamente relacionado con
formalismos lógicos en las relaciones anotadas en semi-anillos.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2020