Browse Theses

"Certain Rational Sets in Formal Language Theory" considers monoids as "memory storage" for non-deterministic computations: I examine the images in free monoids of rational subsets of various (non-free and, in general, finitely presented) monoids M under rational transduction; call the resulting sets M-transduced.

From Salomaa's paper on equality sets, it follows, for example, that if A* is the free monoid generated by two elements and if M = A* $\times$ A* then M-transduced consists of the recursively enumerable sets.

The more important results obtained are the following: (1) If M is a monoid, and if P denotes the free product of M with the non-negative integers (identity elements being amalgamated), then P-transduced consists exactly of the sets rational over M-transduced. From this follows the fact that if M is a Kleene monoid, then so is P. Reutenauer's theorem ("The free product of two Kleene monoids, one of which has a trivial group of units, is again Kleene") now follows easily from a more general result of mine. (2) The composition of rational transductions between free monoids is again rational, as is well known. I provide a new proof of this fact, valid for any equidivisible Kleene monoid. (3) Results from Eilenberg-Schutzenberger's well-known paper on rational sets in commutative monoids are used to derive facts about the complexity of M-transduced when M is commutative. The Eilenberg-Schutzenberger results imply Parikh's theorem for context-free languages. I obtain some structure theorems for commutative Kleene monoids.

In a universal algebraic setting, additional results are obtained. Perhaps most interesting is a generalization of the known theorem, "The set of base k representatives of a recognizable subset of the non-negative integers is recognizable in (0,1, ...,k $-$ 1)*." The proof involves functions which are themselves not rational.