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" <mailbox@dmitry-kazakov.de>
Newsgroups: comp.compilers
Date: Sat, 17 Nov 2007 10:10:14 +0100
Organization: cbb software GmbH
References: 07-11-048
Keywords: parse, theory

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

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