Please use this identifier to cite or link to this item: https://hdl.handle.net/10216/90776
Author(s): Eva Maia
Nelma Moreira
Rogerio Reis
Title: Prefix and Right-Partial Derivative Automata
Issue Date: 2015
Abstract: Recently, Yamamoto presented a new method for the conversion from regular expressions (REs) to non-deterministic finite automata (NFA) based on the Thompson epsilon-NFA (A(T)). The A(T) automaton has two quotients discussed: the suffix automaton A(suf) and the prefix automaton, A(pre). Eliminating epsilon-transitions in A(T), the Glushkov automaton (A(pos)) is obtained. Thus, it is easy to see that A(suf) and the partial derivative automaton (A(pd)) are the same. In this paper, we characterise the A(pre) automaton as a solution of a system of left RE equations and express it as a quotient of A(pos) by a specific left-invariant equivalence relation. We define and characterise the right-partial derivative automaton ((A) over left arrow (pd)). Finally, we study the average size of all these constructions both experimentally and from an analytic combinatorics point of view.
Subject: Ciências da computação e da informação
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://repositorio-aberto.up.pt/handle/10216/90776
Source: EVOLVING COMPUTABILITY
Document Type: Artigo em Livro de Atas de Conferência Internacional
Rights: openAccess
Appears in Collections:FCUP - Artigo em Livro de Atas de Conferência Internacional

Files in This Item:
File Description SizeFormat 
107486.pdf319.57 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.