- -

A split-based incremental deterministic automata minimization algorithm

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A split-based incremental deterministic automata minimization algorithm

Show full item record

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

Files in this item

Item Metadata

Title: A split-based incremental deterministic automata minimization algorithm
Author: García Gómez, Pedro Vázquez-De-Parga Andrade, Manuel Velasco, Jairo A. López Rodríguez, Damián
UPV Unit: Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació
Issued date:
Abstract:
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. ...[+]
Subjects: Autómata finito , Minimización de DFAs , Minimización incremental , Finite automata , DFA minimization , Incremental minimization
Copyrigths: Reserva de todos los derechos
Source:
Theory of Computing Systems. (issn: 1432-4350 )
DOI: 10.1007/s00224-014-9588-y
Publisher:
Springer
Publisher version: http://link.springer.com/article/10.1007/s00224-014-9588-y
Description: 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
Type: 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

 

This item appears in the following Collection(s)

Show full item record