# Re: Algebraic definition of word substitution?

## "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>Sat, 17 Nov 2007 10:10:14 +0100

From comp.compilers

Related articles
Algebraic definition of word substitution? TegiriNenashi@gmail.com (Tegiri Nenashi) (2007-11-16)
Re: Algebraic definition of word substitution? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-11-17)
Re: Algebraic definition of word substitution? mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2007-11-17)
| List of all articles for this month |

 From: "Dmitry A. Kazakov" Newsgroups: comp.compilers Date: Sat, 17 Nov 2007 10:10:14 +0100 Organization: cbb software GmbH References: 07-11-048 Keywords: parse, theory Posted-Date: 18 Nov 2007 01:06:35 EST

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

Post a followup to this message