2026-07-25T01:46:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24121 2025-11-12T13:33:18Z ddc:004 open_access

Register Automata with Permutations Balachander, Mrudula Filiot, Emmanuel Gentilini, Raffaella Tzevelekos, Nikos Register automata data words equivalence minimization active learning 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 (the complexity of graph isomorphism) and NP. We then introduce a subclass of pDRAs, called register automata 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 register automaton 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, and so this yields a polynomial time minimization algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mrudula Balachander and Emmanuel Filiot and Raffaella Gentilini and Nikos Tzevelekos 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.14 urn:nbn:de:0030-drops-241219 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.14 eng https://creativecommons.org/licenses/by/4.0/legalcode