Tag Archives: Linear Bounded Automaton Acceptance

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?

Protected: Inequivalence of Finite Memory Programs

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

Protected: Context-Sensitive Language Membership

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

Protected: Linear Space Acceptance

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: Quasi-Realtime Automaton Acceptance, Quasi-Realtime Language Membership

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

Protected: Two-Way Finite State Automaton Non-Emptiness

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

Protected: Safety of File Protection Systems

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

Protected: Linear Bounded Automaton Acceptance

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