logo móvil
Contáctanos

Eficiente construcción del autómata de ecuaciones

Autores: Ouardi, Faissal; Lotfi, Zineb; Elghadyry, Bilal

Idioma: Inglés

Editor: MDPI

Año: 2021

Descargar PDF

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


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).

Otros recursos que podrían interesarte

Temas Virtualpro