Archivio istituzionale della ricerca dell'Università degli Studi di Palermo
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, pubblicazioni, progetti, attività) adottato dall’Università di Palermo, e ha lo scopo di raccogliere, conservare, documentare, e diffondere ad accesso aperto le informazioni relative alla produzione scientifica degli autori afferenti all’Ateneo.
EnglishIn this paper we describe a “light” algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on real dictionaries, on biological sequences and on the sets of suffixes (resp. factors) of a set of words that shows how our automaton is near to the minimal one. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton. We moreover construct linear algorithms for the insertion and deletion of a word in a finite set, directly from the constructed automaton.
| Data di pubblicazione: | 2012 |
| Titolo: | ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS |
| Autori: | |
| Citazione: | Crochemore, M., Giambruno, L., & Langiu, A. (2012). ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, Volume 23, Issue 2 (2012)(Volume 23, Issue 2 (2012)), 281-301. |
| Rivista: | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1142/S0129054112400138 |
| URL: | http://dx.doi.org/10.1142/S0129054112400138 |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Appare nelle tipologie: | 1.01 Articolo in rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| AbstractS0129054112400138.pdf | Abstract | N/A | Administrator Richiedi una copia |
http://hdl.handle.net/10447/62771
Copyright © 2020