We’re moving away from the Perti Net stuff to a simpler problem to describe, though the reduction is pretty convoluted.

**The problem: **Finite Function Generation. This is problem MS5 in the appendix.

**The description: **Given a set of functions F whose domains and co-domains are the same finite set A, and a new function h, also from A->A. Can h be created by composing functions from F?

**Example:** Here’s a pretty simple example. Let A = {0,1,2,3,4,5}

Let F consist of 2 functions: F2(x) = (x+2) mod 6, and F3(X) = (x+3) mod 6

If h is h(x) = (x+1) mod 6, we can get it from F2(F2(F3(x))).

But if we replace F3 with F4 (X) = (x+4) mod 6, then we can never make h, because all combinations of F2 and F4 keep the same odd/even parity of the inputs.

**Reduction: **Kozen, who has the paper with the reduction on Finite Automata Intersection, uses that problem here as the basis for his reductions. G&J say that the reduction is from Finite Automata Intersection, but since the finite automata we use are the ones created in that reduction, I think it’s more correct to say that this reduction is from LBA Acceptance, since that is where we start with an arbitrary problem instance.

The Finite Automata Intersection reduction started with an arbitrary machine M and an input string w, and made a bunch of finite automata F_{i} such that M accepts w if and only if there was at least one string in the language of each F_{1} (i.e., the intersection of the languages of the machines is non-empty). We’ll label state j of machine i q_{i}^{j}. Because they are FA’s, each machine i has one start state (q_{i}^{start }), and they were built to have one final state (q_{i}^{final}).

Create a set A which will be the set of the states of all machines, plus three extra elements: o_{1}, o_{2}, and o_{3}. Every symbol in the common alphabet of the machines a gets a function f_{a}:

- f
_{a}(q_{j}^{j }) = The state we go to from q_{i}^{j }on input a. Note that this will be some q_{i}^{k }for some k (some state on the same machine). - f
_{a}(o_{1}) = o_{3} - f
_{a}(o_{2}) = o_{2} - f
_{a}(o_{3}) = o_{3}

It’s worth mentioning that since the machines are DFAs, there is a well-defined transition from each state on each input symbol, so these are functions that provide a single value for each domain element. Also notice that we can compose these functions to build f_{w} for some string w: f_{w}(q) = the state we end up in starting in state q on the string w. This means that a machine i accepts a string w iff f_{w}(q_{i}^{start }) = q_{i}^{final}.

We’ll add a new function “f_{init}” to our set of functions. f_{init} takes elements from A:

- f(q) returns q
_{i}^{start}if q is any state in a machine q_{i} - f(o
_{1}) = o_{2} - f(o
_{2}) = o_{3} - f(o
_{3}) = o_{3}

Now we’ll build our function h:

- h(q) returns q
_{i}^{final}if q is any state in a machine q_{i} - h(o
_{i}) = f_{init}(o_{i}) for i from 1 to 3.

Suppose that there is a string w in the languages of all of our automata F_{i}. This would mean that for all machines i, f_{w}(q_{i}^{start }) = q_{i}^{final}. It also means that those f functions need to map f_{w}(o_{1}) to o_{3}, f_{w}(o_{2}) to o_{2}, and f_{w}(o_{3}) to o_{3.} We can get this by h = f_{w} ° f_{init}.

In the other direction, suppose we can generate h by the composition of our f functions. The first function in the composition has to be f_{init }because all other functions take o_{1} to o_{3}, and then all functions keep o_{3} at o_{3}. This can’t happen because h(o_{1}) = o_{2}.

After the first f_{init}, we can’t have another f_{iniit} because calling f_{init} twice would take o_{1} to o_{2} the first time, and then to o_{3} the second time. All of the other f_{a} functions keep o_{2} at o_{2}. So we know the composition has to be f_{init} first, then some number of f_{1} functions forming a composed f_{w.}

If h is given any state in a machine as input, it returns the final state of that machine. If f_{init} is given any state in a machine as input, it returns the start state of that machine. For f_{w}(f_{init}(q)) to return qi^{final}, it must be the case that f_{w}(q_{i}^{start}) = q_{i}^{final}, for all i. This gives us a string w that is in the language of each machine.

**Difficulty**: 8. It’s interesting to see how the functions are made- that there is a function for each input symbol, instead of for each machine, which I, at least, would expect. Also, the use of the various o_{i} inputs is important, easy to mess up, and hard to come up with.