Prefix and Right-Partial Derivative Automata.

Room FC1.029, DMat-FCUP
Tuesday, 16 June, 2015 - 14:30

Recently, Yamamoto presented a new method for the conversion from regular expressions (REs) to non-deterministic finite automata (NFA) based on the Thompson $\varepsilon$-NFA ($\at$). The $\at$ automaton has two quotients  discussed: the suffix automaton $\asuf$ and the prefix automaton, $\apre$.  Eliminating $\varepsilon$-transitions in $\at$, the Glushkov automaton ($\mathcal{A}_{pos}$) 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  $\mathcal{A}_{pos}$ 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.

Speaker: 

Eva Maia (FCUP/CMUP)
Error | CMUP

Error

The website encountered an unexpected error. Please try again later.