Impacto de distintas formas de acceso a memoria sobre la complejidad temporal de Autómatas Finitos Bidireccionales.

Abstract

En el marco de un proyecto de investigación se puso atención a las variantes en el acceso a memoria auxiliar de los autómatas finitos bidireccionales. Así se presentó un autómata con accesos Lifo y Fifo, que mostró gran potencialidad y desempeños muy interesantes ante problemas específicos. Estimu lados por estos resultados, se estudió un nuevo autómata con acceso Lifo y dos variantes de accesos Fifo a memoria auxiliar, objeto de esta presenta ción. Las pruebas se orientaron a evaluar la complejidad temporal y la sensibilidad de este indicador ante variantes en la morfología de las cadenas de datos, contrastando los resultados con los obtenidos con una Máquinas de Turing y el autómata de memoria Lifo/Fifo ya citado. Se presen ta un caso de estudio y los resultados obtenidos