2507.06158

#1 Addition Automata and Attractors of Digit Systems Corresponding to Expanding Rational Matrices [PDF] [Copy] [Kimi] [REL]

Authors: Anjelo Gabriel R. Cruz, Manuel Joseph C. Loquias, Jörg M. Thuswaldner

Let $A$ be an expanding $2 \times 2$ matrix with rational entries and $\mathbb{Z}^2[A]$ be the smallest $A$-invariant $\mathbb{Z}$-module containing $\mathbb{Z}^2$. Let $\mathcal{D}$ be a finite subset of $\mathbb{Z}^2[A]$ which is a complete residue system of $\mathbb{Z}^2[A]/A\mathbb{Z}^2[A]$. The pair $(A,\mathcal{D})$ is called a {\em digit system} with {\em base} $A$ and {\em digit set} $\mathcal{D}$. It is well known that every vector $x \in \mathbb{Z}^2[A]$ can be written uniquely in the form

$$x = d_0 + Ad_1 + \cdots + A^kd_k + A^{k+1}p,$$ with $k\in \mathbb{N}$ minimal, $d_0,\dots,d_k \in \mathcal{D}$, and $p$ taken from a finite set of {\em periodic elements}, the so-called {\em attractor} of $(A,\mathcal{D})$. If $p$ can always be chosen to be $0$ we say that $(A,\mathcal{D})$ has the {\em finiteness property}. In the present paper we introduce finite-state transducer automata which realize the addition of the vectors $\pm(1,0)^\top$ and $\pm(0,1)^\top$ to a given vector $x\in \mathbb{Z}^2[A]$ in a number system $(A,\mathcal{D})$ with collinear digit set. These automata are applied to characterize all pairs $(A,\mathcal{D})$ that have the finiteness property and, more generally, to characterize the attractors of these digit systems.

Subjects: Number Theory , Formal Languages and Automata Theory

Publish: 2025-07-08 16:40:15 UTC

---