ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH

• Type: Article in International Scientific Journal
• Date: 2011

Authors

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

Journal

Title: International Journal of Foundations of Computer Science

Vol. 22 No. 7

Pages: 1593-1606

ISSN: 0129-0541

Publisher: World Scientific

Indexing

ISI Web of Knowledge - 17 Citations

Scopus - 21 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Associated Projects

CANTE - CANTE: Complexidade descriptiva e computacional de linguagens formais

Other information

Authenticus ID: P-002-JXT

DOI: 10.1142/s0129054111008908

Abstract (EN): The partial derivative automaton (A(pd)) 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 (A(pos)). By estimating the number of regular expressions that have E as a partial derivative, we compute a lower bound of the average number of mergings of states in A(pos) 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 A(pos). The lower bound corresponds to consider the A(pd) automaton for the marked version of the regular expression, i.e. where all its letters are made different. Experimental results suggest that the average number of states of this automaton, and of the A(pd) automaton for the unmarked regular expression, are very close to each other.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14