ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS

Laura Giambruno, Maxime Crochemore, Alessio Langiu, Alessio Langiu

Risultato della ricerca: Article

Abstract

In 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.
Lingua originaleEnglish
pagine (da-a)281-301
Numero di pagine21
RivistaInternational Journal of Foundations of Computer Science
VolumeVolume 23, Issue 2 (2012)
Stato di pubblicazionePublished - 2012

Fingerprint

Glossaries

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)

Cita questo

Giambruno, L., Crochemore, M., Langiu, A., & 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), 281-301.

ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS. / Giambruno, Laura; Crochemore, Maxime; Langiu, Alessio; Langiu, Alessio.

In: International Journal of Foundations of Computer Science, Vol. Volume 23, Issue 2 (2012), 2012, pag. 281-301.

Risultato della ricerca: Article

Giambruno, L, Crochemore, M, Langiu, A & Langiu, A 2012, 'ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS', International Journal of Foundations of Computer Science, vol. Volume 23, Issue 2 (2012), pagg. 281-301.
Giambruno, Laura ; Crochemore, Maxime ; Langiu, Alessio ; Langiu, Alessio. / ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS. In: International Journal of Foundations of Computer Science. 2012 ; Vol. Volume 23, Issue 2 (2012). pagg. 281-301.
@article{4d92dc916c314ceca04a3815b844158b,
title = "ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS",
abstract = "In 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.",
keywords = "Finite set of words, deterministic automata, minimal automata, online construction.",
author = "Laura Giambruno and Maxime Crochemore and Alessio Langiu and Alessio Langiu",
year = "2012",
language = "English",
volume = "Volume 23, Issue 2 (2012)",
pages = "281--301",
journal = "International Journal of Foundations of Computer Science",
issn = "0129-0541",
publisher = "World Scientific Publishing Co. Pte Ltd",

}

TY - JOUR

T1 - ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS

AU - Giambruno, Laura

AU - Crochemore, Maxime

AU - Langiu, Alessio

AU - Langiu, Alessio

PY - 2012

Y1 - 2012

N2 - In 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.

AB - In 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.

KW - Finite set of words

KW - deterministic automata

KW - minimal automata

KW - online construction.

UR - http://hdl.handle.net/10447/62771

UR - http://dx.doi.org/10.1142/S0129054112400138

M3 - Article

VL - Volume 23, Issue 2 (2012)

SP - 281

EP - 301

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

ER -