The group $(\mathbb{Z}, +)$ is automatic (ala Khoussainov) when using the "standard" representation in a decimal base. But if I want to use a different representation of Z, encoding my integers with the alphabet $\Sigma = \{y, z\}$
$0 = z$
$1 = yz$
$-1 = zy$
$2 = yyz$
$-2 = zyy$...

however the representation of each integer is not unique... $ z = yzy = yyzyy = yyyzyyy$ (the standard construction in set theory) This leads to problems later.

If we define
$a + b :=$ match $a$ with
$|z \rightarrow b$
$|y^nzy^m \rightarrow y^{n-1}zy^m + yb$
$|zy^n \rightarrow zy^{n-1} + by$

Now, by some convolution function, I can accept equations such as "$z + z = z$" or "$yyyz + zyy = yyyzyy$" but not equations such as "$z + z = yzy$" and "$yyyz + zyy = yz$"

Should this (unary integral addition) count as an automatic function?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.