Re: Algebraic definition of word substitution?

On Fri, 16 Nov 2007 11:11:22 -0800 (PST), Tegiri Nenashi wrote:

Arguably word substitution is the most frequent operator in
programming. Yet I struggle to see how is it defined. Formally, given
a word over an alphabet of terminal symbols, say {a,b,c,...} how do
we derive a word where each occurrence of s is substituted with t?

It is a ternary operation (per word symbol):

S x S x S --> S
---------------
a a a -> a
....
a s t -> a
b s t -> b
....
r s t -> r
s s t -> t
t s t -> t
....
z z z -> z

Maybe you want to split it into binary operations? If so, then you could
add the word 0 to the language and a pair of operations like * and +:

X * Y = 0 iif X=Y and X, otherwise

X + Y = Y iff X=0 and X, otherwise

Then (X * s) + t will do substitution s->t on X.

BTW, in image processing there are so-called ROPs (Raster Operations) which
serve similar purposes.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
.