Register Automata with Permutations

In this paper, we propose a new model of register automata whose equivalence problem is in PTime like the automata in [17] (called herein MRT-automata), which admits canonical and minimal representatives like Lar-automata, and which is exponentially more succinct than both models. The model, called deterministic register automata with permutations (pDRAs), is an extension of MRT-automata with the possibility of applying permutations on the registers. No duplicate values in registers nor empty registers are allowed, although some registers can be dropped (become unavailable) in some states. When reading a datum $d$ from the infinite alphabet $𝒟$, a pDRA can test whether it is already stored in some register $r$, or it is fresh (not stored in any register). In the latter case, the pDRA assigns the fresh datum $d$ to some register. In both cases, a permutation (which depends on the transition) is applied on the registers to permute their content. The content of unavailable registers is deleted.

We study language-related properties of pDRAs. After showing that pDRAs are exponentially more succinct than MRT-automata and Lar-DRAs, we look at generalizations of known results in the pDRA setting. We show that pDRAs have membership, emptiness, equivalence and data memorability problems in PTime.

We then focus on mimimization and show that pDRAs have minimal and canonical representatives. We prove that pDRAs can be minimized in exponential time. The associated decision problem is in NP and we prove that it is as hard as the graph isomorphism problem.

The barrier in efficient minimization motivates a subclass of pDRAs, that we call pDRAs with fixed register policy. In this model, permutations applied to registers only depend on the number of available registers and the register test. Therefore, any fixed register policy $\mathrm{\Pi }$ determines a class of pDRAs, which we denote $\mathrm{\Pi }$-DRAs. Additionally, in a $\mathrm{\Pi }$-DRA, registers are ordered and data are required to be stored in consecutive registers. For instance, the model of [4] coincides with Lar-DRAs, where Lar is a policy ensuring that registers are ordered by last occurrence of their contents.

As an equi-expressive particular case of pDRAs, $\mathrm{\Pi }$-DRAs inherit some of the properties of pDRAs, such as PTime equivalence (improving the exponential upper bound of [4] as a special case). Our next contribution is a Myhill-Nerode congruence for $\mathrm{\Pi }$-DRAs, which yields canonical and minimal $\mathrm{\Pi }$-DRAs for any regular data language. This generalizes the results of [4] with a different approach based on abstract residual languages. In some sense, compared to Lar-DRA, our result shows that the last appearance policy is not necessary to obtain a canonical and minimal model: fixing a register policy is actually sufficient.

We use the results gathered for $\mathrm{\Pi }$-DRAs, either directly or by inheritance from pDRAs, to set up an active learning framework for regular data languages, in the spirit of $L^{\ast }$ and $L^{\mathrm{\#}}$ algorithms for DFAs [1, 25]. We show that any regular data language $L$ can be learned in polynomial time, using polynomially many queries (in the size of the minimal $\mathrm{\Pi }$-DRA for $L$) to oracles of three types: equivalence, membership and memorability. The latter asks, given a word and a datum in that word, whether it is memorable or not. Our learning algorithm returns a minimal $\mathrm{\Pi }$-DRA for $L$, and, since the oracles can be implemented in PTime, this also yields a PTime minimization algorithm for $\mathrm{\Pi }$-DRAs, for any fixed policy $\mathrm{\Pi }$.

In summary, we start by introducing pDRAs. After establishing standard results (beginning of Section 3), we delve into distinctive features of pDRAs and their $\mathrm{\Pi }$-DRA subclass, and develop novel results and algorithms. Our strongest contributions include:

• $\mathrm{■}$

  Memorability problem in PTime (Section 3). This is important for efficient minimization and learning.

• $\mathrm{■}$

  Canonical representatives for both pDRAs (Section 4) and $\mathrm{\Pi }$-DRAs (Section 5) based on equivalence relations on data words, in the spirit of Myhill-Nerode relations. We are able to construct automata that are minimal both in the number of states and in the number of registers. The minimal pDRA for a language is unique once the order in which data that need to be memorized has been fixed (see Remark 20).

• $\mathrm{■}$

  Minimization in ExpTime and GI-hard for pDRAs (Section 4), and in PTime for pDRAs with a constant number of registers and for $\mathrm{\Pi }$-DRAs (Section 6, improving prior exponential bounds [4]).

• $\mathrm{■}$

  PTime active learning for $\mathrm{\Pi }$-DRAs (Section 6).

A succinct register automata model has been developed in [8], where succinctness is achieved by allowing registers to contain duplicate elements. As mentioned earlier, this comes at the cost of a PSpace-hard equivalence. A different approach to obtain a Myhill-Nerode characterisation of regular data languages was proposed in [6, 7], in terms of deterministic nominal automata, which are equi-expressive as deterministic register automata [5]. Nominal automata are finite-state automata recast within the universe of nominal sets [21], and where finiteness is generalized to orbit-finiteness. That approach offers neat generalizations of standard constructions and algorithms from finite-state automata to nominal automata (e.g. learning with $L^{\ast }$ [14]). On the other hand, the inner-workings of nominal automata and their algorithms are reliant on nominal-sets reasoning, such as equivalence under data-permutation, which introduces a level of indirection. Libraries dedicated to nominal-sets reasoning are available to that effect, though in terms of theoretical complexity and practical benchmarking, direct custom-made register-automata algorithms are typically faster [18, 3]. To represent nominal automata outside nominal sets, a representation scheme akin to a register discipline is essentially needed. However, as argued in [7, Sec. 6.2], extending finite automata with registers implicitly puts a linear order on the stored data, which is incompatible with minimality in the sense of Myhill-Nerode. Adding register permutations on transitions solves this problem and it turns out that minimal orbit-finite nominal automata (with straight state sets) and minimal pDRAs have same number of states (we thank the anonymous reviewer for pointing this connection out).

The problem of minimisation of systems dealing with data coming from an infinite alphabet has been studied extensively in the setting of $\pi$-calculus processes and in particular using History-Dependent Automata (HDAs) [15, 20]. Those works can be seen as precursors of the research in register automata and nominal automata. While the focus had been on mobile processes and bisimulation, rather than language acceptance, HDAs brought up central issues inherent in minimising systems with data, namely picking a canonical order of storing data and dealing with symmetries between stored data. Moreover, HDAs first featured transitions with reassignment of registers (names, in HDA terminology), of which the permutations we use in pDRAs can be seen as a special case.

The problem of learning register automata has been previously considered in [12, 11, 2]. The learner in [2] addresses Lar-DRA and works in a passive framework, i.e. without relying on the active interaction with an oracle (but only on positive and negative samples). Within active learning, the state of the art learner in [11] (improving on [12]) addresses the model in [8] and is exponential in both the number of registers and the length of the longest counterexample provided by the teacher. We already mentioned nominal $L^{\ast }$ (called $\nu L^{\ast }$) for learning nominal automata [14]. This has membership query complexity exponential in the number of states and registers (or longest counterexample, see loc. cit.). Note, however, that the learning algorithms above do not use a memorability oracle.

For $i,j\in \mathbb{N}$, we let $[i,j]$ be the set $\{k\in \mathbb{N}\mid i\le k\wedge k\le j\}$. Note that $[i,j]=\mathrm{\varnothing }$ when . We let $𝒫(X)$ be the powerset of $X$. Given a set $X$, a permutation over $X$ is a bijection from $X$ to itself ($\pi :X\stackrel{\cong }{\to }X$), whereas a partial permutation over $X$ is a bijection $\pi :X_1\to X_2$ for subsets $X_1,X_2\subseteq X$ (we write $\pi :X\stackrel{\cong }{\rightharpoonup }X$).
For any relation $R\subseteq X\times Y$, we define its domain as $\mathrm{𝖽𝗈𝗆}(R)=\{x\in X\mid \exists y:(x,y)\in R\}$ and its range as $\mathrm{𝗋𝗇𝗀}(R)=\{y\in Y\mid \exists x:(x,y)\in R\}$. Given $X^{\prime }\subseteq \mathrm{𝖽𝗈𝗆}(R)$, we may write ${R|}_{X^{\prime }}$ for the restriction $R\cap (X^{\prime }\times Y)$. For any two relations $R_1\subseteq X\times Y,R_2\subseteq Y\times Z$, we define their composition as $R_1;R_2=\{(i,j)\mid \exists k.(i,k)\in R_1\wedge (k,j)\in R_2\}$. For any $R\subseteq X\times Y$ and $i\in X,j\in Y$, we define the update $R[i\mapsto j]=\{(i,j)\}\cup R\setminus (\{i\}\times X)$.

We fix an infinite alphabet $𝒟$ of data. Data are ranged over by $d$ and variants, or by $a,b,\mathrm{\dots }$ and variants, while sometimes we may simply use numbers $1,2,3,\mathrm{\dots }$. A data word is a finite sequence $w\in {𝒟}^{\ast }$. We denote by $ϵ$ the empty word, $|w|$ the length of $w$, and $w[i]$ the $i$th datum in $w$ ($i\in [1,|w|]$). We sometimes see $w$ as a function $\widehat{w}:[1,|w|]\to 𝒟$. A data permutation is a bijection $\tau :𝒟\to 𝒟$ fixing all but finitely many elements of $𝒟$; we write $\mathrm{Perm}(𝒟)$ for the set of data permutations. Given $d,d^{\prime }\in 𝒟$, we write $(d{d}^{\prime })$ for the data permutation that swaps $d$ and $d^{\prime }$, and fixes other data.

A nominal set [21] (over $𝒟$) is a set $X$ along with a group action $\cdot :\mathrm{Perm}(𝒟)\times X\to X$, that is, for each data permutation $\tau$ and $x\in X$, we have $\tau \cdot x\in X$. We say that a set $S\subseteq 𝒟$ is a support of $x\in X$ if, for all permutations $\tau$, if $\tau (d)=d$ for all $d\in S$ then $\tau \cdot x=x$. We stipulate that all elements of a nominal set have finite support. Finite support is closed under intersection and, hence, each element $x$ of a nominal set $X$ has least finite support which we denote by $\mathrm{𝗌𝗎𝗉𝗉}(x)$. We say that $x$ is equivariant if $\mathrm{𝗌𝗎𝗉𝗉}(x)=\mathrm{\varnothing }$, i.e. $\tau \cdot x=x$ for all $\tau \in \mathrm{Perm}(𝒟)$. For a subset $Y$ of a nominal set $X$ and any $\tau$, we write $\tau \cdot Y$ for the set obtained from $Y$ by applying $\tau$ elementwise on it: $\tau \cdot Y=\{\tau \cdot x\mid x\in Y\}$.

The set ${𝒟}^{\ast }$ of data words is a nominal set, with action $\tau \cdot w=\widehat{w};\tau$. For any $w\in {𝒟}^{\ast }$, we can see that $\mathrm{𝗌𝗎𝗉𝗉}(w)=\{w[i]\mid i\in [1,|w|]\}$. Note that a set of words $L\subseteq {𝒟}^{\ast }$ has finite support just if there is finite $S\subseteq 𝒟$ such that, for all $\tau$, if $\tau (d)=d$ for all $d\in S$ then $\tau \cdot L=L$. We write $\mathrm{𝗌𝗎𝗉𝗉}(L)$ for the least finite support of $L$. $L$ is called a data language if it is equivariant, that is, if it has empty support, i.e., it is closed under data permutation. Given $u,v\in {𝒟}^{\ast }$, we write $u\simeq v$ if there exists $\tau \in \mathrm{Perm}(𝒟)$ such that $u=\tau \cdot v$.

In this paper registers are represented by natural numbers ranging over $[1,r]$ for some $r\ge 1$, and register assignments are partial injective mappings $\rho :[1,r]\rightharpoonup 𝒟$. We observe that if ${\rho }_1,{\rho }_2:[1,r]\rightharpoonup 𝒟$ are two register assignments, then ${\rho }_1;{\rho }_2^{-1}$ is a partial permutation over $[1,r]$ which identifies registers holding the same data: ${\rho }_1;{\rho }_2^{-1}=\{(i,j)\mid i\in \mathrm{𝖽𝗈𝗆}({\rho }_1)\wedge j\in \mathrm{𝖽𝗈𝗆}({\rho }_2)\wedge {\rho }_1(i)={\rho }_2(j)\}$.

For any $n\in \mathbb{N}$, we let ${𝒮}_n$ be the group of permutations on $[1,n]$. We write $\mathrm{𝗂𝖽}$ for the identity permutation on $[1,n]$. We may write permutations using sequence notation, i.e. as $(\pi (1),\mathrm{\dots },\pi (n))$, for $\pi \in {𝒮}_n$. Given a partial permutation $\tau :[1,n]\rightharpoonup [1,n]$ its canonical extension is the permutation $\widehat{\tau }\in {𝒮}_n$ obtained by setting: $\widehat{\tau }(x)=\tau (x)$ if $x\in \mathrm{𝖽𝗈𝗆}(\tau )$; and $\widehat{\tau }(x)={\tau }^{-\kappa }(x)$ if $x\in \mathrm{𝗋𝗇𝗀}(\tau )\setminus \mathrm{𝖽𝗈𝗆}(\tau )$ and $\kappa =\max \{\kappa \mid {\tau }^{-\kappa }(x)\text{ is defined}\}$ (${\tau }^{-\kappa }$ stands for the $\kappa$-fold composition ${\tau }^{-1};\mathrm{\dots };{\tau }^{-1}$); and, finally, $\widehat{\tau }(x)=x$ if $x\in [1,n]\setminus (\mathrm{𝖽𝗈𝗆}(\tau )\cup \mathrm{𝗋𝗇𝗀}(\tau ))$. Put otherwise, $\widehat{\tau }$ extends $\tau$ by closing maximal paths in $\tau$ and by being the identity everywhere else. In particular, given sequences of pairwise distinct elements $\overrightarrow{i},\overrightarrow{j}\in {[1,n]}^k$, for some $k\le n$, we write $(\overrightarrow{i}\mapsto \overrightarrow{j})$ for the canonical extension to $[1,n]$ of the map $\{(i_l,j_l)\mid l\in [1,k]\}$.

A configuration of a pDRA $𝒜$ is a pair $(p,\rho )$, where $p\in Q$ and $\rho :\mu (p)\to 𝒟$ is a register assignment, defined as a (total) mapping from $\mu (p)$ to data. We denote by ${ℂ}_{𝒜}$ the set of configurations of $𝒜$. Transitions between configurations are modeled as a labelled transition system ${\stackrel{}{\to }}_{𝒜}\subseteq {ℂ}_{𝒜}\times 𝒟\times {ℂ}_{𝒜}$, whose elements are denoted by ${\kappa }_1{\stackrel{𝑑}{\to }}_{𝒜}{\kappa }_2$, for ${\kappa }_i\in {ℂ}_{𝒜},d\in 𝒟$. We let $(p,{\rho }_1){\stackrel{𝑑}{\to }}_{𝒜}(q,{\rho }_2)$, when one of the following holds:

• $\mathrm{■}$

  ${\rho }_1(k)=d$, for some $k\in \mu (p)$, ${\delta }_{=}(p,k)=(q,\pi )$ and ${\rho }_2={({\pi }^{-1};{\rho }_1)|}_{\mu (q)}$ (Equality)

• $\mathrm{■}$

  $d\notin \mathrm{𝗋𝗇𝗀}({\rho }_1)$, ${\delta }_{\ne }(p)=(q,k,\pi )$, and ${\rho }_2={({\pi }^{-1};{\rho }_1[k\mapsto d])|}_{\mu (q)}$ (Disequality)

Note that, due to the availability condition, the assignment ${\rho }_2$ is in both cases well defined.

A run of a word $w=d_1{d}_2\mathrm{\dots }{d}_n\in {𝒟}^{\ast }$ on $𝒜$ is a sequence of transitions ${\kappa }_0{\stackrel{d_1}{\to }}_{𝒜}{\kappa }_1{\stackrel{d_2}{\to }}_{𝒜}\mathrm{\dots }{\stackrel{d_n}{\to }}_{𝒜}{\kappa }_n$ where ${\kappa }_i\in {ℂ}_{𝒜}$ and ${\kappa }_0$ is the initial configuration, defined as ${\kappa }_0=(q_0,\mathrm{\varnothing })$ where $\mathrm{\varnothing }$ is the register assignment with empty domain. The pDRA $𝒜$ is deterministic in the sense that there is at most one transition per datum $d\in 𝒟$: given a configuration $(p,{\rho }_1)$, there is at most one configuration $(q,{\rho }_2)$ such that $(p,{\rho }_1){\stackrel{𝑑}{\to }}_{𝒜}(q,{\rho }_2)$.

Additionally, we also note that the transitions preserve the “injectivity” of the register assignments. Indeed, the ${\delta }_{=}$ transitions do not change the data stored in the registers but merely rearrange the storage or delete some values. New data are stored via ${\delta }_{\ne }$ transitions, which ensures that the new datum $d$ differs from all existing stored values in registers.

If $w$ is a data word and $𝒜$ has a run on $w$ from a configuration $(q,\rho )$ to a configuration $(q^{\prime },{\rho }^{\prime })$, then we write $(q,\rho ){\stackrel{𝑤}{\to }}_{𝒜}(q^{\prime },{\rho }^{\prime })$. The language recognised by $(q,\rho )$ is defined as $ℒ(q,\rho )=\{w\in {𝒟}^{\ast }\mid (q,\rho ){\stackrel{𝑤}{\to }}_{𝒜}(q^{\prime },{\rho }^{\prime })\text{ and }{q}^{\prime }\in F\}$. Accordingly, the language recognised by $𝒜$ is defined as $ℒ(𝒜)=ℒ({\kappa }_0)$.

Note that while every data language $L$ is equivariant, $u^{-1}L$ may not necessarily be so, although $\mathrm{𝗌𝗎𝗉𝗉}(u^{-1}L)\subseteq \mathrm{𝗌𝗎𝗉𝗉}(u)$.

MRT-automata [17] are the permutation-free restriction of pDRAs, i.e. only the identity permutation is used. This restriction severely affects succinctness, as witnessed e.g. by the family of languages $L_n=\{d_1\mathrm{\dots }{d}_n{d}_{\pi (1)}\mathrm{\dots }{d}_{\pi (n)}\mid \forall i\ne j.d_i\ne d_j\wedge \pi \in {𝒮}_n\}$.

For 1, by nominal sets reasoning, $d\in \mathrm{𝗌𝗎𝗉𝗉}(u^{-1}L)$ iff $u^{-1}L\ne {((d{d}^{\prime })\cdot u)}^{-1}L$ for any fresh $d^{\prime }$.
For 2, suppose there exists $d\notin \mathrm{𝗋𝗇𝗀}(\rho )$ such that $d\in {\mathrm{𝗆𝖾𝗆}}_L(u)$. By 1, $u^{-1}L\ne {((d{d}^{\prime })\cdot u)}^{-1}L$. However, as $d^{\prime }$ is fresh in $u$ and $d$ is not stored in $\rho$, both $u$ and $(d{d}^{\prime })\cdot u$ reach the same configuration $(q,\rho )$, which implies $u^{-1}L=ℒ(q,\rho )={((d{d}^{\prime })\cdot u)}^{-1}L$, contradiction. $◀$

The memorability problem asks, given as input a pDRA $𝒜$, a word $u$ and a datum $d$ in $u$, whether $d$ is $ℒ(𝒜)$-memorable in $u$.

For the first claim, following Lemma 9, take any datum $d^{\prime }$ fresh in $u$. It suffices to compute the configurations $(q,\rho )$ and $(q^{\prime },{\rho }^{\prime })$ reached by the pDRA on reading $u$ and $(d{d}^{\prime })\cdot u$ respectively, and check if $ℒ(q,\rho )\ne ℒ(q^{\prime },{\rho }^{\prime })$ holds, which is in PTime (cf. Theorem 8).
For the second claim, we only provide a proof sketch. We show that the set of registers which contain the memorable data in a configuration, only depends on the state of the configuration. This allows one to turn any pDRA into a frugal one. $◀$

Since $u{\equiv }_L^{\tau }v$, we have $u^{-1}L={(\tau \cdot v)}^{-1}L$. By nominal sets reasoning (see e.g. [21, Ch. 2]), we have $\mathrm{𝗌𝗎𝗉𝗉}(u^{-1}L)=\mathrm{𝗌𝗎𝗉𝗉}({(\tau \cdot v)}^{-1}L)=\mathrm{𝗌𝗎𝗉𝗉}(\tau \cdot (v^{-1}L))=\tau \cdot \mathrm{𝗌𝗎𝗉𝗉}(v^{-1}L)$. Hence $|{\mathrm{𝗆𝖾𝗆}}_L(u)|=|{\mathrm{𝗆𝖾𝗆}}_L(v)|$. $◀$

We illustrate data word equivalence via a simple albeit non-trivial example. We then focus on the suitability of this relation as a Myhill-Nerode equivalence relation.

Let $𝒜$ be a pDRA recognizing $L$. Take any state $q$ and let $u,v\in {𝒟}^{\ast }$ be such that: $(q_0,\mathrm{\varnothing }){\stackrel{𝑢}{\to }}_{𝒜}(q,{\rho }_1)$ and $(q_0,\mathrm{\varnothing }){\stackrel{𝑣}{\to }}_{𝒜}(q,{\rho }_2)$. Since ${\rho }_1,{\rho }_2$ are injective (as by definition of pDRA, there are no duplicates in register assignments), there exists a data permutation $\tau$ such that ${\tau |}_{\mathrm{𝗋𝗇𝗀}({\rho }_2)}={\rho }_2^{-1};{\rho }_1$. Then, from $(q_0,\mathrm{\varnothing }){\stackrel{𝑣}{\to }}_{𝒜}(q,{\rho }_2)$ we get $(q_0,\mathrm{\varnothing }){\stackrel{\tau \cdot v}{\to }}_{𝒜}(q,{\rho }_2;\tau )=(q,{\rho }_1)$. Therefore, $u^{-1}L={(\tau \cdot v)}^{-1}L$, i.e. $u{\equiv }_{L}v$. This implies that ${\equiv }_L$ has finite index.
The other direction is based on the construction of a canonical automaton explained below. $◀$

Let us assume that ${\equiv }_L$ has finite index. For each equivalence class $c$ of ${\equiv }_L$, let $u_c$ be some representative of $c$ and ${\rho }_c:[1,|{\mathrm{𝗆𝖾𝗆}}_L(u_c)|]\to {\mathrm{𝗆𝖾𝗆}}_L(u_c)$ a register assignment. For any word $u$, we hereby denote by $[u]$ its ${\equiv }_L$-equivalence class. We now construct a minimal pDRA ${𝒜}_L$ recognizing $L$, whose states are the chosen class representatives, with the following invariant (shown in Lemma 18 below): on reading any word $v$, ${𝒜}_L$ reaches configuration $(u_c,{\rho }_c;{\tau }^{-1})$ for some $\tau$ such that $u_c{\equiv }_L^{\tau }v$. We construct the minimal pDRA ${𝒜}_L=(Q_L,{\mu }_L,q_0,F_L,{\delta }_L={\delta }_{=}\uplus {\delta }_{\ne })$ as follows:

• $\mathrm{■}$

  the number of registers is $r=\max (\{|{\mathrm{𝗆𝖾𝗆}}_L(u)|\mid u\in {𝒟}^{\ast }\})$ (it exists by Lemma 14);

• $\mathrm{■}$

  $Q_L=\{u_c\mid c\in {𝒟}^{\ast }{/}_{{\equiv }_L}\}$, ${\mu }_L(u_c)=[1,|{\mathrm{𝗆𝖾𝗆}}_L(u_c)|]$ for all $u_c\in Q_L$, and $q_0=u_{[ϵ]}$;

• $\mathrm{■}$

  $F_L=\{u_c\mid u_c\in L\}$;

• $\mathrm{■}$

  ${\delta }_{=}$ is defined as follows. Let $u_c$ be some representative and $d\in {\mathrm{𝗆𝖾𝗆}}_L(u_c)$. After a successful equality test with register $k$, the automaton goes to state $u_{c^{\prime }}$ where $c^{\prime }=[u_{c}d]$ and $d={\rho }_c(k)$. So, we add the transition ${\delta }_{=}(u_c,k)=(u_{c^{\prime }},\pi )$ for some $\pi$ that we now construct. The registers need to permuted to account for the fact some data of ${\mathrm{𝗆𝖾𝗆}}_L(u_c)$ may need to be deleted (if they are not memorable in $u_{c}d$), and the fact that $u_{c}d$ and $u_{c^{\prime }}$ have equal residual languages up to some permutation $\tau$. Let $i=|{\mathrm{𝗆𝖾𝗆}}_L(u_c)|$, $j=|{\mathrm{𝗆𝖾𝗆}}_L(u_{c^{\prime }})|$ and $\tau :𝒟\to 𝒟$ such that $u_{c^{\prime }}{\equiv }_L^{\tau }{u}_{c}d$. Let ${\pi }^{\prime }={\rho }_c;\tau ;{\rho }_{c^{\prime }}^{-1}$. Note that $j\le i$, $\mathrm{𝗋𝗇𝗀}({\pi }^{\prime })=[1,j]$ and $\mathrm{𝖽𝗈𝗆}({\pi }^{\prime })\subseteq [1,i]$. Then, $\pi :[1,i]\to [1,i]$ is defined to be a canonical extension of ${\pi }^{\prime }$ to $[1,i]$.

• $\mathrm{■}$

  ${\delta }_{\ne }$ is defined similarly as ${\delta }_{=}$, we let ${\delta }_{\ne }(u_c)=(u_{c^{\prime }},i+1,\pi )$ where $c^{\prime }=[u_{c}d]$ for $d$ any fresh datum, and $\pi$ is a canonical extension of ${\pi }^{\prime }$ to $[1,i+1]$, for ${\pi }^{\prime }={\rho }_c[i+1\mapsto d];\tau ;{\rho }_{c^{\prime }}^{-1}$. So, $d$ is stored in the first available register ($i+1$), before the permutation $\pi$ is applied.

Note that ${𝒜}_L$ is complete. We illustrate this construction with the following example.

We finally prove that $ℒ({𝒜}_L)=L$ and that the automaton is minimal. For this, we use the fact that runs of ${𝒜}_L$ compute the ${\equiv }_L$-equivalence class of the word they read.

For space reasons, we only prove 2 here.It is immediate as a consequence of 1 that $ℒ({𝒜}_L)=L$. Indeed, $v\in {𝒜}_{ℒ}$ iff the state $u_c$ reached by ${𝒜}_L$ on $v$ is accepting, iff $u_c\in L$, iff $ϵ\in u_c^{-1}L={(\tau \cdot v)}^{-1}L$ for some $\tau$, iff $\tau \cdot v\in L$, iff $v\in L$ as $L$ is equivariant.
We prove that ${𝒜}_L$ is minimal. First, ${𝒜}_L$ is complete by definition. It is frugal by 1, as registers contain exactly the memorable data (and it is necessary as proved by Lemma 9). If it is not state minimal, then there exists a pDRA with less states than the index of ${\equiv }_L$ recognizing $L$. Therefore, there exist two inequivalent words $u{\not\equiv }_{L}v$ which respectively reach two configurations $(q,{\rho }_1)$ and $(q,{\rho }_2)$ with the same state $q$. As shown in the proof of Theorem 16, this implies that $u{\equiv }_{L}v$, contradiction. $◀$

Minimizing a pDRA $𝒜$ recognizing a language $L$ can be done in EXPTime. Indeed, it suffices to apply the construction of the canonical automaton ${𝒜}_L$ step-by-step, starting from initial state $ϵ$, based on a subroutine deciding ${\equiv }_L$. From a state $u_c$ with chosen assignment ${\rho }_c$ created so far and for all data $d\in \mathrm{𝗋𝗇𝗀}({\rho }_c)\cup \text{min}(𝒟\setminus \mathrm{𝗋𝗇𝗀}({\rho }_c))$, the algorithm checks whether $u_{c}d{\equiv }_L{u}_{c^{\prime }}$ for some existing state $u_{c^{\prime }}$, otherwise state $u_{c}d$ is created, with ${\rho }_{[u_{c}d]}$ being arbitrary. Whether $u_1{\equiv }_L{u}_2$ holds, given $u_1,u_2$ and $𝒜$, can be decided in EXPTime: compute the configurations $(q_i,{\rho }_i)$ reached by $𝒜$ on $u_i$, and check if there exists a permutation $\tau :\mathrm{𝗋𝗇𝗀}({\rho }_2)\to \mathrm{𝗋𝗇𝗀}({\rho }_2)$ such that $L_{𝒜}(q_1,{\rho }_1)=L_{𝒜}(q_2,{\rho }_2;\tau )$. The latter can be done in PTime by Theorem 8. Note that due to the enumeration of register permutations, the minimization procedure is exponential only in the number of registers, which in turn is in PTime for a constant number of registers.

Whether we can do better than exponential time is a hard question. We can show that checking whether a complete and frugal pDRA is not minimal (called pDRA-nonMin problem) is at least as hard as the Graph Isomorphism problem (GI). GI is known to be in NP but not known to be in coNP.

We introduce some notions towards an equivalence relation on data words, whose index corresponds to the minimal number of states that suffices for a $\mathrm{\Pi }$-DRA to recognize a data language $L$. A key ingredient, unlike in pDRAs, is that the order in which $L$-memorable data are stored by a $\mathrm{\Pi }$-DRA is canonical, i.e., it only depends on $\mathrm{\Pi }$. Thus we can define, for any word $w\in {𝒟}^{\ast }$, a word ${\mathrm{𝗆𝖾𝗆}}_L^{\mathrm{\Pi }}(w)$ which orders the $L$-memorable data of $w$. We illustrate it for $\mathrm{\Pi }=\text{Lar}$. Initially, ${\mathrm{𝗆𝖾𝗆}}_L^{\text{Lar}}(ϵ)=ϵ$. Consider a word $w=1234$ where ${\mathrm{𝗆𝖾𝗆}}_L^{\text{Lar}}(w)=1234$ and ${\mathrm{𝗆𝖾𝗆}}_L(w2)=\{2,3\}$. Then, ${\mathrm{𝗆𝖾𝗆}}_L^{\text{Lar}}(w2)=32$.

In general, for an arbitrary policy $\mathrm{\Pi }$, ${\mathrm{𝗆𝖾𝗆}}_L^{\mathrm{\Pi }}(w)$ can informally be defined as the register assignment reached by any frugal $\mathrm{\Pi }$-DRA recognizing $L$ and reading $w$ (modulo considering infinite state $\mathrm{\Pi }$-DRAs, as $L$ is equivariant but not necessarily regular). Formally, ${\mathrm{𝗆𝖾𝗆}}_L^{\mathrm{\Pi }}(ϵ)=ϵ$, and ${\mathrm{𝗆𝖾𝗆}}_L^{\mathrm{\Pi }}(wd)$ is built from $m={\mathrm{𝗆𝖾𝗆}}_L^{\mathrm{\Pi }}(w)$ and $M={\mathrm{𝗆𝖾𝗆}}_L(wd)$ as follows. First, let $m^{\prime }=md$ if $d$ is not $L$-memorable in $w$, and $m^{\prime }=m$ otherwise. Let $k$ be such that $m^{\prime }[k]=d$. The positions of $m^{\prime }$ are reordered, giving a word $m^{\prime \prime }$ of same length, obtained by applying permutation $\mathrm{\Pi }(|m|,k)$ on $m^{\prime }$. Then, ${\mathrm{𝗆𝖾𝗆}}_L^{\mathrm{\Pi }}(wd)$ is obtained by applying on $m^{\prime \prime }$ the erasing morphism which replaces any datum not in $M$ by $ϵ$.