Quasi-encoding of a group
BEWARE! This term is nonstandard and is being used locally within the wiki. [SHOW MORE]
Let be a group. An encoding of over a binary alphabet (or equivalently, over any constant-sized alphabet) is the following data:
- An injective mapping from the group to the set of words in that alphabet. In other words, each element of the group is expressed as a word over the alphabet. This is called the code for that element of the group.
- An algorithm that takes in the codes for and outputs the code for .
- An algorithm that takes in the code for and outputs the code for .
A quasi-encoding becomes an encoding if we further have an algorithm that takes as input a word in the language and outputs whether or not it is a valid code-word.
Any quasi-encoding of a group naturally gives a quasi-encoding of any subgroup. Namely, we simply restrict the encoding function (the injective map from the group to the language) to the subgroup.