ON THE AVERAGE SIZE OF GLUSHKOV AND PARTIAL DERIVATIVE AUTOMATA

• Tipo: Artigo em Revista Científica Internacional
• Data: 2012

Autores

Sabine Broda (Autor) FCUP; Antonio Machiavelo (Autor) FCUP; Nelma Moreira (Autor) FCUP; Rogerio Reis (Autor) FCUP

Revista

Título: International Journal of Foundations of Computer Science

Vol. 23

Páginas: 969-984

ISSN: 0129-0541

Editora: World Scientific

Indexação

ISI Web of Knowledge - 14 Citações

Scopus - 20 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Projetos Associados

CANTE - CANTE: Complexidade descriptiva e computacional de linguagens formais

Outras Informações

ID Authenticus: P-002-74A

DOI: 10.1142/s0129054112400400

Abstract (EN): In this paper, the relation between the Glushkov automaton (A(pos)) and the partial derivative automaton (A(pd)) of a given regular expression, in terms of transition complexity, is studied. The average transition complexity of A(pos) was proved by Nicaud to be linear in the size of the corresponding expression. This result was obtained using an upper bound of the number of transitions of A(pos). Here we present a new quadratic construction of A(pos) that leads to a more elegant and straightforward implementation, and that allows the exact counting of the number of transitions. Based on that, a better estimation of the average size is presented. Asymptotically, and as the alphabet size grows, the number of transitions per state is on average 2. Broda et al. computed an upper bound for the ratio of the number of states of A(pd) to the number of states of A(pos), which is about 1/2 for large alphabet sizes. Here we show how to obtain an upper bound for the number of transitions in A(pd), which we then use to get an average case approximation. In conclusion, assymptotically, and for large alphabets, the size of Apd is half the size of the . This is corroborated by some experiments, even for small alphabets and small regular expressions.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 16