Monoids and linear systems: solution

[Mark Hopkins]

Monoids and Languages

-------- -------- -------- -------- -------- -------- -------- --------
This is a followup to "Monoids and Linear Systems". Unfortunately, only
one attempt so far was made to solve the problem posed there. Dexter Kozen
essentially provided a solution via references [1] and [2]. Here, a direct
solution will be given based on an interesting relation between the algebra
discussed in [2], the definition given in the previous article, and a third
algebra to be presented below. [3]

Contents:
(1.1) Regular Monoid = Rational Monoid
(1.2) Automata as Linear Systems of Equations
(1.3) The 2nd Challenge: prove that --
"Every computeable language is represented by a regular expression"

(1.1) Regular Monoid = Rational Monoid
In the original article a regular monoid was defined as follows:

DEFINITION 1: A monoid is an algebraic system containing an element 1 and a
product such that:
a(bc) = (ab)c
a1 = a = 1a

DEFINITION 2: A regular monoid M is a monoid which is partially ordered and
closed under least upper bounds of all finite subsets and the
least upper bounds of subsets of the form { a^n: n >= 0 } for
which:

(1) a 0 c = 0 (where 0 = lub( {} ) is the least element of M).

(2) a (lub B) c = lub { a b c: b is in B }
whenever (lub B) is defined for a subset B of M.

Use the operation a1 + a2 + ... + an to denote lub { a1, a2, ..., an } when
n > 1, and the operation a* to denote lub { a^n: n >= 0 }.

Property (1) is actually a special case of (2) where B is the empty set, so
only (2) is needed.

First, let's state the following.

DEFINITION 3: The rational subsets, R(M), of a monoid M are the sets closed
under:
(1) Finite Unions
(2) Kleene Star a* = { a^n: n >= 0 }
(3) Concatenation AB = { a b: a is in A, b in B }
and containing the singletons {x} for each x in M.

THEOREM 1: Let M be a monoid generated by X. Then:

(a) The smallest collection of subsets closed under (1)-(3) of
DEF. 3 and containing the singleton {x} for each x in X is
R(M). We'll use the term R(X) and R(M) interchangeably

(b) R(X) contains an isomorphic copy of M as a subset with the
injection x |-> {x}.

So it's customary to use {x} and x interchangeably.

A definition similar to DEF. 2 can be posed:

DEFINITION 4: A Rational Monoid is a partially ordered monoid in which each
rational subset has a least upper bound.

One then has the following theorem, which will greatly illuminate my choice
of of the term "Regular Monoid".

THEOREM 2: Rational Monoids and Regular Monoids are the same thing.
Proof:
Given a regular monoid M, let us provisionally call one of its subsets B
"regular" if lub B exists. Then as per the definition cited above, regular
subsets have the following closure properties:

(a) All finite subsets are regular.
(b) All sets of the form { a^n: n >= 0 } are regular.
(c) All sets of the form a B c = { a b c: b is in B }
are regular when B is regular.

Rational subsets of a monoid easily satisfy closure properties analogous to
all three above. So every rational monoid is a regular monoid.

The converse is proven by showing closure the other way around. This is
done by proving the three properties:

(a) If A and B are regular subsets then so is A union B with

lub (A union B) = lub { lub A, lub B } = lub A + lub B

(b) If A and B are regular subsets then so is

AB = lub { a b: a is in A, b in B }
with
lub AB = (lub A) (lub B)

(c) If A is a regular subset then so is

A* = { 1 } union { a1 a2 ... an: n > 0, ai in A }

with
lub A* = (lub A)*

Also, A* = union { A^n: n >= 0 }, where A^0 is defined as {1}, A^1 as A and
A^{n+1} as A^n A for each n > 0.

To prove these, the following property of least upper bounds will be used:

LEMMA 1: If { A_i: i is in I } is a family of sets contained in a partially
ordered set and A = union ( A_i: i in I ) then A has a least upper
bound whenever all the A_i do with:

lub A = lub { lub A_i: i in I }
Proof: Elementary

COROLLARY 1: If A and B have least upper bounds then so does A union B with
lub (A union B) = lub { lub A, lub B }.

So assume that A and B are regular subsets. Then we have:

(a) lub A + lub B = lub { lub A, lub B }
= lub (A union B) by LEMMA 1

(b) lub A lub B = lub { a lub B: a in A } by (2) under DEF. 2
= lub { lub { ab: b in B }: a in A } also by (2)
= lub { a b: a in A, b in B } by LEMMA 1
= lub AB

(c) (lub A)* = lub { (lub A)^n: n >= 0 } by DEF. 2
= lub { lub (A^n): n >= 0 } by (b)
= lub union { A^n: n >= 0 } by LEMMA 1
= lub A*

Technically, the second step requires a little bit more than (b) since it's
also necessary to show that lub (A^0) = lub {1} = 1 = (lub A)^0.

COROLLARY 2: Let M be a regular monoid generated by X. Then M is the image
R(X) under the homomorphism B |-> lub B.

In [1] Kozen gives the following axiom system for a ...

DEFINITION 5: Kleene Algebra
(a) Semi-Ring Properties
a(bc) = (ab)c a + (b + c) = (a + b) + c
a1 = a = 1a a + 0 = a = 0 + a
a0 = 0 = 0a a + b = b + a
a(b + c) = ab + ac
(b + c)a = ba + ca

(b) Idempotency: a = a + a
(c) lub { a b^n c: n >= 0 } exists and is equal to a b* c.

where the ordering relation is the one define which makes a + b = lub{a,b},
namely: a <= b <==> a + b = b.

DEFINITION 6: A Kleene subset of a Kleene algebra is a subset either of the
form { a b^n c: b >= 0 } or finite.

This turns out to be yet another equivalent of DEF. 2.

THEOREM 3: Kleene Algebras and Rational Monoids are the same thing.
Proof:
Clearly every rational monoid is a Kleene algebra since it satisfies all
the axioms for a semi-ring with idempotency where lub {} is the semi-ring 0
and lub { a, b } is the additive operation.
Part (c) is all that needs to be shown. This follows directly from item
(2) under DEFINITION 2.

The prove the converse means to show that the Kleene subsets of a Kleene
Algebra will have the following closure properties:

(a) All finite subsets are Kleene subsets.
(b) All subsets { a^n: n >= 0 } are Kleene subsets.
(c) All subsets { a b c: b in B } are Kleene subsets whenever B is too.

Parts (a) and (b) come straight out of DEFINITION 5. In particular, when c
and a are both 1 then DEF. 5 (c) reduces to

{ b^n: n >= 0 } = { a b^n c: n >= 0 } = a b* c = b*

For part (c), assume that B is either a Kleene subset. It is either of the
form { a' b'^n c': n >= 0 } or is finite. In these respective cases:

{ a b c: b in B } = { a (a' b'^n c') c: n >= 0 }
= { (a a') b'^n (c' c): n >= 0 }
and
{ a b c: b in B } is finite

which are both Kleene subsets.

Of all the equivalent versions, I think the Rational Monoid best defines
the essential features of this algebra. A rational monoid is really just a
regular expression algebra defined with a set of relations over it. Plenty
of significant examples are out there. For instance, the algebra generated
by the set { o, p, q, b, d, y, z } with the relations

rs = sr for all r in { y, z } and s in { o, p, q, b, d }.
pq = bd = 1, o^2 = o
pd = bq = oq = od = po = bo = 0
1 = qp + db + o

will yield an algebra under which the set of elements of the form o r o and
set of context-free languages over { y, z } will have as an isomorphism the
map L |-> (lub L) o [See part 1.3 below].

(1.2) Automata as Linear Systems of Equations
Following the previous article, define a linear system of equations over
a subset X of a rational monoid M as one whose equatons have the form:

v = lub { t1, t2, ... tn } = t1 + t2 + ... + tn (1)
where ti is either 1 or a term of the form x v'

where v, v' denote variables and x an element of X. For each v, define the
set |v| as the set of all terms:

1 if 1 is a term on the right-hand side of the
of the equation for v.

x1 x2 ... xn if there are variables v = v(0), v(1), v(2), ..., v(n)
n > 0 such that xi v(i) is on the right hand side of the
equation for v(i - 1), i > 0, and 1 is on the
right hand side of the equation for v(n).

This can be linked to that of an finite state automaton as follows:

* The set of states is the set of variables { v1, ..., vm } for some
m > 0 and the start state is v1.
* q = 1 + ... iff q is a final state
* q = ... + x q' + ... iff there is a transition q --> q' on x.

Therefore, the set |v| defined above is just the set of all words which are
deriveable by a sequence of transitions from state v to a final state. The
set |v1| is thus the language accepted by the automaton.

Now let K(X) denote the set of finite sequences over X. Each element of
K(X) denotes a word. Let L(X) class of all subsets of K(X). These objects
denote the languages over X. Using the following notation:

0 = {}
w = { w }, for any word w in K(X).
a b = { a' b': a' is in a, b' in b }
a* = union { a^n: n >= 0 }
a + b = a union b

Then it's easy to see that L(X) is a rational monoid in which set inclusion
is the partial ordering. This is trivial since the partial order over L(X)
is complete.

Finally, let R(K(X)) denote the subset of L(X) which consists of all the
rational subsets of K(X), these are the regular languages over X. This set
is also clearly a rational monoid. By COROLLARY 2, every rational monoid M
generated by X will be the homomorphic image of R(K(X)) by the composition:

< > lub
R(K(X)) ----> R(X) -----> M
where
<a> = { x1 x2 ... xn: (x1, x2, ..., xn) is in a: n >= 0 }

is the map from R(K(X)) to R(X).

In virtue of the well-known connection between regular languages and finite
state automata one has the property:

For every r in R(K(X)), there is a finite system of m equations
of the form (1) over X with variables v1, v2, ..., vm such that

(1) A solution in the v's is: vi = lub |vi|, i = 1, 2, ..., m
(2) r = lub |v1|.

This property extends to the monoid R(X) in virtue of the homomorphism. So
we end up establishing what we sought out to prove.

Also, the original article also asked for a finite system of equations over
X with the solution r = v1 but for which either (1) or (2) was false. This
might not be possible. I thought I had an example with the algebra defined
by the relations
pq = bd = 1, pd = bq = 0
qp + db = 1

generated by X = { p, q, b, d }, in which r = 1 and the last relation above
is used to derive a system of equations in which (1) or (2) fails. I guess
not.

(1.3) The 2nd Challenge: prove that --
"Every computeable language is represented by a regular expression"

DEFINITIONS:
* Let K(X) and L(X) be as defined above.
* Let L'(X) be the class of all "computeable languages" (i.e., the set of
recursively enumerable subsets of K(X)).
* Given a subset, X, of a regular monoid M define a valuation

| |: L(X) -> R(X) = R(M)
given by
|()| = 1, for the empty sequences
|(x1, x2, ..., xn)| = x1 x2 ... xn, for n > 0, x's in X.
|A| = union { |a|: a is in A }

for each A in L(X).

THEOREM: Given a set X, there exists a finitely generated Universal regular
monoid R(X union D) such that:

(a) x d = d x for all x in X, d in D
(b) The set of all elements in R(X union D) which commute with all
the elements of D is isomorphic to the set L'(X) under the map
L |-> |L|.

"Universal" is meant in the sense of (b).
-------- -------- -------- -------- -------- -------- -------- --------

References and Notes:
[1] Dexter Kozen,
"A Completeness Theorem for Kleene Algebras and the Algebra of Regular
Events", _Information and Computation_ 110, 366-390 (1994).

[2] Dexter Kozen,
_The Design and Analysis of Algorithms_, Springer-Verlag (1992).
Lectures 6 and 7 outline the Kleene Algebra cited above.

[3] By a most remarkable coincidence, all the text happened to line up on
the right side. See "The 2nd Untold Story of Einstein's Secret Theory"
in sci.physics for the true, but untold, story behind this mystery.