Technical Report: DCC-2014-02

On the Bisilimarity of the Position Automata

Eva Maia, Nelma Moreira, Rogério Reis

DCC \& CMUP, Faculdade de Ciências 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
January 2014

Abstract

Minimization of nondeterministic finite automata (NFA) is a hard problem (PSPACE-complete). Bisimulations are then an attractive alternative for reducing the size of NFAs, as even bisimilarity (the largest bisimulation) is almost linear using the Paige and Tarjan algorithm. NFAs obtained from regular expressions can have the number of states linear with respect to the size of the regular expressions and conversion methods from regular expressions to equivalent NFAs can produce NFAs without or with transitions labelled with the empty word (epsilon-NFA). The standard conversion without epsilon-transitions is the position automaton, Apos. Other conversions, such as partial derivative automata (Apd) or follow automata (Afol), were proven to be quotients of the position automata (by some bisimulations). Recent experimental results suggested that for \res in (normalized) star normal form the position bisimilarity almost coincide with the Apd automaton. Our goal is to have a better characterization of Apd automata and their relation with the bisimilarity of the position automata. In this paper, we consider Apd automata for regular expressions without Kleene star and establish under which conditions they are isomorphic to the bisimilarity of Apos.