- -

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 sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: TOCSauthor.pdf
Tamaño: 208.9Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir
[Cerrado]
Nombre: García;Vázquez-de ...
Tamaño: 2.183Mb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author García Gómez, Pedro es_ES
dc.contributor.author Vázquez-De-Parga Andrade, Manuel es_ES
dc.contributor.author Velasco, Jairo A. es_ES
dc.contributor.author López Rodríguez, Damián es_ES
dc.date.accessioned 2015-06-15T09:39:46Z
dc.date.available 2015-06-15T09:39:46Z
dc.date.issued 2014-10-24
dc.identifier.issn 1432-4350
dc.identifier.uri http://hdl.handle.net/10251/51687
dc.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 es_ES
dc.description.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. The experimentation carried out shows that our proposal outperforms the algorithms studied whenever the automata have more than a (quite small) number of states and symbols. es_ES
dc.language Inglés es_ES
dc.publisher Springer es_ES
dc.relation.ispartof Theory of Computing Systems es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Autómata finito es_ES
dc.subject Minimización de DFAs es_ES
dc.subject Minimización incremental es_ES
dc.subject Finite automata es_ES
dc.subject DFA minimization es_ES
dc.subject Incremental minimization es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.title A split-based incremental deterministic automata minimization algorithm es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s00224-014-9588-y
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation 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 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion http://link.springer.com/article/10.1007/s00224-014-9588-y es_ES
dc.description.upvformatpinicio 1 es_ES
dc.description.upvformatpfin 18 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.relation.senia 277728
dc.description.references Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company (1979) es_ES
dc.description.references Watson, B.W., Daciuk, J.: An efficient incremental DFA minimization algorithm. Nat. Lang. Eng. 9(1), 49–64 (2003) es_ES
dc.description.references 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) es_ES
dc.description.references 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) es_ES
dc.description.references Moore, E.F.: Gedanken experiments on sequential machines. In: Shannon, C.E., Mc-Carthy, J. (eds.) Automata Studies. Princeton Universty Press, Princeton (1956) es_ES
dc.description.references 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. es_ES
dc.description.references David, J.: Average complexity of Moore’s and Hopcroft’s algorithms. Theor. Comput. Sci. 417, 50–65 (2012) es_ES
dc.description.references 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) es_ES
dc.description.references Gries, D.: Describing an algorithm by Hopcroft. Acta Informatica 2, 97–109 (1973) es_ES
dc.description.references Aho, A., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company (1974) es_ES
dc.description.references 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) es_ES
dc.description.references Knuutila, T.: Re-describing an algorithm by Hopcroft. Theor. Comput. Sci. 250, 333–363 (2001) es_ES
dc.description.references Veanes, M.: Minimization of symbolic automata. Technical report, Microsoft Research, MSR-TR-2013-48 (2013) es_ES
dc.description.references Lothaire, M.: Applied Combinatorics on Words chap. 1. Cambridge University Press, Cambridge (2005) es_ES


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

Mostrar el registro sencillo del ítem