On the average state complexity of partial derivative automata

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

Autores

Sabine Broda (Autor) FCUP; António Machiavelo (Autor) FCUP; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Revista

Título: International Journal of Foundations of Computer Science

Vol. 22 Nº 7

Páginas: 1593-1606

ISSN: 0129-0541

Editora: World Scientific

Classificação Científica

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

CORDIS: Ciências Físicas > Ciência de computadores

Outras Informações

Abstract (EN): The partial derivative automaton Apd is usually smaller than other nondeterministic finite automata constructed from a regular expression, and it can be seen as a quotient of the Glushkov automaton (Apos). By estimating the number of regular expressions that have epsilon as a partial derivative, we compute a lower bound of the average number of mergings of states in Apos and describe its asymptotic behaviour. This depends on the alphabet size, k, and for growing k's its limit approaches half the number of states in Apos. The lower bound corresponds to consider the Apd automaton for the marked version of the re, i.e. where all its letters are made different. Experimental results suggest that the average number of states of this automaton, and of the APd automaton for the unmarked re, are very close to each other.

Idioma: Inglês

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

Notas: Accepted to publication. - ISSN: 0129-0541, Online ISSN: 1793-6373