Primitive recursion and transducers

11/23/2009 please see the updated version: here. Yet another version of the recursion/transducer paper . The main result is that simultaneous primitive recursion on strings corresponds to general products of state machines.

Primitive recursion on strings is analogous to primitive recursion on integers where we define f(0,x) = g(x) and f(n+1,x) = h(f(n,x),x). In strings the null string corresponds to 0 and appending a character corresponds to adding one so that “wa” is the string obtained by appending “a” to “w“. We can also easily define concatenation of strings: concat(w,nullstring)=w and concat(w,ua)= concat(w,u)a Primitive recursion is then:

f(nullstring,x)= g(x)

f(wa,x) = h(a,f(w,x))

You can produce a state machine from such a function trivially by associating each possible value of the function with a state: so there is a state  s= f(w) for each s in the image of f. Then the transition map  Next(s,a)=s’ if and only if h(a,s)=s’.  Let’s make an output function Output(s)=s, so we can get a specific type of state machine – a transducer – or state machine with output. And x0 is the initial state. Call this state machine Transducer(f).  Now if Transducer(f) is defined and g(w) = h(f(w)) then Transducer(g) can be Transducer(f) with a new output function – and then we can throw out any duplicate and unreachable states. If the output function of Transducer(f) is Output_f(s)=x then the new output function Output_g(s)= h(Output_f(s)). And it should be clear that for any state machine, finite or not, there is a corresponding function that can be constructed by primitive recursion on strings and composition.

Simultaneous recursion on strings works by defining two functions F and F* simultaneously (big surprise). Suppose we have g_1 … g_n which are all primitive recursive string functions. Then we can make the following somewhat peculiar definition

1. F(w,i) = g_i(F*(w,i))
2. F*(nullstring,i)= nullstring
3. F*(wa,i) = concat( F*(w,i) , h(a,i,F(w,1) …, F(w,n)))

The idea is that F(w,i) is the output of component i when given the input F*(w,i) and also that h(a,i,F(w,1) …, F(w,n)) is the sequence (string) of events that happen to component i when “a” happens to the composite system in the state determined by “w”. This type of composition has a couple of nice properties.

1. if G(w) = g(F(w,1) …, F(w,n)) then there is an H which can be constructed with just composition and ordinary primitive recursion on strings so that H(w)=G(w). In other words, simultaneous primitive recursion on strings doesn’t create any more state machines, it just tells us how to decompose (divide) state machines.
2. If each g_i corresponds to a finite state machine then G corresponds to a finite state machine.
3. F corresponds to a state machine that is the “general product” of the state machines corresponding to machines corresponding to g_i. I won’t go into details here, but the idea is that simultaneous primitive recursion is essentially a representation of a general automata product in the string function domain!  Read the paper if you want the details.
4. There are some immediate implications for the monoids induced by the state machines and the monoid products induced by composition.

My main interest is in using this stuff to understand big state systems. But the coincidence of simultaneous primitive recursion on string functions corresponding to the general product of automata is good news in terms of validating that the mathematical basis has a structure and is not just a jury rigged construct held together by axioms and hope.