Hi Mira:

Johan mentioned the term transducer. Below is a definition
from Xerox.

Johan is exploring those transducers in more detail.

Yes, Doug is writing the notes.

-- Karl

>Is the "strategy transducer" a term you came up during the
>seminar as a replace for ``path filters''? Sounds interesting.
>I hope Doug will heve detailed seminar notes.
>
>- Mira 
====================
http://www.rxrc.xerox.com/research/mltt/fsSoft/docs/fst-97/xfst97.html
Generic automata software

From
http://www.xrce.xerox.com/research/mltt/fst/fsnetwork.html

We use the term finite-state network to cover both simple 
automata and transducers. A simple automaton encodes a regular language, 
a transducer represents a regular relation. 
If you are not familiar with these terms, start with Regular Expressions. 
http://www.xrce.xerox.com/research/mltt/fst/fssyntax.html

From:
http://www.xrce.xerox.com/research/mltt/fst/fslook.html

Introduction
A transducer encodes a regular relation, a set of pairs of strings. We call the first member of the pair the upper, the second one the lower string. Every pair in the relation is represented in the transducer by a path, a sequence of arcs from the start state to a final state. Consider, for example, the network in Figure 1. 

 
 Figure 1: The relation [a b -> x] 
 The [a b -> x] relation consists of pairs of strings that are identical except that any instance of "ab" in the upper string corresponds to an "x" in the the lower string. Because the network contains loops, there is an infinite number of paths and, consequently, an infinite number of string pairs in the relation. For example, the pair consisting of "caba" and "cxa" is encoded by the path 0-?-0-a:x-2-b:0-0-a-1. The correspondence between the path and the two strings involved is 
illustrated in Figure 2. 


Upper string:   c   a     b     a  
Path: 0-?-0-a:x-2-b:0-0-a-1 
Lower string:   c     x         a 
Figure 2: The path for the pair consisting of "caba" and "cxa" 
The initial "c" in the upper string is matched by the unknown symbol, ?, because "c" is not in the sigma alphabet of the network. In a transducer, ? is treated as an identity pair: any symbol that is not in the sigma, paired with itself. Therefore, the ? also matches the "c" in the lower string. The first "a" in the upper string matches the upper symbol of the a:x pair. The lower symbol of the same pair matches "x" in the lower string. The "b" in the upper string matches upper symbol of the b:0 pair. This pair does not contribute anything to the lower string because the 0 is the epsilon symbol (the empty string). Finally, the "a" in the upper string matches the a transition, which we take here as an identity pair, a:a, thus getting a match for "a" on the lower side as well.