On the Average Number of States of Partial Derivative Automata

• Type: Article in International Conference Proceedings Book
• Date: 2010

Authors

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

Conference proceedings International

Title: DEVELOPMENTS IN LANGUAGE THEORY

Pages: 112-123

14th International Conference on Developments in Language Theory

London, CANADA, AUG 17-20, 2010

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 3 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-003-AK6

DOI: 10.1007/978-3-642-14455-4_12

Abstract (EN): The partial derivative automaton (A(pd)) is usually smaller than other non-deterministic 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 epsilon 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 its limit, as k goes to infinity, is 1/2. The lower bound corresponds exactly 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: 12