Please use this identifier to cite or link to this item:
Author(s): Sabine Broda
António Machiavelo
Nelma Moreira
Rogério Reis
Title: On the average size of pd automata: an analytic combinatorics approach
Issue Date: 2010
Abstract: The partial derivative automaton (NFA_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 (NFA_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 NFA_POS. and describe its asymptotic behaviour. This depends on the alphabet size, k, and its limit, as k goes to infinity, is 1. The lower bound corresponds exactly to consider the NFA_PD 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 NFA_PD automaton for the unmarked RE, 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
Document Type: Relatório Técnico
Rights: openAccess
Appears in Collections:FCUP - Relatório Técnico

Files in This Item:
File Description SizeFormat 
39883.pdfArtigo248.44 kBAdobe PDFThumbnail

This item is licensed under a Creative Commons License Creative Commons