Tag Archives: Difficulty 8

Finite Function Generation

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 Fi such that M accepts w if and only if there was at least one string in the language of each F1 (i.e., the intersection of the languages of the machines is non-empty). We’ll label state j of machine i qij.  Because they are FA’s, each machine i has one start state (qistart ), and they were built to have one final state (qifinal).

Create a set A which will be the set of the states of all machines, plus three extra elements: o1, o2, and o3.  Every symbol in the common alphabet of the machines a gets a function fa:

  • fa(qjj ) = The state we go to from qij on input a.  Note that this will be some qik for some k (some state on the same machine).
  • fa(o1) = o3
  • fa(o2) = o2
  • fa(o3) = o3

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 fw for some string w: fw(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 fw(qistart ) = qifinal.

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

  • f(q) returns qistart if q is any state in a machine qi
  • f(o1) = o2
  • f(o2) = o3
  • f(o3) = o3

Now we’ll build our function h:

  • h(q) returns qifinal if q is any state in a machine qi
  • h(oi) = finit(oi) for i from 1 to 3.

Suppose that there is a string w in the languages of all of our automata Fi.  This would mean that for all machines i, fw(qistart ) = qifinal.  It also means that those f functions need to map fw(o1) to o3, fw(o2) to o2, and fw(o3) to o3.  We can get this by h = fw ° finit.

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 finit because all other functions take o1 to o3, and then all functions keep o3 at o3.  This can’t happen because h(o1) = o2.

After the first finit, we can’t have another finiit because calling finit twice would take o1 to o2 the first time, and then to o3 the second time.  All of the other fa functions keep o2 at o2.  So we know the composition has to be finit first, then some number of f1 functions forming a composed fw.

If h is given any state in a machine as input, it returns the final state of that machine.  If finit is given any state in a machine as input, it returns the start state of that machine.  For fw(finit(q)) to return qifinal, it must be the case that fw(qistart) = qifinal, 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 oi inputs is important, easy to mess up, and hard to come up with.

 

Non-Freedom for Loop-Free Program Schemes

Our old friend Bounded PCP is back for this reduction. What I actually originally wrote in that post was wrong (what I thought was the PCP reduction was actually their reduction for today’s problem), and I modified that post a little to reflect that.  I’m still sad that I can’t find an easy Bounded PCP reduction, but at least for today, all we need is the knowledge that it’s NP-Complete.

The problem: Non-Freedom for Loop-Free Program Schemes.  This is problem PO19 in the appendix.

The description: Suppose we have a set of instructions without loops (so just assignment of a variable, if statements that jump to other instructions, and halt.  Kind of like our Ianov Scheme instructions, but possibly allowing more than one variable).  “No loops” also means that our if statements cannot create a cycle.

Is there a directed path through this set of instructions that can never be followed by any actual computation?  (A program is “free” if all paths are reachable, so “non-free” means some path is not reachable).

Example: Here’s a very simple program:

1: if p then I2 else I3
2: x = 1
3: x = 2

If “p” is a predicate that is always true, than the path I1-I3 can never be realized and the program is non-free.  If p can be true or false, then all paths are possible and the program is free (and so this “non-free” instance is a “no”)

Reduction: As I alluded to at the start, Constable, Hunt, and Sahni reduce from Bounded PCP.  The idea is that they will take a BPCP instance and build a program where all paths are possible if and only if the BPCP instance is unsolvable.  The general idea is to build a scheme where we have 2 variables x1 and x2, which correspond to the two BPCP strings we are building.  At the end of the scheme, we have two predicates: P(x1) and P(x2).  If x1 and x2 are the same (which means we have built the same string) then we can’t get to a path that has true for one and false for the other.

The problem is that we could get that path if we choose a bad set of strings to make x1 and x2, and I’m not sure how we avoid that.  Here’s the picture they put in the paper basically as the entire proof:

I think maybe it might be an example for an instance of BCPP bounded at 1 string from each side (which is why the end case is a set of P2 predicates), but they don’t say and I’m not sure.  It’s not helped by the fact that they use “i” for the number of substrings used, and for an index in one of the strings, or that their font has the letter “l” look the same as the number “1”, or that they don’t explain anywhere why we have 2 levels of predicates, or what those predicates are supposed to be testing for.  I think the top predicates (the P1 ones) are choosing whether we take substring 1,2, and so on to build our solution.  But that means these “h” functions are appending the next character onto the string we’re building, and that’s not said anywhere either.

So, yeah, I don’t know what about this diagram doesn’t let me take incorrect choices for the BPCP problem, leading to a different x1 and x2, and creating a path that way. I definitely wish the paper had more explanation.

Difficulty: 8.  I’m not terribly filled with confidence that my explanation is right, because the explanation in the proof doesn’t really explain much to me.  Am I missing something?

Protected: Microcode Bit Optimization

This content is password protected. To view it please enter your password below:

Protected: Arc Coloring

This content is password protected. To view it please enter your password below:

Protected: Feasible Register Assignment

This content is password protected. To view it please enter your password below:

Protected: Tree Transducer Language Membership

This content is password protected. To view it please enter your password below:

Protected: ETOL Grammar Non-Emptiness

This content is password protected. To view it please enter your password below:

Protected: Regular Expression Inequivalence on Single Character Alphabets

This content is password protected. To view it please enter your password below:

Protected: Covering for Linear Grammars

This content is password protected. To view it please enter your password below:

Protected: Reduction of Incompletely Specified Automata

This content is password protected. To view it please enter your password below: