Monthly Archives: October 2022

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?


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.