Dublin Core
Title
Expressive power of linear algebra query languages
Subject
005.13
Ciencias de la computación
Algoritmos computacionales
Álgebras lineales
Lógica computacional
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2020
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.
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.
Creator
Muñoz Serrano, Thomas
Date
2021-01-15T11:30:46Z
2021-01-15T11:30:46Z
2020
Contributor
Riveros Jaeger, Cristian
Vrgoc, Domagoj
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
ix, 99 páginas
application/pdf
Language
en
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/51008
https://doi.org/10.7764/tesisUC/ING/51008
https://repositorio.uc.cl/handle/11534/51008