Browsing by Author "Muñoz Serrano, Thomas"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Expressive power of linear algebra query languages
    (2020) Muñoz Serrano, Thomas; Riveros Jaeger, Cristian; Vrgoc, Domagoj; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    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.