El paper que escribimos con Abuzer Yakaryılmaz (el cual comenté aquí), fue aceptado en el CSR 2016 (The 11th International Computer Science Symposium in Russia).
Pueden bajar un preprint de arXiv. La versión publicada es un poco más corta por límites de espacio, y está aquí: LNCS 9691:146-160.
Lo que hacemos en este trabajo es definir los autómatas afines. La idea surgió de un comentario que hice en una charla que dio Abuzer en mi grupo acerca de los autómatas cuánticos. La ganancia computacional que tenían estos autómatas parecía venir exclusivamente de las amplitudes negativas, entonces surgió la pregunta de si podríamos tener el mismo poder computacional simplemente usando un autómata probabilista con "probabilidades" negativas. Y así llegamos a las transformaciones afines: la idea es que un estado está representado por un vector cuyas componentes suman uno, sólo que no pedimos que sean positivas (como en un autómata probabilista). Luego usamos transformaciones afines (que mantienen la suma a uno) como matriz de transición. El resultado fue sorprendente ya que en el caso determinista, resultó ser más poderoso que los autómatas finitos cuánticos (y en el caso no determinista, igual).
Dejaré los slides una vez lo prepare para el simposio (que es en San Petersburgo del 9 al 13 de junio). Update: Aquí están.
Cabe aclarar que Abuzer es el especialista en autómatas (igual que Marcos Villagra, co-autor de este blog), mi campo principal es el cálculo lambda y la teoría de tipos... pero estuvo buena esta colaboración y espero ir aprendiendo más del tema.
0 comments:
Publicar un comentario