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
characteristics of a good algorithm

You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

One can change a binary tree into its mirror image by traversing it in Postorder is the only proecess whcih can convert binary tree into its mirror image.

1)    The set of the algorithms whose order is O (1) would run in the identical time.  True/False 2)    Determine the complexity of the following program into big O notation:

Which are the two standard ways of traversing a graph? i. The depth-first traversal   ii. The breadth-first traversal


Explain the Interfaces in Ruby Recall that in object-oriented programming, an interface is a collection of abstract operations that cannot be instantiated. Even though Ruby i

Define the External Path Length The External Path Length E of an extended binary tree is explained as the sum of the lengths of the paths - taken over all external nodes- from

Enumerate about the Data structure An arrangement of data in memory locations to signify values of the carrier set of an abstract data type. Realizing computational mechanis

In order to get the contents of a Binary search tree in ascending order, one has to traverse it in In-order