- -

A split-based incremental deterministic automata minimization algorithm

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

A split-based incremental deterministic automata minimization algorithm

Mostrar el registro completo del ítem

García Gómez, P.; Vázquez-De-Parga Andrade, M.; Velasco, JA.; López Rodríguez, D. (2014). A split-based incremental deterministic automata minimization algorithm. Theory of Computing Systems. 1-18. doi:10.1007/s00224-014-9588-y

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/51687

Ficheros en el ítem

Thumbnail
Nombre: TOCSauthor.pdf
Tamaño: 208.9Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir/Preview
[Cerrado]
Nombre: García;Vázquez-de ...
Tamaño: 2.183Mb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor

Metadatos del ítem

Título: A split-based incremental deterministic automata minimization algorithm
Autor: García Gómez, Pedro Vázquez-De-Parga Andrade, Manuel Velasco, Jairo A. López Rodríguez, Damián
Entidad UPV: Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació
Fecha difusión:
Resumen:
We here study previous results due to Hopcroft and Almeida et al. to propose an incremental split-based deterministic automata minimization algorithm whose average running-time does not depend on the size of the alphabet. ...[+]
Palabras clave: Autómata finito , Minimización de DFAs , Minimización incremental , Finite automata , DFA minimization , Incremental minimization
Derechos de uso: Reserva de todos los derechos
Fuente:
Theory of Computing Systems. (issn: 1432-4350 )
DOI: 10.1007/s00224-014-9588-y
Editorial:
Springer
Versión del editor: http://link.springer.com/article/10.1007/s00224-014-9588-y
Descripción: The final publication is available at Springer via http://dx.doi.org/10.1007/s00224-014-9588-y. La fecha de publicación corresponde a la versión First Online
Tipo: Artículo

References

Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company (1979)

Watson, B.W., Daciuk, J.: An efficient incremental DFA minimization algorithm. Nat. Lang. Eng. 9(1), 49–64 (2003)

Almeida, M., Moreira, N., Reis, R.: Incremental DFA minimisation. In: Domaratzki, M., Salomaa, K. (eds.) CIAA, of Lecture Notes in Computer Science, vol. 6482, pp 39–48. Springer (2010) [+]
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company (1979)

Watson, B.W., Daciuk, J.: An efficient incremental DFA minimization algorithm. Nat. Lang. Eng. 9(1), 49–64 (2003)

Almeida, M., Moreira, N., Reis, R.: Incremental DFA minimisation. In: Domaratzki, M., Salomaa, K. (eds.) CIAA, of Lecture Notes in Computer Science, vol. 6482, pp 39–48. Springer (2010)

Hopcroft, J.E.: An n ⋅ log n $n\cdot \log n$ algorithm for minimizing states in a finite automaton. Technical report, Stanford, University, Stanford (1971)

Moore, E.F.: Gedanken experiments on sequential machines. In: Shannon, C.E., Mc-Carthy, J. (eds.) Automata Studies. Princeton Universty Press, Princeton (1956)

Berstel, J., Boasson, L., Carton, O., Fagnot, I.: Automata: from Mathematics to Applications, chapter Minimization of automata. European Mathematical Society. (arXiv: 1010.5318v3. ) To appear.

David, J.: Average complexity of Moore’s and Hopcroft’s algorithms. Theor. Comput. Sci. 417, 50–65 (2012)

Almeida, M., Moreira, N., Reis, R.: Aspects of enumeration and generation with a string automata representation. In: Leung, H., Pighizzini, G. (eds.) DCFS, pp 58–69. New Mexico State University, Las Cruces (2006)

Gries, D.: Describing an algorithm by Hopcroft. Acta Informatica 2, 97–109 (1973)

Aho, A., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company (1974)

Blum, N.: A O ( n log n ) $\mathcal {O}(n\log n)$ implementation of the standard method for minimizing n-state finite automata. Inf. Process. Lett. 57, 65–69 (1996)

Knuutila, T.: Re-describing an algorithm by Hopcroft. Theor. Comput. Sci. 250, 333–363 (2001)

Veanes, M.: Minimization of symbolic automata. Technical report, Microsoft Research, MSR-TR-2013-48 (2013)

Lothaire, M.: Applied Combinatorics on Words chap. 1. Cambridge University Press, Cambridge (2005)

[-]

recommendations

 

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro completo del ítem