Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
On the Hopcroft's minimization technique for DFA and DFCA
Año:2009
Áreas de investigación
  • Inteligencia artificial
Datos
Descripción
We show that the absolute worst case time complexity for Hopcroft¿s minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires O(nlogn) steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft¿s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu.
Internacional
Si
JCR del ISI
Si
Título de la revista
THEORETICAL COMPUTER SCIENCE
ISSN
0304-3975
Factor de impacto JCR
0,806
Información de impacto
Volumen
410
DOI
http://dx.doi.org/10.1016/j.tcs.2009.02.034
Número de revista
24
Desde la página
2424
Hasta la página
2430
Mes
MAYO
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Participante: Michaela Paun (Department of Mathematics and Statistics, Louisiana Tech University, P.O. Box 10348, Ruston, LA 71272, USA)
  • Autor: Paul Andrei Paun (UPM)
  • Autor: Alfonso Vicente Rodriguez-Paton Aradas (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Inteligencia Artificial (LIA)
  • Departamento: Inteligencia Artificial
S2i 2021 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)