Sunday, August 4, 2013

String rewriting systems

We can describe rewriting systems on finite alphabets which include finitely presented monoids as a special case. The rewriting rules on words generated by a single letter can be described by an iteration type such as the iteration type of order 4:
(f 0 0 0 0) = (f)
(f 0 0 0 0 0) = (f 0)
One possible partial ordering on words of a finite alphabet is the shortlex ordering which is something we may make use of to canonize words under the rewriting system. We can describe groups generated by two involutions by the dihedral group D_n:
(f 0 1 0 1) = (f 1 0)
(f 0 0 1 1 0 0) = (f 0 1 0)
Groups generated by involutions form their own class that includes the symmetric group S_n the dihedral groups of order D_n products of them and various other groups.

No comments:

Post a Comment