Register Automata with Permutations

We propose Permutation Deterministic Register Automata (pDRAs), a deterministic register automaton model where we allow permutations of registers in transitions. The model enables minimal canonical representations and pDRAs can be tested for equivalence in polynomial time. The complexity of minimization is between GI and NP. We then introduce a subclass of pDRAs, called pDRAs with fixed permutation policy, where the register permutation discipline is stipulated globally. This class generalizes the model proposed by Benedikt, Ley and Puppis in 2010, and we show that it also admits minimal and canonical representations, based on a finite-index word equivalence relation. As an application, we show that for any regular data language L, the minimal pDRA with fixed permutation policy recognizing L can be actively learned in polynomial time using oracles for membership, equivalence and data-memorability queries. We show that all the oracles can be implemented in polynomial time, yielding a polynomial-time minimization algorithm.