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.

 

Reachability for 1-Conservative Petri Nets

As promised, here is the next problem, also using Petri nets.  I’m not 100% convinced that my definition of “1-Conservative” is accurate, but it seems to work for this reduction.

The problem: Reachability for 1-Conservative Petri nets.  This is problem MS4 in the appendix.

The description: A “1-Conservative” Petri net has each transition preserve the number of tokens on each side of the transition, and has at most 1 token per edge.  Given such a Petri net and a state M, is there a sequence of transitions that can reach M from the starting state?

Example: I had a hard time finding a non-trivial example of a 1-conservative network.  But maybe that’s ok.  Here’s another figure from the Murata paper:

There are no tokens in this picture.  But notice that if we start with no tokens, no state with tokens is reachable.  If we start with a token in the left state, then both 1-token configurations are reachable, but we won’t be able to reach a configuration with 0 tokens or 2 tokens in it.

Reduction: This is Theorem 3.1 in the Jones, Landweber, and Lien paper.  The reduction is from Linear Bounded Automaton Acceptance.

So we start with a LBA M, with p tape symbols, and m states.  It has an input string $x1x2..xn$.  Our task is to build a 1-Conservative Petri Net.

The first set of places in the Petri net will be represented by Aij,  0 <= i <= n+1, 1 <= j <= p.  This will represent the tape.  Aij will have a token iff space i of the tape has symbol j.

We will also have places labeled Qij, 0 <= i <= n+1, 1 <= j <= m.  This will simulate the states.  Qij will have a token iff the head is over space i of the tape while the machine is in state j.

We’ll also have 2 special places C and D.  Tokens start in all of the Aij places corresponding to the input string of the tape, and in Q11 (the machine starts in state 1 over cell 1 of the tape).

The transitions in the net are based on the transitions in the machine.  If we have a transition from state qs and symbol at to state qr, writing a symbol al we add a transition Qis + Ait -> Qjr + Ail for all i.  “j” in the destination is either i, i+1, or i-1, depending on if the head stays, moves right, or moves left.

If we are in a final state qs, we add a transition Qis->C for all i.

We also add the transition C+Aij -> C+D.

Note that all transitions have 1 token per edge and preserve the number of tokens, so this is a 1-Conservative Petri net.

Our destination state is:

  • 1 token in C
  • N tokens in D
  • 1 token in each Ai1

Since all of these transitions simulate the movement in the LBA, if the LBA accepts the string, we follow all of the transitions to eventually put the token in C.  This allows us to do the last transition to put the tokens in D.

In the other direction, if we can reach the desired state, we must have put a token in C.  To get there, we must have gotten to a final state qf.  Thus, the LBA must have accepted the string (by following the transitions we took in the Petri Net to get to that qf state).

Difficulty:  7.  I like how they can represent all combinations of tape symbols and locations as places.  I’m a little worried because it looks like this assumes you’ll never go beyond the end of the input string, where I thought an LBA was allowed to use a linear multiple of the input string’s size.  Is there some kind of equivalence proof that says an LBA can only need its own input string’s space exactly?

Non-Liveness of Free Choice Petri Nets

The next couple of problems talk about “Petri Nets”, which I hadn’t heard of before.  I found a decent explanation here, and the Wikipedia article also has a good explanation, though I found it pretty dense.  I also took some definitions from a nicely explained paper by Murata.

The problem: Non-liveness of Free Choice Petri Nets.  This is problem MS3 in the appendix.

The description: Given a Petri Net, with the “free choice” property (which means every “place” node either goes to one transition or has input from 1 transition), is it not live? A Petri Net is live if, after any sequence of transitions, each transition remains potentially firable by some future sequence of transitions.   So we are asking- is there a set of transitions that will create a situation where at least one transition will no longer be able to fire?

Example: Here is a live Petri Net from Murata’s paper:

Notice how whatever sequence of transitions we do from the initial state, we will be able to “reset” the net and get to any transition.

Notice that this net is also not “Free choice”, because place P1 gets inputs from 2 transitions, and also feeds into 2 transitions (The 10¢ and 25¢ places also violate this property)

Here is a non-live one from the same paper:

This is not live because even though every transition is reachable from the start state, if we choose the t1 transition to start, we will not be able to ever fire t4.  (In fact, we won’t be able to fire any other transitions).

Also notice that this second Net does have the Free choice property, since each circle has either indegree or outdegree 1 (or both).

Reduction: The reduction is in the paper by Jones, Landweber, and Lien, and it reduces from CNF-SAT. So we start with a formula that has n variables and k clauses.  The Petri Net we build has three places for each variable xi:

  • A place xi associated with the positive setting of the variable
  • A place ~xi associated with the negative setting of the variable,
  • A third place Ai, which will be used to link the two.

For each literal li in clause Cj, we have a place associated with the negation of the literal in the clause (the setting that does not make the clause true).  So, for example, if xi was in clause Cj, we’d have a place (~xi, Cj)

We will also have one last place “F”, which will mean the formula is not true (because some clause was not true)

Our net will have 1 token for each variable, starting in the “A” places, one for each variable.

We will have transitions between:

  • Each Ai and its xi and ~xi
  • Each xi and all of the places corresponding to literals that hold the negation of that variable.  So a transition between xi and places like (~xi, Cj)
  • A transition straight to F for each clause if all of the “literal” places for a clause have tokens.
  • A transition from F to each Ai

The idea here is that the places for literals will gather tokens if their variables are set in a way to not make the clause true.  If none of the literals in the clause are set to make the clause true, then the clause is false, all of their places will have a token, and F will fire.  F will then enable the firing of all of the A places, and we will go around again.

So, let’s suppose the formula is satisfiable.  The tokens start in each Ai, which has transitions to xi and ~xi.  Pick the transition that corresponds to how we set xi in the satisfying assignment of the formula. This will enable some transitions in clauses with xi in it to fire- the literals that have the opposite settings of the variable.  But since every clause is satisfiable, there will not be enough firings to enable the transition to F to fire, and the net will be dead (no more firings will happen after those).

On the other hand, if the formula is not satisfiable, then all assignments of variables make at least one clause false.  So no matter how we decide to make the Ai transition go (to the xi or to the ~xi), some clause will not be satisfied, and that clause will be able to fire its transition to F.  Firing F puts a token at each Ai, enabling all transitions to start again.

Difficulty: 6.  Obviously, this only works if you’ve discussed Petri Nets previously, since learning about them is a separate involved discussion.  But outside of that, the idea of a transition firing on a clause being false is a pretty cool one, and makes sense, because we are looking for non- liveliness, so a Satisfiable formula means we want dead transitions.

Also, I want to commend the Jones, Landweber, and Lien paper for having a very nice example explaining how a formula turns into a Petri Net complete with transitions and explanations working through how what fires and why.  I don’t get that in every paper, and it was nice of them to think about people like me coming along 45 years later.

Cyclic Ordering

This problem is very similar to the Betweenness problem from last time, with a slightly different ordering rule.

The problem: Cyclic Ordering.  This is problem MS2 in the appendix.

The description: Given a set C of triples (a,b,c) from some universal set A, can we find an ordering f of the elements of A, so that for each triple in C, either:

  • f(a) < f(b ) < f(c)
  • f(b) < f(c) < f(a)
  • f(c) < f(a) < f(b)?

Example: Like last time, let’s say A = {a,b,c,d,e,f}.  Here are some triples:

(a,b,c)
(e,b,c)
(a,e,f)
(e,f,a)
(d,f,c)

The usual lexicographic ordering of elements of A will satisfy these triples.

A triple that won’t work with that ordering is (a,e,b).  But an ordering {a,e,b,c,d,f} would satisfy all triples including this new one.

Reduction: Galil and Megiddo use 3SAT.  So we start with a formula with p clauses (each clause is xi∨ yi∨ zi) over r variables (u1..ur, and their negations).  Order each clause so that the variables in it are in increasing order of their subscript.  Our set A will have 3 elements for each variable ui: αi, βi and γi. It will also have 5 additional elements for each clause (these will be the j through n described below)

Each variable is “associated” with a triple from these elements of A.  The positive version of the variable ui is associated with (αi, βi, γi).  The negated version of the variable ~ui is associated with the triple (αii, βi).  These triples won’t get added to C,  but will be the basis of the triples each clause adds to C.

So suppose we have a clause x∨y∨z.  Each of these literals has a triple associated with it as defined above.  Let’s call those triples (a,b,c), (d,e,f), and (g,h,i).  Using those 9 symbols plus the “extra” symbols for this clause j,k,l,m, and n, create the following triples, called Δ0: {(a,c,j), (b,j,k}, (c,k,l), (d,f,j), (e,j,l), (f,l,m), (g,i,k), (h,k,m), (i,m,n), (n,m,l).  These triples, for each clause, create our set of triples C.

Now, suppose we have an assignment of variables- a set S of ui and ~ui that has exactly one choice for each i.  For each clause, build a set of triples Δ out of Δ0 and the triples associated with the literals not in S.  Then if S includes a literal that makes the clause true, there is a way to satisfy every ordering in Δ.  They show this with a table giving the possible assignments.  Here are 2 examples:

  • If S has just x in it (and not y and z), then Δ adds the triples (a,c,b), (d,e,f), and (g,h,i) and the ordering ackmbdefjlnghi will satisfy all triples.
  • If S has y and z in it (and not z), then Δ adds the triples (a,b,c), (d,f,e), and (g,i,h) to Δ0, and the ordering abcjkdmflnegih will satisfy all triples.

In the other direction, if a clause is not satisfied by this assignment, then none of its literals are in S, and so we form Δ by adding the triples (a,b,c), (d,e,f), and (g,h,i) to Δ0.  But if we had an ordering of the elements of A that satisfied the triple (a,b,c), it must also satisfy the triple (a,c,j) from Δ0.  This means that (b,c,j) is effectively a triple as well (the ordering has to satisfy that triple as well).  Since (b,j,k) is in Δ0, then (c,j,k) is effectively a triple, and since (c,k,l) is in Δ0, we can conclude that (j,k,l) must also satisfy the ordering.

We can perform a similar analysis to eventually conclude that (l,m,n) must also satisfy the ordering.  But we have the triple (n,m,l) in Δ0, and there is no way to satisfy both consistently.  Thus, if a clause is not satisfied, there is no legal ordering to satisfy all of the triples in Δ.

Taking this analysis and applying it to all clauses completes the reduction.

Difficulty: 8.  It’s not obvious, at all, even looking at the problem, how you can come up with these different triples.  I can (mostly) follow the logic and see that it works, but wow, coming up with this must have been a huge pain.

Betweenness

The last section is on “Miscellaneous” problems.  There are some weird ones in here, but we start with a pretty straightforward number problem.

The problem: Betweenness.  This is problem MS1 in the appendix.

The description: Given a set C of triples (a,b,c), where each element of each triple comes from a superset A, can we find an ordering of the elements of A such that according to that ordering, each triple is in either increasing or decreasing order?

Example: It’s actually hard to do a good example for this because most groups of symbols (digits, letters, subscripts, …) have an implicit ordering of elements, and to go against that would be confusing.  Having random symbols without connotations of meaning gets pretty confusing pretty quickly as well.

So let’s lean in and say A = {a,b,c,d,e,f} and our triples are:

(a,d,f)
(f,d,b)
(h,d,a)
(f,g,h)
(d,f,h)

We’re allowed any ordering of the elements of A, and the “normal” lexicographical one with ‘a’ first and ‘f’ last satisfies the betweenness rules.

But now suppose we add the new triple: (b,a,d).  That is an illegal triple in our normal order, but if we change our ordering so that ‘b’ is first and ‘a’ is second, we can still satisfy all of the triples.

Reduction: The paper by Opatrny uses Hypergraph 2-Colorability (which we called “Set Splitting”).  Recall that our reduction only made sets of size 3, so we can start with an instance where each set has at most 3 elements (or, each hyperedge connects at most 3 vertices).

So, suppose we have a set of N vertices s1..sn, a set of J 3-vertex hyperedges (ai, bi, ci), as well as M 2-vertex “regular” edges (di, ei).

Our first job is to build superset A.  It has:

  • One symbol for each vertex,
  • A new symbol X.
  • A set of J new symbols Yk, one for each 3-vertex hyperedge.

Now we build C.

  • Each hyperedge (ak, bk, ck) generates two triples: (ak, Yk, bk) and (Yk, X, ck)
  • Each two-vertex edge (dk, ek) generates the triple (dk, X, ek)

Suppose the graph had a 2-coloring.  Recall that meant that each vertex had a color (the paper uses red and blue) so that each edge and hyperedge touches vertices of both colors.  We need to make an ordering of A that satisfies all triples.  The ordering will have positive,  negative, and rational ranks.

  • X has rank of 0.
  • If vertex si is red, its rank is i.  If it’s blue, its rank is -i.
  • Each Yi was associated with a hyperedge (ai, bi, ci).
    • If ai and bi have the same color (and so the same sign), Yi‘s rank is min(rank(ai), rank(bi)) + \frac{1}{i+1}.
    • If they have different colors, the rank is \frac{1}{i+1} if ci is blue, and -\frac{1}{i+1} if ci is red

So, suppose every edge had 2 colors.  We know:

  • If ai and bi are the same color, they are the same sign, and Yi is between them, satisfying the (ak, Yk, bk) triple.
  • If ai and bi are the same color, ci must be the other color (and the other sign from Yi), satisfying the (Yk, X, ck) triple.
  • If ai and bi are different colors, they are different signs.  Setting Yi to a value between 1 and -1 satisfies the (ak, Yk, bk) triple.
  • If ai and bi are different colors, ci can be either color, so making Yi the opposite sign as ci satisfies the (Yk, X, ck) triple.
  • An edge with just 2 vertices needs both vertices opposite colors, and thus opposite signs, so the (dk, X, ek) triple is satisfied.

So far, so good.  In the opposite direction, suppose we have a solution to the betweenness instance.  We’ll assign colors to vertices such that a vertex’s color is red if its rank is > X’s rank.  Otherwise, it will be assigned blue.  Our triples will now allow any set of ai, bi, and ci to all be greater than or less than X (or for both di and ei to be greater than or less than X), which means that every edge in the hypergraph has both a red and a blue vertex.

Difficulty: 7.  It’s relatively easy to see what you need to do.  It’s harder to make the numbers actually work.  Even this paper has to resort to using rational numbers for the ranks, which is a fixable problem, but certainly not obvious.

Programs With Formally Recursive Procedures

This is the last of the “Program Optimization” problems, and the next section is the last one on “Miscellaneous” problems, which has 19 problems in it.  So, unless some diversion into a problem not in the book happens, we’re on the countdown through the last 20 problems!  The end is in sight!

The problem: Programs with Formally Recursive Procedures.  This is problem PO20 in the Appendix.

The description: Given a set of function definitions and a program that makes a sequence of function calls using those definitions (the paper by Winklmann uses Algol because he wrote it in 1982.  But any language that allows recursion should work).   Are any of the procedures in the program formally recursive?  For our purposes, “formally recursive” means that there exists a chain of calls that has a call to a function higher in the chain (not necessarily a parent, any ancestor will do).

My first instinct was to wonder if this problem was actually undecidable.  It’s not because we will have some fixed # of procedures d, and so any call chain needs to be checked only to depth d+1- if we get that far, we must have a repeat someplace.  If we never get that far, we can back up and check other call chains, eventually checking all of the paths through the call tree exhaustively.  The proof that the problem is in NP is in the paper, but it involves representing the call tree as a DAG so we can use one vertex for two equivalent paths.  Winklmann says that if you do that the number of vertices is “bounded” by the number of procedures in the program (he doesn’t say what that bound is, though).

Example: It’s hard to make a small example that’s not obvious.  How about this:

E(){
  E();
}

D(){
}

C(){
 A();
}

B(){
 D();
}

A(){
 B();
 F
}

main(){
  A()
}

If “F” is replaced by a call to C, the program is formally recursive, because the call chain main->A->C->A has a repeat.  If we replace that F with another call to B the program is not formally recursive because even though recursive functions like E exist (and even though B gets called twice in two different chains), there is no call chain that will start at main and hit E (or anything) more than once.

Reduction: Winklmann uses 3SAT.  So we start with a formula B with m clauses and n variables.  We’ll write some functions:

AssignXi(c1..cm): generates two calls to AssignXi+1. The function has one parameter for each clause.  The first call simulates setting variable Xi to true by passing a “true” value in all parameters that represent clauses that have variable Xi represented positively.  The second call simulates setting variable Xi to false by passing a “true” value in all parameters that represent clauses that have variable Xi returning negatively.  In all other cases, the function passes on the ci parameter it was given.

AssignXn(c1..cm): once we reach the end of the variables, we have to stop.  This function calls the “Check” function we’ll be defining in a minute twice, once reflecting setting variable Xn to true, one reflecting setting it to false.

Truej(cj+1..cm):There is one “true” function for each clause, each one has a parameter for all clauses with larger numbers. The paper writes this function a little weirdly, but I think a good definition is:

if(cj+1 is true){
Truej+1(cj+2..cm);
else
Falsej+1(cj+2...cm);
}

So, as long as the parameters are true, we’ll continue calling down through the  true functions to the end.  The last True function is what will make us formally recursive:

Truem(): Calls Assign1(False, False, ...False). Our main program will begin with a call to Assign1 with these exact parameters, so if we can get here, we will have found our recursive call.

The False functions end a call chain:

Falsej(cj+1..cm){
// do nothing
}

The Check function’s job is to start the appropriate call to True or False:

Check(c1..cm){
if(c1 is true)
True1(c2..cm);
else
False1(c2..cm);
}

Our main program is just a call to Assign1(False, False..False).  It’ll go through all of the various AssignXifuntions trying to assign variables (and thus clauses) to true. Each assignment will be checked, and each check will either hit a False function (meaning a clause wasn’t satisfied, and so we will backtrack and try an alternate assignment) or the final True function, which will generate our recursive call.  So this program has a recursive call chain if and only if the formula was satisfiable.

Notice that while the run of this program might take exponential time, that’s ok because reductions are concerned with the time it takes to create the new problem instance, and there are “just” 2m+n+1 functions to create.

Difficulty: 6.  This is a neat problem and reduction- I think the “write a backtracking program to try all combinations” is pretty gettable.  The hard part is the check and true/false functions at the end.  We can’t really use loops because loops make programs undecidable (you can’t show the problem is in NP by going down d+1 calls if you might have an infinite loop someplace and won’t get through all of those calls).  So we have to build a chain of recursive calls instead, with dead-ends to force the backtracking.

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?

Non-Containment for Free B-Schemes

Here is another scheme problem with a different kind of a reduction.

The problem: Non-Containment for Free B-Schemes. This is problem PO18 in the appendix.

The description: A “B-Scheme is” a rooted, directed, acyclic graph where each vertex has outdegree of either 0 (a “leaf”) or 2 (a “test”).  The test vertices label their out edges as “T” or “F”.  Each vertex gets a label.  Test vertices are labeled as boolean Boolean variables, leaves are labeled with function symbols (with the special symbol “Ω” meaning “undefined function”.

Multiple vertices can have the same label, but in a “free” B-scheme, no path from the root to a leaf hits two vertices with the same label.  We can “assign” truth values to the boolean variables, which then define a path through the scheme to a leaf.  The value of the truth assignment is the label given to the leaf we end up in.

Suppse we have two such B-Schemes, S1 and S2.  S1 is contained in S2 if for all assignments of variables, either S1 ends up in Ω, or S1 ends up in a leaf that is the same label as S2‘s leaf with the same assignment.

So, our question is: Given two free B-Schemes S1 and S2, is S1 not  contained in S2?

Example:

Here is our S1:

“O” is the label for the Ω leaf

Here is S2

(x1a and x1b both are labeled for the variable x1.  I had to give them different names so Graphviz didn’t think they were the same variable.)

S2 returns the number of true assignments of x0 and x1.  S1 correctly finds the same leaf if at least one variable is true, but goes to O otherwise.

But, S1 is NOT contained in S2 because assigning both variables to true puts S1 in L1 and S2 in L2.

Reduction: The paper by Fortune, Hopcroft, and Schmidt defines this problem and reduces from 3SAT. First, we replace all positive occurrences of the same variable xi with new variables ui1..uip (if it occurred p times).  We similarly replace all negative occurrences of xi with vi1..viq (if it appeared negated q times).  Our job is to build two schemes.

S1‘s job is to tell us if the formula is satisfiable.  Each clause (a1,b1, c1), gets a chain of vertices. It goes “across” on F, and down to the first variable of the second clause on T.  If all literals get assigned F, we end up in a Ω leaf.  The final clause has edges from T to our output “f” leaf (Yes, that means the vertex we reach when the formula is satisfiable and all of the clauses are true is labeled “f”.  I’m sorry.)  Here is the paper’s example.  Keep in mind that each of the a,b, and c vertices here represent literals whose actual value in the formula is one of the u and v variables we created above.

S2‘s job is to make sure that all of our new u and v vertices have the same (and consistent) truth values.  If we ever have a ui with a different truth value than some other uj (or if it has the same truth value as its corresponding vj) we jump to f.  If everything is ok, we jump to a new end point g.  Here is the diagram from the paper.  Notice that they are doing this for all of the replacements for all of the variables in one scheme.

If our original formula was satisfiable, we would find a way to make S1 go to f, and since all of the variable assignments are consistent, we could use those assignments to make S2 go to g, so S1 is not contained in S2,  In the other direction, if S1 is not contained in S2, then since all S1 can reach is Ω and f, it must be the case that there is an assignment that leads S1 to f and S2 to g.  S2 ends in g only when its u and v variables are assigned consistently.  S1 goes to f only when its clauses are all satisfied.  Thus, we have found a way to satisfy the formula.

Difficulty: 7.  This is different from the other scheme problems we have seen, where the second scheme is the trivial “yes” scheme.  Here, we need to use both schemes to check different aspects of the solution.  That’s pretty cool.

Strong Inequivalence for Monadic Recursion Schemes

As promised, now we extend the proof of the Ianov Scheme problem to other problems.

The problem: Strong Inequivalence for Monadic Recursion Schemes. This is problem PO17 in the appendix.

The description: Suppose we have a sequence of expressions F1..Fn.  Each is of the form:

Fi(x) = if Pi(x) then Ai(x) else Bi(x)

Each Pi is a boolean predicate, each Ai and Bi are compositions of function calls from F or from a given set of “basis” functions f. This is a monadic recursion scheme.  A linear monadic recursion scheme adds the requirement that each A and B composition can have at most one call to one of our F functions.

So, similar to our last problem, if we are given a set of basis functions f, a set of predicates P, and two schemes that take a start variable x0 into an initial function F0, can assign functions and predicates to the two schemes to make them have different outputs?

Example: Let’s turn our Ianov Scheme example into this format:

Scheme 1:

F1(x): If P(x) then F2(x), else f( F2(x))

F2(x): If P(x) then x else x

Scheme 2:

F1(x) If P(x) then x else x

Scheme 2 is the identity function- it always returns x.  Scheme 1 is the identity when P(x) is true, or when f is itself the identity.  So if we have a predicate set of {p(x) = true, p(x) = false} and a function set of {f(x) = x+1}, then we can make Scheme 1 return a different value for its starting variable and thus the two schemes are equivalent.

Reduction: This is the paper by Constable, Hunt, and Sahni again, and in fact builds off of their Ianov Scheme result from last time.  The idea is that if we can take any program in that format, and convert it into a recursion scheme, then we have a reduction.   So, suppose we are at instruction “j” of the program, which will map to function Fj of our scheme. Recall those programs had three kinds of instructions:

  1. x=f(x), where f is some function- f will be a basis function in our recursion scheme, and we will create the statement:Fj(x) = If P1(x) then Fj+1(f(x)) else Fj+1(f(x)). This will take us to the next “line” of the program sending f(x) as the variable we are working on.
  2. If Pk(x) goto I1 else goto I2, then we create the statement:
    Fj(x) = If Pk(x) then FI1 else FI2. This will take us to the corresponding “line” of the program we will do next, based on our predicate Pk
  3. Halt.  Then we just do:
    Fj(x) = x

This turns any program into an equivalent monadic recursion scheme, thus converting our Ianov Scheme problem instance into a monadic recursion scheme instance.

Difficulty: 5.  The actual “Write this program as a set of function statements” task isn’t hard.  As usual, wrapping your head around the definitions of what the problems are talking about is the difficult part.

Strong Inequivalence of Ianov Schemes

I’d never heard of “Ianov schemes” before, but we’ll be using them for the next couple of problems, so let’s take a look!

The problem: Strong Inequivalence of Ianov Schemes.  This is problem PO16 of the appendix.

The description: Given two programs with a single variable x and instructions:

  1. x = f(x) (where f is some function from some given set of functions F)
  2. if p(x) goto I1 else goto I2 (p(x) is a boolean predicate from some given set of predicates P, I1 and I2 are instructions in the program)
  3. Halt

Are the two programs not strongly equivalent: Can we find a function from F for each f, a predicate from P for each p, and an initial value for each variable that gives different final values for the variable in both programs?

Example: Here is one similar to what we will need in a minute:

P1:

1: if p(x) then 4 else 2
2: x =  f(x)
3: Halt
4: Halt

P2:

1: Halt

Suppose the only choice for f is f(x)= x+ 1(so, changing the variable).  Then the programs are different if we have a p(x) that will let us get to line 2 in P1.  If our only choice of p is something like “p(x) = true”, then the two programs are always equivalent.  If our set of P is (p(x) = true, p(x) = false), then we can choose a predicate that makes the programs inequivalent.

Reduction: The paper from Constable, Hunt, and Sahni basically does this in two parts.  G&J say to use 3SAT, but this looks to me like DNF Non-Tautology.

First (this is Proposition 2.11), they show how to take a DNF formula and turn it into a program.  The program works as a giant chain of if statements checking each literal in each clause.  If a literal is checked to be false, we move on to the next clause.  If all of the literals in a clause are true, we make it to the first (“+”) halting state.  If none of the clauses make it to the “+” state, we go to the second (“-“) halting state.  This means that the “-” state is only reachable if we do not start with a tautology.

Next (This is part iii of Corollary 2.14 of Theorem 2.13), they show that they can extend this into an Ianov scheme program by making the “+” state be just a halt command (so the variable never gets changed), and the “-” state be:

1: x= f(x)  (Where f is some function that changes x)
2: halt.

So the only way this program is different from the trivial “just halt” program is if we can reach the “-” instruction, which only happens if the formula is not a tautology.

Difficulty: 5. The program to test the non-tautology is not that hard.  As usual, the hardest part is parsing all of the definitions in the problem