Algorithm of decorated graph, Data Structure & Algorithms

As we talked in class, a program with two integer variables is universal. Now, we consider a special form of four variableprograms. Let G = (V; E) be a directed graph, where V is a finite set of nodes, and E ⊆V X V be the set of (directed) edges (arcs). In particular, we identify a node as the initial node, and a node as the final node. Let x1; x2; x3; x4 be four non-negative integer variables. Further, we decorate each edge with one of the following instructions: (1 ≤i≤ 4)

xi:= xi + 1;

xi:= 0;

xi == c? (c is a non-negative integer)

The result is called a decorated graph (we still use G to denote it). The semantics of a decorated graph is straightforward. It executes from the initial node with x1; x2; x3; x4 being 0, then walks along the graph. G can walk an edge (v, v') if all of the following conditions are satisfied: for each 1 ≤i≤4,

  • if the edge is decorated with instruction xi:= xi + 1 for some i, the new value of xi is one more than the old value, and all the other xj(j ≠i) is unchanged.
  • if the edge is decorated with instruction xi:= 0, the new value of xi is set to 0, and all the other xj (j ≠i) is unchanged.
  • if the edge is decorated with instruction xi == c?, the value of xi must be c.

If at a node, G has more than one edge that can be walked, then G non-deterministically chooses one. If at a node G has no edge that can be walked, then G crashes (i.e., do not walk any further). We say that a decorated graph G is terminating if G can walk from an initial node to a final node and at the final node the values of x1; x2; x3; x4 satisfy the following constraint:

x1 = x2 = x3 = x4:

Show me an algorithm that answers (yes/no) whether G is terminating or not. (To correct a common misunderstanding, I shall point out that a walk could be arbitrarily long even though there are only 10 nodes in the graph! So, don't even try depth/breadth first search.)

Posted Date: 3/22/2013 4:06:38 AM | Location : United States







Related Discussions:- Algorithm of decorated graph, Assignment Help, Ask Question on Algorithm of decorated graph, Get Answer, Expert's Help, Algorithm of decorated graph Discussions

Write discussion on Algorithm of decorated graph
Your posts are moderated
Related Questions
Linear search employee an exhaustive method of verified each element in the array against a key value. Whereas a match is found, the search halts. Will sorting the array before uti

what''s queue ?

How to create multiple queue on single array?

Explain th term input and output-  Pseudocode Input and output indicated by the use of terms input number, print total, output total, print "result is" x and so on.

Think of a program you have used that is unacceptably slow. Identify the specific operations that make the program slow. Identify other basic operations that the program performs q

How branching takes place in Instruction pipeline. Explain with suitable examples

Column Major Representation In memory the second method of representing two-dimensional array is the column major representation. Under this illustration, the first column of

Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

what are registers? why we need register? Definition? Types? What registers can do for us?