Observatorio de I+D+i UPM

Memorias de investigación
Ponencias en congresos:
Hopcroft’s Minimization Technique: Queues or Stacks?
Año:2008
Áreas de investigación
  • Inteligencia artificial
Datos
Descripción
Abstract. We consider the absolute worst case time complexity for Hopcroft’s minimization algorithm applied to unary languages (or a modification of this algorithm for cover automata minimization). We show that in this setting the worst case is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. We refine a previous result by showing that the Berstel/Carton example reported before 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 when considering the setting 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 is desirable for the case of unary languages in the setting of deterministic finite automata.
Internacional
Si
Nombre congreso
13th international conference on Implementation and Applications of Automata
Tipo de participación
960
Lugar del congreso
San Francisco
Revisores
Si
ISBN o ISSN
978-3-540-70843-8
DOI
10.1007/978-3-540-70844-5
Fecha inicio congreso
21/07/2008
Fecha fin congreso
24/07/2008
Desde la página
78
Hasta la página
91
Título de las actas
Hopcroft’s Minimization Technique: Queues or Stacks?
Esta actividad pertenece a memorias de investigación
Participantes
  • Participante: Mihaela Păun (Louisiana Tech University)
  • 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)