|
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.
|