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

Return to the comp.compilers page.
Search the comp.compilers archives again.