Please use this identifier to cite or link to this item:
https://hdl.handle.net/10216/99614
Author(s): | Broda, S António Machiavelo Nelma Moreira Rogério Reis |
Title: | On the Average Number of States of Partial Derivative Automata |
Issue Date: | 2010 |
Abstract: | 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. |
Subject: | Ciência de computadores, Ciências da computação e da informação Computer science, Computer and information sciences |
Scientific areas: | Ciências exactas e naturais::Ciências da computação e da informação Natural sciences::Computer and information sciences |
URI: | https://hdl.handle.net/10216/99614 |
Source: | DEVELOPMENTS IN LANGUAGE THEORY |
Document Type: | Artigo em Livro de Atas de Conferência Internacional |
Rights: | restrictedAccess |
Appears in Collections: | FCUP - Artigo em Livro de Atas de Conferência Internacional |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
48400.pdf Restricted Access | Artigo | 174.1 kB | Adobe PDF | Request a copy from the Author(s) |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.