En una entrada anterior Alejandro había anunciado un nuevo paper sobre una idea de un modelo de computación con transformaciones afines. A modo de continuación de ese artículo, este servidor en coautoría con Abuzer Yakaryilmaz, acabamos de hacer público una continuación a la idea de lo autómatas afines. Se puede descargar el manuscrito directamente desde arXiv. En este caso nos concentramos en la complejidad descripcional de dichos computadores con varios resultados interesantes.
También aprovecho esta ocasión para resaltar otra continuación más de este mismo paper, titulado "Can one quantum bit separate any pair of words with zero-error?," escrito por Belovs, Montoya y Yakaryilmaz; también puede descargarse desde arXiv. En este artículo en particular se mira un problema muy sencillo de explicar pero bastante complejo de resolver, el de separar palabras. Por ejemplo, si te doy x e y, ¿cuál él es el autómata de tamaño mínimo que acepta x y rechaza y?
Entonces, por lo que va de año ya son 3 los artículos sobre autómatas afines. ¿Será el inicio de una línea de invetigación? Solo el tiempo lo dirá. Por ahora, el modelo es muy interesante y prometedor ya que simplifica muchos argumentos en la teoría de autómatas cuánticos.
0 comments:
Publicar un comentario