Why can't we reduce register automata to symbolic automata?

Question

When considering automata, they are normally considered over finite alphabets. The following are two types of automata that can handle words over infinite alphabets (definitions included for clarity).

The symbols $\triangleright$ and $\triangleleft$, appended to the beginning and end of the word respectively, are delimiters and are not in $\Sigma$. That is, the automata process words of the form w = $\triangleright$v$\triangleleft$ where v $\in$ $\Sigma^*$.

A k-register automaton $\mathcal A$ over $\Sigma$ is a 5-tuple (Q, $q_0$, F, $\tau_0$, P) where:

• Q is a finite set of states;

• $q_0$ $\in$ Q is the initial (or starting) state;

• F $\subseteq$ Q is the set of final (or accepting) states;

• $\tau_0$ : $\{0,1,...,k\}$ $\to$ $\Sigma$ $\cup$ $\{\triangleright,\triangleleft\}$ is the initial register assignment; and,

• P is a finite set of transitions of the form ($i$, $q$) $\to$ ($q'$, $d$) or $q$ $\to$ ($q'$, $i$, $d$) for $i$ $\in$ $\{0,1,...,k\}$, $q$, $q'$ $\in$ Q and $d$ $\in$ $\{Stay, Left, Right\}$.

A symbolic finite automaton (SFA) $\mathcal M$ is a 5-tuple ($\mathcal A$, Q, $q_0$, F, $\Delta$) where:

• $\mathcal A$ is an effective Boolean Algebra (the alphabet);
• Q is a finite set of states;
• $q_0$ $\in$ Q is the initial (or starting) state;
• F $\subseteq$ Q is the set of final (or accepting) states; and,
• $\Delta$ $\subseteq$ Q $\times$ $\Psi_{\mathcal A}$ $\times$ Q is a finite set of transitions.

Research has shown that for register automata, equivalence is not decidable but in symbolic automata, it is. My question is why? These two automata types work with similar results, so why is it that we can't reduce one to the other?

Something tells me this is a very simple problem but I can't seem to find an answer anywhere, so thank you for any help! :)

My current thoughts are to do with the fact that SFA require their alphabet to be an effective boolean algebra, whereas RA work on anything and so their alphabets dont have to follow the rules of a Boolean algebra. I dont know how to correctly formulate this idea into anything useful though.

Answer 1

The basic difference is that register automata have a memory while symbolic finite automata do not. Over an infinite alphabet this gives RA a power that can't be replicated in SFAs. Symbolic automata can only recognize unary predicates, and other relations are much harder.

For a simple example, consider the language $L=\{xx\mid x\in\Sigma\}$. That is, the set of all strings of length 2 that repeat a character. There is an easy RA to achieve this: state 0 reads x and stores it in register 1, going to state 1 (i.e. $q_0\to (q_1,0,\mathsf{right})$), and state 1 goes to the accept state 2 if the current value matches (that is $(q_1,0)\to (q_2,\mathsf{stay})$, and $F=\{q_2\}$) and rejects otherwise.

Suppose that a SFA accepts this language, where $\Sigma$ is infinite. Because for all $x\in\Sigma$, $xx\in L$, every character must initially be permitted. That is, for all $x\in\Sigma$ there is a state $q_x$ such that $(q_0,\phi,q_x)\in\Delta$ and $\phi(x)$ is true. Since $\Delta$ (and $Q$) are finite, there are clearly a finite number of such states $q_x$. But they are being tasked with distinguishing an infinite number of possible outcomes, depending on which $x$ was read. More precisely, by the pigeonhole principle there must exist $x\ne y$ such that $q_x=q_y$. Then the SFA must accept the string $x$ starting from $q_x$, since $xx\in L$, but that means it also accepts the string $x$ starting from $q_y$, so $yx\in L$ as well and hence the SFA doesn't correctly recognize $L$.

Answer 2

There is an extension of symbolic automata with registers. See

https://arxiv.org/abs/1811.06968