Finite-time encoding of a group

Definition

Symbol-free definition

An encoding of a group is said to be a finite-time encoding if all the algorithms (outputting the identity element, computing the product, computing the inverse, and testing membership) terminate in finite time.

Explicit definition with symbols

Let $G$ be a group. A finite-time encoding of $G$ over a binary alphabet (or equivalently, over any constant-sized alphabet) is an injective map from $G$ to the set of words in that alphabet. In other words, each element of $G$ is expressed uniquely as a word over that alphabet. This is called the code of that element of the group. We further have the following:

• An algorithm that outputs the code for the identity element of the group (in finite time)
• An algorithm that takes as input the codes of two elements $g,h\in G$ and outputs the code for $gh$ in finite time
• An algorithm that takes as input the code of an element $g\in G$ and outputs the code for $g^{-1}$ in finite time
• An algorithm that takes a word $w$ and outputs whether it occurs as a code-word for any element of $G$

Relation with other properties

Stronger properties of encodings

• Bounded-time encoding of a group
• Log-size encoding of a group