13 DEZEMBRO / QUARTA FEIRA / 10:51
FCUP PT 
 EN
 
 
APRESENTAÇÃO
PESSOAS
ENSINO
INVESTIGAÇÃO
BIBLIOTECA
NOTÍCIAS
CONTACTOS

Technical Report: DCC-2014-09

Left Relations

Eva Maia, Nelma Moreira, Rog?o Reis

DCC \& CMUP, Faculdade de Ci?ias da Universidade do Porto
R. Campo Alegre 687, 4169-007 Porto, Portugal
e-mail: emaia@dcc.fc.up.pt,nam@dcc.fc.up.pt,rvr@dcc.fc.up.pt
December 2014

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 (At). The At automaton has two quotients considered: the suffix automaton Asuf and the prefix automaton, Apre. Eliminating epsilon-transitions in At, the Glushkov automaton (Apos) is obtained. Thus, it is easy to see that Asuf and the partial derivative automaton (Apd) are the same. In this paper, we characterise the Apre automaton as a solution of a system of left RE equations and express it as a quotient of apos by a specific left-invariant equivalence relation. We define and characterise the right-partial derivative automaton (Apdr). Finally, we study the average size of all these constructions both experimentally and from an analytic combinatorics point of view.


FCUP 2017