Eficiente construcción del autómata de ecuaciones
Autores: Ouardi, Faissal; Lotfi, Zineb; Elghadyry, Bilal
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Eficiente construcción del autómata de ecuaciones
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Autómata de ecuaciones
Autómata de Thompson
Complejidad temporal
Complejidad espacial
Autómatas Finitos Deterministas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 38
Citaciones: Sin citaciones
Este documento describe un algoritmo rápido para construir directamente el autómata de ecuaciones a partir del conocido autómata de Thompson asociado con una expresión regular. Allauzen y Mohri han presentado una construcción unificada de autómatas pequeños y dieron una construcción del autómata de ecuaciones con complejidad temporal y espacial en , donde denota el número de transiciones del autómata de Thompson. Se basa en dos operaciones clásicas de autómatas, a saber, la eliminación de epsilon y el algoritmo de Hopcroft para la minimización de Autómatas Finitos Deterministas (DFA). Utilizando la noción de c-continuación, Ziadi et al. presentaron una rápida computación del autómata de ecuaciones en complejidad temporal. En este documento, diseñamos un algoritmo sensible a la salida que combina las ventajas de los algoritmos anteriores y mostramos que su complejidad computacional puede reducirse a , donde denota el número de estados del autómata de ecuaciones, mediante un algoritmo de eliminación de epsilon y minimización de Bubenzer de un Autómata Finito Determinista Acíclico (ADFA).
Descripción
Este documento describe un algoritmo rápido para construir directamente el autómata de ecuaciones a partir del conocido autómata de Thompson asociado con una expresión regular. Allauzen y Mohri han presentado una construcción unificada de autómatas pequeños y dieron una construcción del autómata de ecuaciones con complejidad temporal y espacial en , donde denota el número de transiciones del autómata de Thompson. Se basa en dos operaciones clásicas de autómatas, a saber, la eliminación de epsilon y el algoritmo de Hopcroft para la minimización de Autómatas Finitos Deterministas (DFA). Utilizando la noción de c-continuación, Ziadi et al. presentaron una rápida computación del autómata de ecuaciones en complejidad temporal. En este documento, diseñamos un algoritmo sensible a la salida que combina las ventajas de los algoritmos anteriores y mostramos que su complejidad computacional puede reducirse a , donde denota el número de estados del autómata de ecuaciones, mediante un algoritmo de eliminación de epsilon y minimización de Bubenzer de un Autómata Finito Determinista Acíclico (ADFA).