FA presented groups
In some of previous posts we have discussed regular languages and automatic relations from automata theory. This discussion were meant to lead to the upcoming discussion of automatic groups. Groups are one of the most fundamental algebraic structures arising almost everywhere in mathematics. Why to study automatic group? Well this kind of research arouse around sixties when Rabin and others asked what would happen if we impose some kind of algorithmic conditions on mathematical structures. First people studied heavily so called computable structures, i.e. structures recognized by computable functions. These days people study structures under all sorts of algorithmic constraints. Some study in computable constraints, some go beyond and look at Turing machines which work with reals, while some people, like me, study structures with automata-theoretic constraints. One of the first people who have done that are Hodgson, Khoussainov and Nerode.
There are several variants of studying groups in automata-theoretic settings. I know at least three:
Finite automata presentations
Automatic groups which were studied by geometric group theorists
Groups generated by finite automata
Today we are going to discuss the first variant. Let us provide some definitions first.
Definitions
Let $(G,\circ)$ be a a given group. We say that $(G,\circ)$ forms an automatic presentation if:
$G$ is a regular language
$\circ:G\times G\to G$ is an automatic function
We say that a group $G$ is FA-presented if it has an automatic presentation. In other words we are looking for a group isomorphism:
$\phi: D\to G$
such that $D$ is a regular domain with an automatic group operation.
Examples
Clearly, any finite group is determined by a its multiplication table. By taking a large enough alphabet, we can assign a letter for each element. As for group operation, we just need to make use of a multiplication table, which is finite. So any finite group is FA-presented. That was pretty easy. What about infinite groups?
Let us take the easiest example of $G=(\mathbb{Z},+)$. It has a presentation of $G=\langle a\mid \cdot \rangle$. However, we find that this presentation is not automatic, simply because: $a^n \circ a^n = a^{2n}$. Recall that a finite automaton cannot do doubling the length. It might seem a bit disheartening, as the simplest presentation, of this group turned out to be not automatic. Fortunately, there is another presentation, namely dyadic. We can represent each integer as:
\[
n = (-1)^s(a_0 + a_12 + a_2 2^2 + \ldots + a_k 2^k)
\]
where $s,a_i\in\{0,1\}$. So we can represent each element of $\mathbb{Z}$ as:
\[
n = sa_0a_1a_2\ldots a_k
\]
In this presentation, domain of $\mathbb{Z}$ becomes $\{0,1 \}^*$ which is clearly a regular language. Moreover, a group operation is automatic, simply because addition involves a carrying which involves a finite amount of memory. So $\mathbb{Z}$ joins the class of FA-presented groups.
Later we will learn that a class of FA presented groups can be characterized if the group is finitely generated. Namely, FA presented groups coincide with virtually abelian groups in that case. So we get an impression that FA-presented groups are almost abelian ones. In the next blog posts I hope to cover more examples and properties of these groups.
There are several variants of studying groups in automata-theoretic settings. I know at least three:
Finite automata presentations
Automatic groups which were studied by geometric group theorists
Groups generated by finite automata
Today we are going to discuss the first variant. Let us provide some definitions first.
Definitions
Let $(G,\circ)$ be a a given group. We say that $(G,\circ)$ forms an automatic presentation if:
$G$ is a regular language
$\circ:G\times G\to G$ is an automatic function
We say that a group $G$ is FA-presented if it has an automatic presentation. In other words we are looking for a group isomorphism:
$\phi: D\to G$
such that $D$ is a regular domain with an automatic group operation.
Examples
Clearly, any finite group is determined by a its multiplication table. By taking a large enough alphabet, we can assign a letter for each element. As for group operation, we just need to make use of a multiplication table, which is finite. So any finite group is FA-presented. That was pretty easy. What about infinite groups?
Let us take the easiest example of $G=(\mathbb{Z},+)$. It has a presentation of $G=\langle a\mid \cdot \rangle$. However, we find that this presentation is not automatic, simply because: $a^n \circ a^n = a^{2n}$. Recall that a finite automaton cannot do doubling the length. It might seem a bit disheartening, as the simplest presentation, of this group turned out to be not automatic. Fortunately, there is another presentation, namely dyadic. We can represent each integer as:
\[
n = (-1)^s(a_0 + a_12 + a_2 2^2 + \ldots + a_k 2^k)
\]
where $s,a_i\in\{0,1\}$. So we can represent each element of $\mathbb{Z}$ as:
\[
n = sa_0a_1a_2\ldots a_k
\]
In this presentation, domain of $\mathbb{Z}$ becomes $\{0,1 \}^*$ which is clearly a regular language. Moreover, a group operation is automatic, simply because addition involves a carrying which involves a finite amount of memory. So $\mathbb{Z}$ joins the class of FA-presented groups.
Later we will learn that a class of FA presented groups can be characterized if the group is finitely generated. Namely, FA presented groups coincide with virtually abelian groups in that case. So we get an impression that FA-presented groups are almost abelian ones. In the next blog posts I hope to cover more examples and properties of these groups.
Comments
Post a Comment