Tag Archives: Difficulty 7

Word Problem For Products of Symmetric Groups

The next problem in the Appendix is “Register Sufficiency for Loops”, which basically asks “Given a set of loop variables and K registers, can we assign variables to registers so that there is no conflict between loop iterations?”.  The reduction is better explained in two parts.  This is the first part.

The problem: The “Word Problem for Products of Symmetric Groups” (WPPSG).  This is not in the appendix.  It is defined in the paper by Garey, Johnson, Miller, and Papadimitriou that has the reduction we will want for the Register Sufficiency for Loops problem.

The description: Given an integer K, and m sets X1 through Xm, each containing a subset of {1..K}, and a permutation π of the numbers from 1-K. Can we get π by a series of permutations defined by permuting with X1, then X2, and so on through Xk?

Example:

To “permute with” an Xi set,  I mean we can rearrange the elements corresponding to the positions in Xi however we want, but elements that are not listed in Xi do not move.

So, suppose we had K=5 and 3 sets:

X1 = {1,3,5}

X2 = {2,3}

X3 = {4,5}

If π = {3,1,2,5,4}, we can do this by first permuting with Xusing {3.1,5} turning {1,2,3,4,5} into {3,2,1,4,5}.  Then we permute X2 using {3,2},turning {3,2,1,4,5} into {3,1,2,4,5}.  Finally, we permute X3, using {5,4} turning {3,2,1,4,5} into {3,2,1,5,4}.

If π = {2,1,5,3,4} we can’t do it.  There is no way to get a 2 into the first location, since the only permutation that can possibly place something in the first location is X1, and we have to do the X permutations in order.

Reduction:

If you’re following along, this is Theorem 2 of the paper.  They go from Disjoint Connecting Paths, but add the restriction that the graphs are directed acyclic graphs.  (They say it’s a “trivial modification” to a standard reduction.  We did that reduction slightly differently, but since we went from a flow problem, I think it is fine to convert that to do a DAG version of the problem reduction from a directed version of the flow problem).

They also modify the problem so that the start vertices all have indegree 0 (and all vertices with indegree 0 are start vertices), and all end vertices have outdegree 0 (and all vertices with outdegree 0 are end vertices).

So, we’re given a DAG G, and a set of start vertices s1..sn along with their matching end vertices t1..tn.  First, we will take the graph and replace all edges a= (u,v) with a pair of edges going through a new vertex just for edge a: (u, wa) and (wa, v).  That new vertex is “private” to the edge and is not used anywhere else.  Our new graph G’ has q vertices.

Since we do have a DAG, we can topologically sort the vertices.  Set up a sorting so that the first vertices in the sort are the vertices s1..sn. We can get away with this because all of the s vertices have indegree 0. Similarly, make the last vertices in the sorting be t1..tn.

For each vertex vi, define B(i) = {j:(vi, vj) is an edge}.

Now we’re ready to build our WPPSG instance.  Our X sets are:

Xj = {n+j} ∪ B(n+j) for j from 1 to q-n

The last set is Xq-n+1 = {1,2,…q-n}

The permutation we want to build is:

π(i) = q-n+i for i from 1 to n

π(i) = i-n for i from n+1 to q.

Our WPPSG instance has one position in its permutation for each vertex in G’.  Every position starts labeled by its own index.  Each set Xi contains vertex vn+1 and its immediate predecessors.  So permutation X1 will replace s1 with a label of one of its neighbors, which corresponds to moving along that edge.  Suppose we permute s1 with some vertex v.  Then when we get to Xv, we will permute with one of v’s neighbors, and so on down the chain until we get the final position on a t vertex.  The final permutation ensures that we have eventually permuted the labels to end up with their corresponding t vertices.  (It doesn’t matter what happens with the rest of the labels).

Difficulty: 7.  I like the idea of “pushing” a path through a graph into a permutation problem.

Context-Free Programmed Language Membership

Here’s another kind of grammar I hadn’t heard of until doing these problems.

The problem: Context-Free Programmed Language Membership.  This is problem AL17 in the appendix.

The description: Given an ε-free Context-Free programmed grammar (explained below) G, and a string x, is x in the language generated by G?

Example: A programmed grammar gives a label to each production, and then after each production a set of labels for the “next” production, depending on whether we did the production or not.

So we might write a grammar like:

1: S->aSa {2} {3}

This means that if we do the production S->aSa we next go to production 2. If we don’t, we next go to production 3

2: S->bSb {1,4}{3}

Now, if we do this production, we have a choice of 2 production rules to follow.  We can go do 1 again, or we can go to 3.

3: S->a {}{}

If we have a terminal, we have no choice for the next production.

4: S->b {} {}

So, this grammar could produce the string ababa by the productions:

1: S=>aSa.  Next, we go to 2.

2: aSa=>abSba.  Next, we’ll go to 1 (we could have also gone to 4)

1: abSba=>abSba (we decide not to do the production, and so go to 3)

3: abSba=>ababa.  (we stop because we have no non-terminals left)

Reduction: The paper by Shamir and Beeri has the reduction, but I have a hard time following their notation, so I will try to rephrase it.  The reduction is from 3-CNF-Satisfiability.

What we’ll do is start with a CNF formula.  We’ll start by creating a CFG that generates strings where for each clause (l1, l2, l3) we generate all combinations of T1, T2, T3, F1, F2, and F3 with at least one T.  This will represent the ways we can make a clause true.  The T’s and F’s will be non-terminals.

Now we will try to replace the T’s and F’s with the actual literals from the formula with the following rules:

1:  T1-> q1  {2}{3}

2: T1->q1 {2} {4}

3: T1->~q1 {3}{5}

4: F1->~q1 {4}{6}

5: F1->q1 {5}{6}

Rule 6 starts the process again on the next literal.  The idea is that with rule 1 we either replace T1 with q1 (setting variable q1 to true, and sending us down a chain that will replace all F1’s with ~q1) or won’t (which will send us to rule 3, where we set T1 to ~q1, meaning we set q1 to false, and go down that chain of replacements).

Our question then becomes can this grammar can generate the original input string of the formula?

Difficulty: 7.  I had an alternate formulation where I replaced each literal with T or F and tried to form a chain of all T’s.  I couldn’t think of a way to let the grammar define “at least one T in a clause”  and still keep it context-free (a production like TTT->”yes” is not context-free because there is more than one non-terminal on the left side), which I think is why this solution goes the other direction (the final string has the literals, where for mine, the literals in the formula were non-terminals and I wanted my terminal string to be “Yes”).  But the idea of using the program to “choose” whether a variable is set to true or false, and then you’re forced to use the substitutions given in the program to keep all of the other replacements of that variable the same isn’t that hard to get.

 

Protected: Reynolds Covering for Context-Free Grammars

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

Protected: Finite State Automaton Intersection

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

Protected: Non-Erasing Stack Automaton Acceptance

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

Protected: NxN Go

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

Protected: Annihilation

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

Protected: Generalized Kayles

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

Protected: Generalized Geography

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

Protected: Simultaneous Divisibility of Linear Polynomials

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