Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Characterization of Glushkov automata
Autore:
Caron, P; Ziadi, D;
Indirizzi:
Univ Rouen, Lab Informat Rouen, F-76821 Mt St Aignan, France Univ Rouen Mt St Aignan France F-76821 uen, F-76821 Mt St Aignan, France
Titolo Testata:
THEORETICAL COMPUTER SCIENCE
fascicolo: 1-2, volume: 233, anno: 2000,
pagine: 75 - 90
SICI:
0304-3975(20000228)233:1-2<75:COGA>2.0.ZU;2-2
Fonte:
ISI
Lingua:
ENG
Soggetto:
REGULAR EXPRESSIONS; SEMIGROUPS; ALGORITHM;
Keywords:
automata theory; Glushkov automaton; graphs theory; regular expression;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
22
Recensione:
Indirizzi per estratti:
Indirizzo: Caron, P Univ Rouen, Lab Informat Rouen, F-76821 Mt St Aignan, France UnivRouen Mt St Aignan France F-76821 821 Mt St Aignan, France
Citazione:
P. Caron e D. Ziadi, "Characterization of Glushkov automata", THEOR COMP, 233(1-2), 2000, pp. 75-90

Abstract

Glushkov's algorithm computes a nondeterministic finite automaton without epsilon-transitions and with n + 1 states from a regular expression having n occurrences of letters. The aim of this paper is to give a set of necessary and sufficient conditions characterizing this automaton. Our characterization theorem is formulated in terms of directed graphs. Moreover these conditions allow us to produce an algorithm of conversion of a Glushkov automaton into a regular expression of small size. (C) 2000 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 26/11/20 alle ore 20:13:47