Monoids and Computation: Syntactic Monoids

While doing some reading on rings, I came across some interesting stuff about
Monoids and syntax. That's right up my alley, so I decided to write a post about that.

We start by defining a new property for monoids - a kind of equivalence
relation called a monoid congruence. A Monoid congruence defines
equivalence classes within the set of values in a monoid. The monoid congruence
relation is generally written as "~", and it's a relation between two values in a
monoid: ~⊆M×M. A monoid congruence has all of the usual properties
of an equivalence relation: it's symmetric, reflexive, and transitive. It also
respects the monoid operator: if a, b, c, and d are all members of a monoid M,
a~c, and b~d, then aºb~cºd.

If we have a monoid congruence relation "~", then we can obviously use it to create a collection of equivalence classes, called congruence classes. If a is a member of monoid (M,º), then we can define the congruence class [a]={m∈M | x~a } - that is, the set of objects in M that are "~" with a.

We can then define a new operation on the congruence classes: if a and b are members of a monoid (M,º), then we can define an operation "*" by
[a]*[b]=[aºb]. If you look at the set of congruence classes of M given by "~", and the "*", what do you get? Another monoid, which we call a quotient monoid. The quotient monoid created by a particular congruence relation "~" is
written M/~.

Now, we take a new step, and this is where it starts to get really interesting. Remember how I described the relationship between monoids and computing devices? We're going to start taking advantage of that. If we take a monoid, and use concatenation
as the notation for the monoid operator, then we can describe products as strings: "abc" is (aºb)ºc.

In automata theory, we talk about formal languages, which are specific sets of strings of symbols. A formal language is usually described by some system of rules, which describe
how the strings in the language are generated. For a very simple example, we can
use a regular expression, like "a⁺b^*" to represent the language consisting of any number of "a"s, possibly followed by any number of "b"s. We can
talk about more complicated languages, by using grammars. For example, the classic
first language that can't be described by simple regular expressions is the following:

X → (X)
X → X X
X → ε

This language consists of sequences of open and close parens where the number of opens and closes is balanced: strings like "()", "(())", "((()(()(()))))", and so on.

If we think of a monoid as a meta-computing machine, then we can
talk about the kinds of languages that can be accepted by a particular
monoid - that is, if we're working with a machine built from the monoid, what kinds of languages can that machine accept? It turns out that we can define that
set using monoid quotients!

We can start by defining a syntactic quotient, using contatenation to denote the monoid operator. If M is a monoid, and S is a subset of M,
then we can define left and right syntactic quotients of S:

• If m∈M, then the right syntactic quotient of S by m,
  written S/m = { a∈M | am ∈ S }.
• If n∈M, then the left syntactic quotient of S by n,
  written n\S = { b∈M | mb∈S }.

We can then use the syntactic quotients to define congruence relations,
exactly as we did above. We get two congruence relations, the right syntactic equivalence, ~s, which is the congruence relation induced by the right syntactic quotient, and the left syntactic equivalence s~, which is the congruence relation implied by the left syntactic quotient. And finally, we can define a total syntactic congruence (also called a double-sided congruence), written ~_s using both:

a ~_s b ⇔ (∀x,y∈M: xay∈S ⇔ xby∈S

So, here's where the connection to computable languages comes in. The syntactic quotient, following the procedure above, defines a new monoid - the syntactic monoid of S, which we call M(S). The syntactic monoid of S is a monoid which accepts
the set S. We call a language - consisting of the strings of symbols that
concatenated together by M's monoid operator result in values in S. So we've finally really gotten to the point where we can really see how a monoid represents a computing device. In computation theory, we can describe every computing device in terms of languages. We can likewise describe computable languages in terms of monoids.

In particular, we can define what it means for a language to be recognizable by a
monoid, M. Take a language, L⊆M. If the set of quotients {L/m|m∈M} is finite,
then L is recognizable by M.

There's more to it than this - transition monoids are particularly interesting. But that's enough for this post. We'll save it for later.