Abstract:
Let A be a finite set that will be used as an alphabet. Let A* be the set of all words, of finite length, of symbols from the alphabet A. A word p in A* is said to be primitive if it cannot be expressed as the concatenation of two or more copies of the same word. Each nonnull word w in A* has a unique representation as a power of a primitive word. This provides a way of coordinatizing the set of nonnull words in A* as ordered pairs: Identify each word w with the unique ordered pair (p,n) for which: p in a primitive word; n is a positive integer; and w is the concatenation of n copies of p. We visualize a y-axis labeled with the positive integers as usual. We visualize the set of primitive words as replacing the set of integers (positive, zero, and negative) along an x-axis. (We allow ourselves the freedom to choose whatever one-one correspondence we wish between the set of primitive words and the set of integers.) By the identification of w with the appropriate pair (p,n), the nonnull words in A* are then viewed as lying at the strict points of the strict upper half plane. By a language L over the alphabet A, we mean a set of nonnull words in A*. Each language L can now be viewed as a subset of the upper half plane. We call this visualization of L a 'sketch'. We classify languages by the visual features of their sketches. We say that two languages, L & L', are 'sketch equivalent' if, by an appropriate re-ordering of the primitive words on the x-axis, the sketch of L can be made congruent with the original sketch of L'. For the class of regular languages, we define a computable class of 'sketch parameters' and show that two regular languages are sketch equivalent if and only if they have the same sketch parameters.
If you are interested in having the full paper, email me and a copy will be sent to you as an email attachment.