Evaluación del desempeño de un autómata finito determinista bidireccional con memoria Lifo/Fifo

Abstract

En el campo de las máquinas abstractas hay una franja muy interesante que normalmente recibe poca atención, que está integrada por aquellas de capacidad inferior a la Máquina de Turing y mayor a la del Autómata Finito. Las evidencias mostraron que estas máquinas disponen de una gran potencialidad y pueden tener desempeños muy interesantes ante problemas específicos, lo que llevó a tratarlas como objetos de estudio en este trabajo. Con este fin se reconocieron y evaluaron las principales máquinas disponibles, se propuso una nueva máquina con memoria Lifo/Fifo, se seleccionó un caso de estudio y se analizaron los resultados obtenidos medianteel uso de un simulador implementado a tal fin. Las pruebas se orientaron a evaluar la complejidad temporal y la sensibilidad de este indicador ante variantes en las cadenas de datos, contrastando los resultados con los obtenidos con dos Máquinas de Turing. El trabajo ofreció la oportunidad de reconocer otras máquinas a ser estudiadas en el futuro y también confirmaron el enorme valor técnico y pedagógico de los procesos de simulación.The field of abstract machines includes a very interesting band that usually receives little attention. It is composed of machines of lower capacity than Turing Machine and greater than Finite Automaton. Evidences showed that these machines have a great potentialand have very interesting performance when solving specific problems. So, main machines available were recognized and a new machine with LIFO / FIFO memory was proposed. After that, a case study was selected and its results were analyzed with a specific simulator that had to be implemented in order to study the behavior of the new machine. The tests were oriented to the evaluation of time complexity and to study the sensitivity of this indicator to different data strings. The results were compared with those obtained with Turing machines. This work offered the opportunity to recognize other machines to be studied in the future and also confirmed the enormous technical and educational value of simulation processes.